Yukicoder No.2256 Step by Stepの別解
yukicoder.me
この問題の考察過程と別解を書きます。
まず、高さ6であることから、縦棒2本が同じ場所にあるのは(N=1を除いて)禁止です。
これがただの壁になっちゃって、起動にも終了にも貢献しないからですね。
また、この考察から、最初の連鎖は端から始まって端で終わる方が良いだろうという気持ちにもなります。
そこで、サンプル1を眺めると、かなり良さそうな形をしていることが分かります。
012 345 345 225 141 300
これをちょっと形を変更することで、次のようなものを作ります。
134 02a 02a 011 323 44z
これは、0→1→2→3と連鎖し、aaを2マス降ろした後、何らかの方法でa及びzが全部消えると444が消えて終了します。
この後ろに、aaが2マス落ちると連鎖が始まり、最後にzが消えるパーツを置くと良さそうに思えます。
そのようなパーツが大きいと嬉しくないので幅2くらいで作れないか考えると、次のようなパーツが作れることが分かります。
23 01a 21a 00 12 33z
このパーツは前のパーツのaaが全て消えると0→1→2と消え、zが消えると3が連鎖して前のパーツのzが消えます。
これ自体も同じaaとzの構造を持っているので、このパーツはいくらでも繋げることができます。
最後に終端ですが、よく見るとa=zの時に丁度自動で繋がる形をしているので、そのようにすることで答えを求めることができました。
これで、 の場合は全て解けています。
従って後は最初が4マスのパーツを作れればよく、これはサンプル2を変形すると次のようなものが作れます。
3665 244a 211a 1000 2334 655z
コーナーケースで があるので気を付けてください (明らかに作れます)。
実装はこちら
yukicoder.me