問題
スペシャルジャッジに対応していない様子なのでジャッジ解提出する以外AC取れない気がする。
先に5888をやるべき。パズル系の問題。
Stack Machineというプログラミング言語が定義されている。
入力V[i]と出力R[i]のペアがN個与えられている。
入力はプログラムの初期状態として、スタックに一つ積まれている値である。
Stack Machineのプログラムを作成せよ。
そのプログラムはどのV[i]についても対応するR[i]を最後のスタックの状態として終了するものでなければならない。各V[i]は異なる。
解法
何かしらの多項式を求めるのかと思ったが誤り。
プログラムにV[i]とR[i]のペアを埋め込み、初期スタックの値に一致するものだけR[i]が生き残り、それ以外は0にする条件分岐のような振る舞いをするプログラムを作る。
2数を取り出し同じ値なら1、異なるなら0をスタックに詰む操作を作る。
これができると初期値とV[i]が一致するか調べ、0か1が積まれ、R[i]を掛けることで目的のプログラムが完成する。
aとbが一致するかどうかはa-bが0か否かで判定する。更に言うとa-bが負になると不便なので(a-b)(a-b)が0か否か判定する。
(a-b)(a-b)は簡単にできるのでスタックのトップが0か判定する。
xの0判定はxを2進数に分解してスタックに積み、全ての論理和を取り、最後にその論理否定を取れば良い。
(a-b)(a-b)は100以下なのでせいぜい6ビット求めれば良い。
xからx mod 2とx div 2の2数をスタックに詰む操作を5回行う。
すると長さ6の01列ができる。
a,bの論理和がやや難しい。演算で書くと、
a or b := a+b-ab
となる。
書き下すと
[a][b] NUM 1 [a][b][1] SUB [a][b-1] SWP [b-1][a] NUM 1 [b-1][a][1] SUB [b-1][a-1] MUL [ab-a-b+1] NUM 1 [ab-a-b+1][1] SWP [1][ab-a-b+1] SUB [a+b-ab]
論理否定は1から減算するだけ。
5888を解いておくと、手元で正しいか確認することができる。
