Sun May 31 2020

dc コマンドの練習

dc はスタックマシンによる計算機を実現するコマンド. ほとんどその操作を1文字のコマンドで行うので, AtCoder でゴルフをやるのに良さそう. というか kotatsugame さんが実際無双してる.

私も使えるようになりたい.

整数/少数に関する演算は普通のスタックマシン. 文字列が扱える. 文字列は文字列として表示する以外に, それ自体を dc のコマンド(のマクロ)として使うことが出来, マクロ実行に関するコマンドも用意されてる. 例えば条件分岐して実行するとか. つまり if 文と同じことが使える.

よし一通り読んだ. いくつかは意味がわからなかったけれど.

AtCoder 過去問を dc で解いてく

最近の問題から順に, A/B 問題を中心に埋めてく. いきなりゴルフをできるわけもないので素直に解いてく.

ABC168/A

いきなり数一個を標準入力から読む方法が分からない. ? で一行読んで dc として実行をするらしい. プロコンだと入力はスペース区切りで数字が並んでるので, スタックに入力を積むという操作をひたすらしてくれる.

条件分岐をして, 3種類のいずれかを実行すればいい.

[[hon]pq]  # [hon] を `p`rint して `q`uit するというマクロ
sh         # これを `h` に `s`tore する

[[bon]pq]  # 同様
sb

[[pon]pq]  # 同様
sp

?          # 入力 (数が一つスタックされる)
10%        # 10 で割った剰余を取る

d          # `d`uplicate
3=b        # それが 3 と等しかったら `b` を実行
           # `=` はスタックから取り出して剰余が消えてしまうので,
           # duplicate しておく必要があった

# if 0= or 1= or 6= or 8=
d0=p
d1=p
d6=p
d8=p

# else
lh         # `l`oad `h`
x          # e`x`ecute

最後の else は, 各マクロを全部 q で quit してるからそれ以降は実行されないことを利用している. のだが, これを動かすと期待通りの出力をした後に Exit code 1 で終了し, AtCoder では RuntimeError となる. なぜだろう. わからないが, マクロの最後の q をやめると解決した. このために else のようなことが出来なくなり, いくつか修正して

[[hon]n]
sh
[[bon]n]
sb
[[pon]n]
sp
?
10%
d3=b
d0=p
d1=p
d6=p
d8=p
d2=h
d4=h
d5=h
d7=h
d9=h

これで通った. q を消した以外に, 文字列の出力に n を使っている. しかし qexit 1 するのはなんで???

ABC168/B

文字列の処理...? 分からないし他に提出してる人もいない. パス

ABC169/A

パス

ABC169/B

答えを先にいうと, \(\min(A,K) - \max(K-A-B,0)\).

min や max は < による条件分岐で実現できるが, else 相当をぱっと書けなくて then 節だけでどうこうするようになってるので, \(\min(A,K)\)

let mut a = A;
if A > K {
    a = K;
}

ってやる.

?
sk
sc
sb
sa

lklalalk
# Stack = K A A K
[r]sr
<r
# if A < K:
#   Stack = A K
# else:
#   Stack = K A
lkla-lb-
sd
# Reg[d] = (K-A-B)
ld 0
# Stack = _ _ (K-A-B) 0

[ld-]
sr
<r
# if (K-A-B) < 0:
#   _ _
# else
#   _ (_ - (K-A-B))
p

コメントを省いて不要な改行空白を除くと

?skscsbsalklalalk[r]sr<rlkla-lb-sdld0[ld-]sr<rp

で 48 byte. ちなみに現在の dc での最短は 23 byte abc167/submissions/13161505. レベルが違う. 無駄なロード/ストアをしないで, できるだけスタック上だけで操作してそう. < が2つ登場してるので2回大小比較してるのは同じ?

ABC166/A

入力は文字列 "ABC" または "ARC". これを ? で受け取ってみると,

ABC
f
1122

c

ARC
f
12

この動作を完全に説明することは出来ないが, どうやら dc は強引に 16 進数として読める部分だけを読んでくれるらしい. 例えば "F" は 15 を表す. というわけで入力を受け取って "F" との大小比較をすることで所望の条件分岐が出来そう.

[[ABC]n]sb
[[ARC]n]sr
?d
F<r  # if "F" < input() then "ABC"
F>b  # if "F" > input() then "ARC"

dc で一位の人の 14 byte コード. https://atcoder.jp/contests/abc166/submissions/12790872

整数を print すると ascii コードとして見てやってくれるらしい. "ABC" も "ARC" も真ん中の一文字が違うだけなので, 条件分岐を作らずに上手く出力させてる.