dcゴルフの備忘録

2020-04-20 備忘録コードゴルフ dc Comments Word Count: 2679words Read Count: 6minutes

はじめに

man dcを個人的にまとめたもの. (間違ってるかも)

基本的にAtCoderのdc環境(v1.4.1)で検証をしています. 便宜上, スタックのtopから順に, $s_1, s_2, \ldots$と定義します.

?で1行入力を受け取る. 入力された内容をマクロとして実行する.

例) 4 2 9を入力 → 4をスタックにpush → 2をスタックにpush → 9をスタックにpush

コマンド	処理	改行
`p`	$s_1$を出力	あり
`n`	$s_1$を出力してpop	なし
`P`	$s_1$を文字列として出力してpop (数値なら256進数にしてASCIIコードに変換)	なし
`f`	スタック全体を出力 (上がtop)	あり

整数・小数をスタックにpushしたいときは単にその数値を書く.

複数の値を連続してpushしたいときは各数値の間に空白を開ける.
- 17 9.2 : $17$と$9.2$をpush
- 一部コマンドで代替することで空白を省けるケースもある.
  - K : 0
  - O : 10
負数を表すマイナスは_を用いる.
- _28 : -28をpush
$0,1,\ldots,9,A(10),B(11),\ldots,F(15)$を, $i$進数($i$は入力基数)の各桁の値として用いる.
- 429 : $4 \cdot i^2 + 2 \cdot i^1 + 9 \cdot i^0$
- 23.7 : $2 \cdot i^1 + 3 \cdot i^0 + 7 \cdot i^{-1}$
- _B7E : $-(11 \cdot i^2 + 7 \cdot i^1 + 14 \cdot i^0)$
- BE.D : $11 \cdot i^1 + 14 \cdot i^0 + 13 \cdot i^{-1}$
- yukicoderのdc環境(v1.3.95)では挙動が一部異なる
  - 1桁の場合は同じように$0,1,\ldots,15$を表す.
  - 2桁以上(小数点以下も含む)の場合は, $i$以上の桁は$i - 1$に抑えられる. ($i$進数の各桁は本来$0$から$i - 1$であるべきなので)
    - _A7E : $-(9 \cdot 10^2 + 7 \cdot 10^1 + 9 \cdot 10^0)$ ($i = 10$のとき)

演算に使用した値は(基本的に)popされる. 精度は一部例外を除いて被演算子で定まる.

コマンド	処理	注意
`+`	$s_2 + s_1$を積む	-
`-`	$s_2 - s_1$を積む	-
`*`	$s_2 \times s_1$を積む	-
`/`	$s_2 \div s_1$を積む	$s_1=0$なら何も起こらない(popもされない). 精度は精度値で指定される.
`%`	$s_2 \ \mathrm{mod}\ s_1$を積む	$s_1=0$なら何も起こらない(popもされない).
`~`	$s_2 \div s_1$と$s_2 \ \mathrm{mod}\ s_1$をこの順に積む	$s_1=0$なら何も起こらない(popもされない). 精度は精度値で指定される.
`^`	$s_2 ^ {s_1}$を積む	$s_1$の小数点以下は無視される.
`\|`	${s_3 ^ {s_2}} \ \mathrm{mod}\ s_1$を積む	$s_1=0$なら何も起こらない(popもされない). 整数を渡す.
`v`	$\sqrt{s_1}$を積む	$s_1<0$ならpopのみ行われる.

コマンド	処理
`c`	スタックを空にする
`d`	$s_1$を積む
`r`	$s_1$と$s_2$をswapする
`R`	$s_1$をpopして, スタックの上部$\lvert s_1 \rvert$個をrotateする. $\cdot\ s_1$が正なら, 元の$s_2$が$s_3$に動く方向へ. $\cdot\ s_1$が負なら, 元の$s_3$が$s_2$に動く方向へ.

操作するレジスタ名を$(reg)$として表す. レジスタ名は1文字で指定する.

各レジスタはそれ自身のスタックを持っている.

単に表示する, もしくはマクロ(dcの命令列)として実行することができる.

操作するレジスタ名を$(reg)$として表す.

コマンド	処理
`[hoge]`	文字列`hoge`をスタックに積む.
`a`	$s_1$をpopし, 数値なら$s_1 \ \mathrm{mod}\ 256$をASCIIコードとして文字列にしたものを, 文字列ならその最初の文字をスタックに積む.
`x`	$s_1$をpopし, マクロとして実行する.
`>`$(reg)$	$s_1 > s_2$なら, $(reg)$の内容をマクロとして実行する.
`!>`$(reg)$	$s_1 \leq s_2$なら, $(reg)$の内容をマクロとして実行する.
`<`$(reg)$	$s_1 < s_2$なら, $(reg)$の内容をマクロとして実行する.
`!<`$(reg)$	$s_1 \geq s_2$なら, $(reg)$の内容をマクロとして実行する.
`=`$(reg)$	$s_1 = s_2$なら, $(reg)$の内容をマクロとして実行する.
`!=`$(reg)$	$s_1 \neq s_2$なら, $(reg)$の内容をマクロとして実行する.
`q`	実行中のマクロと, それを呼び出したマクロを終了する. `q`を含むマクロが最上層で行われた場合はexitする.
`Q`	$s_1$をpopし, その回数だけマクロから抜ける. 最上層に到達してもexitしない.

コマンド	処理
`Z`	$s_1$をpopし, それが文字列ならその長さを, そうでないならその桁数をスタックに積む.
`X`	$s_1$をpopし, それが文字列なら$0$を, そうでないならその精度をスタックに積む.
`z`	現在のスタックのサイズをスタックに積む.
`!`$(command)$	$(command)$をシステムコマンドとして実行する.
`#`	続く文字列はコメントとして処理される.
`:`$(arr)$	$s_1, s_2$をpopし, 配列$(arr)$の$s_1$番目に$s_2$を保存する.
`;`$(arr)$	$s_1$をpopし, 配列$(arr)$の$s_1$番目の値をスタックに積む.

k,iで疑似pop
- 精度と(入力後の)入力基数は変えても問題ないことが多いので.
Xでtopを0に
- topが整数であり不要ならXで0にできる. (その後は+して消すなり, ループで適当に処理するなり.)
[neg] [pos] [x]でvrp
- $x < 0$なら[neg], そうでないなら[pos]を出力.
- vに負値を渡すとpopのみ行われることを利用.
単に$10$をpushしたいときはO,Iを使う
- これを利用してO9^7+で$10^9+7$が表せる.
  - O9 : Oは桁じゃないので, $10$と$9$のように独立の数としてパースされる
  - A9 : Aは桁なので, $10 \cdot 10 + 9 = 109$としてパースされる
sで上書きしていないレジスタにアクセスすると, スタックに$0$が積まれる.
- 「ある条件を満たしたら$0$を積む」みたいなのを短く書ける.
  - 例. ABC164A - Sheep and Wolves
Pで$0$や$10$を(実質)空文字扱いできる
- $0$ : ヌル文字
- $10$ : 改行文字