はむ吉（のんびり）の練習ノート

プログラミングとことばに関する話題を中心に，思いついたこと，試してみたこと，学んだことを，覚え書きを兼ねてまとめます．その際に役立った，技術書，参考書，辞書，機器などの紹介も行います．

Chokudai Contest 001に参加した：はじめてのマラソン系コンテスト

AtCoder 競技プログラミング プログラミング

先ほどまで、AtCoderのChokudai Contest 001にオンラインで参加していました。このコンテストは、普段AtCoderでよく開催されているものとは異なり、いわゆるマラソン系のコンテストでした。私はこれまでマラソン系コンテストに出たことがなかったのですが、試しに参加してみました。

マラソン系コンテストとは

マラソン系コンテストでは、長い制限時間の中で、出された問題に対して、なるべくよい解を与えるコードを作成することが目標となります。代表例としては、TopCoderのMarathonMatchが挙げられます。通常のコンテストとは異なり、このようなコンテストでは、必ずしも最適解を提出する必要はありません。出した解が最適解に近いほど、得られる点数は高くなります。

Chokudai Contest 001に参加するまで

先述のように、私はマラソン系コンテストに参加したことがありませんでした。また、このようなコンテストでよく用いられる技法についても、あまりよく知りませんでした。それゆえ、今回のコンテストに参加して、私は果たして正の点数が取れるのだろうかと思っていました。しかし、物は試しということで、とりあえず参加してみることにしました。

Chokudai Contest 001で提出したコードとその考え方

今回のコンテストでは、問題が1つだけ出されました（
A: 高橋君の山崩しゲーム - Chokudai Contest 001 | AtCoder
）。コードの実行時間に対する制限が長め（10秒）であったため、Python 3を使用しました。以下では、この問題に対して私が提出したコード（一覧）と、それを作成したときの方針について述べます。

f:id:hamukichi_nbr:20160320231441p:plain

第1の提出：自明な解答

最初のコード（541032点）は、各マスに対して、0になるまで操作を繰り返すという単純な方針で作成しました。この段階では、隣接するマスは考慮しませんでした。すなわち、操作のステップ3は無視しました。極端なテストケース（例：すべてのマスに100が書かれている）がなかったため、この解答でも54万点あまりが得られました。なお、最近AtCoderではNumPyやSciPyなどのライブラリを利用できるようになったので、この解答では試しにNumPyの配列を使いました。

第2・第3の提出：隣のマスを見てみる

ここからは、ステップ3を考慮しました。その結果として、わずかながら得点が増えました。

2番目のコード（541359点）は、各マスの数値を1減らした後で、その一つ隣のマスがステップ3の条件を満たせばその数値も1減らし、最後に上記の自明な方法によるという方針で書いたものです。この修正により、点数が約300点増えました。

続く3番目のコード（541371点）は、上の方法で一つ隣のマスだけではなく、条件を満たす限りその隣、その隣、……も見るようにしたものです。ただし、コードに表れているように、まじめな探索はしませんでした。この改良により、点数が約10点だけ増えました。

第4～第6の提出：擬似乱数に頼る

これらのコードは、擬似乱数を使ってマスを見ていく順番をいろいろと変えるという方針で作成したものです。4番目のコード（541371点）では、隣接するマス（上下左右）を見る順番をシャッフルしましたが、ほとんど効果がありませんでした。そこで、5番目のコード（541437点）では最初にマスを見ていく順番をシャッフルしたところ、数十点だけ上がりました。そこで、6番目（542005点）ではこのシャッフルを15回行い、最も手数が少なくなる答えを出力するようにしたところ、さらに500点ほど点数が増えました。少しずつではあるものの点数が増えていき、だんだん楽しくなってきました。

第7の提出：行き詰まり

7番目の解答（541425点）では、調子に乗ってシャッフルの回数を15回から20回に増やしましたが、計算量が増えただけで、得点は下がってしまいました。そこで、発想の根本的な転換が必要であると感じました。とはいえ、なかなかよさそうな方法を思いつかなかったのです。やがて半ばあきらめて、ほかの作業に移ってしまいました。

第8・第9の提出：深さ優先探索の利用

コンテスト終了間際になって、よさそうな方法を思いつきました。それは、深さ優先探索と経路復元により、数値が1ずつ減っていくマスの列たちを見つけ、これらのそれぞれに対して一連の操作を行うことを繰り返すというものでした。深さ優先探索は何度か使ったことがあったものの、経路復元を行った経験はまったくありませんでした。しかし、たとえ間に合わなくても、とりあえず自分なりにコードを書いてみることにしました。焦りもあり、なんだかぐちゃぐちゃなコードになりましたが、なんとか終了約2分前に8番目の答案（560962点）を出すことができました。なお、反復回数を増やしてもう一度提出しました（9番目、560962点）が、得点は変わりませんでした*1。

感想

初めてのマラソン系コンテストでしたが、楽しむことができました。改良したコードを提出していくたびに点数が上がっていったときには、着実に前進しているという感覚を得られました。また、いったん行き詰まったものの、終盤になってよりよい解法を導けたのは、喜ばしいことでした。最後まで根気よく問題に取り組むことの重要性を改めて認識しました。今後同じようなコンテストが開催されるならば、ぜひ参加したいものです。お疲れさまでした。

参考にしたページ

*1:「前の提出から5分以上開けての提出をお願いします」と書かれていたにもかかわらず、8回目の提出から2分も経たないうちに9回目の提出を行ってしまいました。申し訳ありません。