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

14944 ワード

Bitcoin 競技プログラミング AtCoder AtCoder テキストリンク

本日（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

問題文ではs₁, s₂, s₃は文字のようだが、まとめて整数として読みこむことにした。整数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はループを使わずに解く方法があるかもしれない。誰か解いてほしい。

参考

Atcoder Beginners Selectionを難解言語Pietで解いてみた - ベースメモ

Author And Source

この問題について(BitcoinのスクリプトでAtCoderの問題を解いてみた), 我々は、より多くの情報をここで見つけました https://qiita.com/kusano_k/items/f72ff637fdc96fdbc15d

著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。

Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .

10.メールを送る

オープンソースファームウェアダウンロードツール