TopCoder Marathon Match 123

　参加していました。

コンテストへのリンク

コンテスト後のツイート

　前回のMarathon Match 122も参加したのですが、実装終わると思ったものが書き終わらず、時間ギリギリで出したコードがバグあり＆エラー出力消し忘れ（のため大きいサイズだとTLEする）がひどく、レートを大きく落としてしまいました……。

　それがショックだったので、今回は初日からちゃんと参加。とはいえ、初提出が終了日前日と、余裕はあまりありませんでしたが。

　ルールは、盤面のどこでも二点をSwapできるマッチ3ゲームで、1000ターンでどれだけ点数を出せるか（点数のルールは説明省略）。

　ビジュアライズが宝石になっていたので、「コラムス」か？　と思いましたが、あれは斜めも消せました。

やったこと

　Xターン後、スコアを最大化できるようなSwapを探索……とかだと計算時間が間に合わなそう（特にPythonだと）なので、その方針はあまり考えず、適切なパターンを作って、それに当て嵌める方針でいきました。

　ツイッター等で他の人の解法を見る限り、その方針は正しかったよう。

　ただ、そのパターンへの組み換えへの実装には結構苦労しました。

　一連鎖目から色が揃っているかを見ていき、揃っていなければ、後の連鎖のやつの中で、その色を持っているやつからもらう……みたいな方針です。

　どの色で組むかは、その数個の中で最も多い個数のやつを採用するようにしました。

　パターンについて。

　点数計算を見ると、長い連鎖を組むのが良いですが、長いサイズの消しも一回くらいはあると良さそう、ということで、二連鎖目に横長の消しをするようにしています。暴発の防ぎ方が分からず、長い連鎖が組めなそう……と分かってからはそこを重視しました。

　ただ、横16マス消しも可能だということが分かったのが最終日夜だったのは痛かった。もっと前に気付いていれば、パターン作成を詰められたかもしれません。

　自分のパターンは、二連鎖目に長いサイズ（最大N-1個）を一番下の段で消して、そこから3個ずつ、前の連鎖に一個か二個重なるように置いて、連鎖を続けていくというもの。そのどれを選ぶか、というのを目で見て決めました。ただ、適当に置くと（連鎖ごとの色が全て異なっていても）連鎖中に暴発してしまうことがあるので、そこはプログラムでチェックしています。

　そうやって作ったパターンの中で、実際に実行したとき点数が良さそうなものを採用しました。

反省点

　点数が伸びなかった原因ははっきりしていて、パターン構築が甘かった、これにつきます。もちろん、パターンへの組み替え方の実装なども良くないのですが、一番の原因はそこ。

　一番下の段ではなく、盤面の中程で横長の消しを行い（それも、N-1個ではなく、N個を数段同時にやってもいい）、そこから下に向かって連鎖を繋げていくような方針なら、もっと安全に長い連鎖を組めた模様。

　パズル部分で考察が及んでいなかった、というのは残念。

　パターン次第ではもっと点数が伸びるはず、とはずっと思っていたのに、そこを詰められなかったのは良くないですね。

　実装力（や言語選択）のせいで負けた、と言えるような成績を取りたい。今回の自分の方針だと、他の言語に書き換えたとしてもほぼ点数は伸びません（一応、最後着火する前に、一手で連鎖が増やせるSwapがあるか調べる探索を入れているので、その部分は伸ばせるかもしれませんが、誤差の範囲でしょう）。

　マラソン系のコンテストでは、大体いつも、考察パズル部分ではっきり負けていた……とコンテスト後に分からされているので、もっとここに力を注ぐべきですね。