本日（2018年6月2日）、競技プログラミングコンテストcodeFlyerが開催される。仮想通貨取引所を運営するbitFlyerの主催なので、きっと、使用可能な言語はBitcoinの取引に使用されているスクリプトだけだろう。ということで練習をした。
現在のAtCoderで使用可能な言語にBitcoinのスクリプトが無いので、Pythonのインタプリタを実装した。Input:に書かれた形式で標準入力から入力を読み取ってスタックに積み、Code:のスクリプトを実装して、Output:の形式で標準出力に書き出す。
AtCoder Beginners Selectionに挑戦した。初心者向けの簡単な問題が揃っている。
はじめてのあっとこーだー（Welcome to AtCoder）
sには手を付けず、a+b+cを実行すれば良い。
Input: int int int str
Output: int str
Code:
OP_ADD
OP_ADD
Product
問題文の通りに実装するだけ。
Input: int int
Output: str
Code:
OP_MUL
2
OP_SWAP
OP_MOD
OP_IF
Odd
OP_ELSE
Even
OP_ENDIF
Placing Marbles
問題文ではs1, s2, s3は文字のようだが、まとめて整数として読みこむことにした。整数sとして読みこんでしまえば、答えはs%10+s/10%10+s/10/10となる。入力が8通りしかないので、単純に比較するという手もある。
Input: int
Output: int
Code:
OP_DUP
10
OP_SWAP
OP_MOD
OP_SWAP
10
OP_SWAP
OP_DIV
OP_DUP
10
OP_SWAP
OP_MOD
OP_SWAP
10
OP_SWAP
OP_DIV
OP_ADD
OP_ADD
Otoshidama
これがなかなか難しかった。
以降では、Yを最初に1,000で割ってしまい、10円札と5円札、1円札の枚数を考える。
o...............................................................................
.o...o....o.....................................................................
..o...o...oo...o....o...........................................................
...o...o...oo..oo...oo...o....o.................................................
....o...o...oo..oo..ooo..oo...oo...o....o.......................................
.....o...o...oo..oo..ooo.ooo..ooo..oo...oo...o....o.............................
......o...o...oo..oo..ooo.ooo.oooo.ooo..ooo..oo...oo...o....o...................
.......o...o...oo..oo..ooo.ooo.oooooooo.oooo.ooo..ooo..oo...oo...o....o.........
........o...o...oo..oo..ooo.ooo.ooooooooooooooooo.oooo.ooo..ooo..oo...oo...o....
.........o...o...oo..oo..ooo.ooo.oooooooooooooooooooooooooo.oooo.ooo..ooo..oo...
..........o...o...oo..oo..ooo.ooo.ooooooooooooooooooooooooooooooooooo.oooo.ooo..
...........o...o...oo..oo..ooo.ooo.oooooooooooooooooooooooooooooooooooooooooooo.
こんな感じで、どのNとYなら可能なのだろうかとか考えたところ、次のような処理で答えが得られることがわかった。
N,Y = map(int, raw_input().split())
Y /= 1000
x = (Y-N)/9-[0,3,2,1,0,3,2,1,0][(Y-N)%9]
y = [0,7,5,3,1,8,6,4,2][(Y-N)%9]
z = N-x-y
if x>= 0 and z>=0:
print x, y, z
else:
print -1, -1, -1
全てを1円札で支払うと、Y枚になる。鶴亀算の要領で5円札や10円札に変えると、それぞれ4枚や9枚紙幣の枚数が減る。すなわち、「xとyを自然数（0は自然数）として、4x+9y=Y-Nを満たせますか？」という問題になる。可能な金額を減らさないようにしつつ、yを最小にすることを考えると、yは9周期で0, 7, 5, 3, 1, 8, 6, 4, 2, …となる。という感じだろうか。これをBitcoinのスクリプトで実装すると、
Input: int int
Output: int int int
Code:
1000 OP_ROT OP_DIV
OP_2DUP OP_SUB
9 OP_OVER OP_MOD
OP_DUP 0 OP_NUMEQUAL OP_IF 0 OP_ELSE
OP_DUP 1 OP_NUMEQUAL OP_IF 7 OP_ELSE
OP_DUP 2 OP_NUMEQUAL OP_IF 5 OP_ELSE
OP_DUP 3 OP_NUMEQUAL OP_IF 3 OP_ELSE
OP_DUP 4 OP_NUMEQUAL OP_IF 1 OP_ELSE
OP_DUP 5 OP_NUMEQUAL OP_IF 8 OP_ELSE
OP_DUP 6 OP_NUMEQUAL OP_IF 6 OP_ELSE
OP_DUP 7 OP_NUMEQUAL OP_IF 4 OP_ELSE
OP_DUP 8 OP_NUMEQUAL OP_IF 2 OP_ELSE
OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF
OP_OVER 0 OP_NUMEQUAL OP_IF 0 OP_ELSE
OP_OVER 1 OP_NUMEQUAL OP_IF 3 OP_ELSE
OP_OVER 2 OP_NUMEQUAL OP_IF 2 OP_ELSE
OP_OVER 3 OP_NUMEQUAL OP_IF 1 OP_ELSE
OP_OVER 4 OP_NUMEQUAL OP_IF 0 OP_ELSE
OP_OVER 5 OP_NUMEQUAL OP_IF 3 OP_ELSE
OP_OVER 6 OP_NUMEQUAL OP_IF 2 OP_ELSE
OP_OVER 7 OP_NUMEQUAL OP_IF 1 OP_ELSE
OP_OVER 8 OP_NUMEQUAL OP_IF 0 OP_ELSE
OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF
OP_2SWAP OP_DROP
9 OP_SWAP OP_DIV OP_SUB
OP_DUP OP_DUP OP_ABS OP_NUMEQUAL
OP_IF
OP_2OVER OP_DROP
OP_3DUP OP_SUB OP_SUB
OP_DUP OP_DUP OP_ABS OP_NUMEQUAL
OP_IF
OP_2SWAP
OP_ELSE
-1 -1 -1
OP_ENDIF
OP_ELSE
-1 -1 -1
OP_ENDIF
スタックの様子を加えると次のようになる。左側がスタックの先頭。
# N Y
1000 OP_ROT OP_DIV
# Y/1000 N
OP_2DUP OP_SUB
# Y/1000-N Y/1000 N
9 OP_OVER OP_MOD
# (Y/1000-N)%9 Y/1000-N Y/1000 N
OP_DUP 0 OP_NUMEQUAL OP_IF 0 OP_ELSE
OP_DUP 1 OP_NUMEQUAL OP_IF 7 OP_ELSE
OP_DUP 2 OP_NUMEQUAL OP_IF 5 OP_ELSE
OP_DUP 3 OP_NUMEQUAL OP_IF 3 OP_ELSE
OP_DUP 4 OP_NUMEQUAL OP_IF 1 OP_ELSE
OP_DUP 5 OP_NUMEQUAL OP_IF 8 OP_ELSE
OP_DUP 6 OP_NUMEQUAL OP_IF 6 OP_ELSE
OP_DUP 7 OP_NUMEQUAL OP_IF 4 OP_ELSE
OP_DUP 8 OP_NUMEQUAL OP_IF 2 OP_ELSE
OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF
# y (Y/1000-N)%9 Y/1000-N Y/1000 N
OP_OVER 0 OP_NUMEQUAL OP_IF 0 OP_ELSE
OP_OVER 1 OP_NUMEQUAL OP_IF 3 OP_ELSE
OP_OVER 2 OP_NUMEQUAL OP_IF 2 OP_ELSE
OP_OVER 3 OP_NUMEQUAL OP_IF 1 OP_ELSE
OP_OVER 4 OP_NUMEQUAL OP_IF 0 OP_ELSE
OP_OVER 5 OP_NUMEQUAL OP_IF 3 OP_ELSE
OP_OVER 6 OP_NUMEQUAL OP_IF 2 OP_ELSE
OP_OVER 7 OP_NUMEQUAL OP_IF 1 OP_ELSE
OP_OVER 8 OP_NUMEQUAL OP_IF 0 OP_ELSE
OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF OP_ENDIF
# [0,3,2,1,0,3,2,1,0][(Y-N)%9] y (Y/1000-N)%9 Y/1000-N Y/1000 N
OP_2SWAP OP_DROP
# Y/1000-N [0,3,2,1,0,3,2,1,0][(Y-N)%9] y Y/1000 N
9 OP_SWAP OP_DIV OP_SUB
# x y Y/1000 N
OP_DUP OP_DUP OP_ABS OP_NUMEQUAL
# x>=0 x y Y/1000 N
OP_IF
OP_2OVER OP_DROP
# N x y Y/1000 N
OP_3DUP OP_SUB OP_SUB
# z N x y Y/1000 N
OP_DUP OP_DUP OP_ABS OP_NUMEQUAL
# z>=0 z N x y Y/1000 N
OP_IF
OP_2SWAP
# x y z N Y/1000 N
OP_ELSE
-1 -1 -1
OP_ENDIF
OP_ELSE
-1 -1 -1
OP_ENDIF
その他の問題
Bitcoinのスクリプトではループが書けないので、その他の問題は厳しい。入力のサイズに上限があるので、大量のコードを並べるということで解けなくはないかもしれないが……。Coinsはループを使わずに解く方法があるかもしれない。誰か解いてほしい。