AtCoder Beginner Contest 188

　Fが解けずに終了。これは反省しないと。

コンテストへのリンク
コンテスト後のツイート

F - +1-1x2

　AGCで類題が出題されていた。

　このときのAGCは一問も解けず終わってしまったため非常に悔しく、印象に残っていた。

　そのため、Fを見たとき、まずこの問題を思い出した。

　……が、スタートの数Xが定まっていないと上手くいかない気がして捨ててしまった。

　実際は同じ方法で上手くいく。解法をきちんと理解していれば分かったはずなので、反省。

　その後、「2倍する回数を決め打つ」という方針を思い付く。が、1WAが取れずに終わった。

　これも方針が悪かったわけではなく、koboshiさんの解説や、fairy_lettuceさんの解説のように、正しく実装すれば通る方針だった。

　自分のコード内で、「$1, 2, \dots , 2^a$及び、$-1, -2, \dots , -2^a$を使って、xが作れるか」というのをpartition(a, x)と書き、メモ化再帰で調べようとしている。このとき、負の数も使えるというのが重要で、たとえば、「$1, 2, 4, 8$で$7$が作れるか？」だったら、「4+2+1」ではなく、「8-1」とできることに注意しなくてはいけない。

　このpartition(4, 7)という例だと、上の桁から見ていった場合、

・partition(3,7)

（1, 2, 4で7が作れるか？）

・1+partition(3, 7-8) = 1+partition(3, 1)

（1, 2, 4で-1を作れるか？　正負は共に使えるので、1, 2, 4で1を作れるか？　と同じ。）

の二通りを考えれば良い。

　その辺り、一応分かっていたはずなのに、一番上の桁でのみ負のを考慮するようにしてしまっていた。上の桁から順に見ていったのだが、最初だけマイナスを考慮すれば良いと勘違いし、そこから抜け出せなかった。

　各桁の使い方はプラスとマイナスで二通りあるのだから、プラスとマイナスの両方を考慮するのは自然ですね。小手先の変更で通そうとせず、落ち着いて考えればこの方法でも通せたはず。

　これも反省。