BitcoinのスクリプトでAtCoderの問題を解いてみた

本日（2018年6月2日）、競技プログラミングコンテスト[codeFlyer](https://bitflyer.com/ja-jp/recruit/codeflyer201806)が開催される。仮想通貨取引所を運営するbitFlyerの主催なので、きっと、使用可能な言語はBitcoinの取引に使用されている[スクリプト](https://en.bitcoin.it/wiki/Script)だけだろう。ということで練習をした。

現在のAtCoderで使用可能な言語にBitcoinのスクリプトが無いので、Pythonのインタプリタを実装した。`Input:`に書かれた形式で標準入力から入力を読み取ってスタックに積み、`Code:`のスクリプトを実装して、`Output:`の形式で標準出力に書き出す。

https://github.com/kusano/pybitcoinscript/blob/master/pybitcoinscript.py

[AtCoder Beginners Selection](https://beta.atcoder.jp/contests/abs)に挑戦した。初心者向けの簡単な問題が揃っている。

# はじめてのあっとこーだー（Welcome to AtCoder）

https://beta.atcoder.jp/contests/abs/tasks/practice_1

`s`には手を付けず、`a+b+c`を実行すれば良い。

```
Input: int int int str
Output: int str
Code:
  OP_ADD
  OP_ADD
```

https://beta.atcoder.jp/contests/abs/submissions/2595495

# Product

https://beta.atcoder.jp/contests/abs/tasks/abc086_a

問題文の通りに実装するだけ。

```
Input: int int
Output: str
Code:
  OP_MUL
  2
  OP_SWAP
  OP_MOD
  OP_IF
    Odd
  OP_ELSE
    Even
  OP_ENDIF
```

https://beta.atcoder.jp/contests/abs/submissions/2595497

# Placing Marbles

https://beta.atcoder.jp/contests/abs/tasks/abc081_a

問題文ではs<sub>1</sub>, s<sub>2</sub>, s<sub>3</sub>は文字のようだが、まとめて整数として読みこむことにした。整数`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
```

https://beta.atcoder.jp/contests/abs/submissions/2595501

# Otoshidama

https://beta.atcoder.jp/contests/abs/tasks/abc085_c

これがなかなか難しかった。

以降では、`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`なら可能なのだろうかとか考えたところ、次のような処理で答えが得られることがわかった。

```py
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
```

スタックの様子を加えると次のようになる。左側がスタックの先頭。

```py
# 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
```

https://beta.atcoder.jp/contests/abs/submissions/2595504

# その他の問題

Bitcoinのスクリプトではループが書けないので、その他の問題は厳しい。入力のサイズに上限があるので、大量のコードを並べるということで解けなくはないかもしれないが……。[Coins](https://beta.atcoder.jp/contests/abs/tasks/abc087_b)はループを使わずに解く方法があるかもしれない。誰か解いてほしい。

# 参考

[Atcoder Beginners Selectionを難解言語Pietで解いてみた \- ベースメモ](http://basemusi.hatenablog.com/entry/2018/03/21/195500)