dc はスタックマシンによる計算機を実現するコマンド. ほとんどその操作を1文字のコマンドで行うので, AtCoder でゴルフをやるのに良さそう. というか kotatsugame さんが実際無双してる.
私も使えるようになりたい.
整数/少数に関する演算は普通のスタックマシン. 文字列が扱える. 文字列は文字列として表示する以外に, それ自体を dc のコマンド(のマクロ)として使うことが出来, マクロ実行に関するコマンドも用意されてる. 例えば条件分岐して実行するとか. つまり if 文と同じことが使える.
よし一通り読んだ. いくつかは意味がわからなかったけれど.
最近の問題から順に, A/B 問題を中心に埋めてく. いきなりゴルフをできるわけもないので素直に解いてく.
いきなり数一個を標準入力から読む方法が分からない. ?
で一行読んで 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
を使っている. しかし q
で exit 1
するのはなんで???
文字列の処理...? 分からないし他に提出してる人もいない. パス
パス
答えを先にいうと, \(\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回大小比較してるのは同じ?
入力は文字列 "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" も真ん中の一文字が違うだけなので, 条件分岐を作らずに上手く出力させてる.