マラソンマッチで気をつけるべきこと

今までHTTF、ハル研プロコン、AHC、などのマラソン型競技プログラミングコンテストに参加してきました。初参加から一年以上が経ったでしょうか。個人的には普段のアルゴと呼ばれる分野のコンテストよりマラソンの方が向いている(相対的な順位がよい)と感じており、比較的力を入れてきました。

本記事では、マラソンに取り組むときに考えていることを自分の振り返りも兼ねてまとめます。

短期型では制限時間以内に実装できる範囲の中で得点の期待値が高そうなものを選ぶことが重要になりますが、今回は長期型、2週間ほどのコンテストにおける戦略にフォーカスします。

有名問題との類似性

まず問題を読むわけですが、その問題が、有名問題と似ているか考えます。例えばハル研プロコンでは、経路最適化問題が出題されましたが、上位陣の解法をみると所謂TSPの知見が多く利用されています。AHC001では、長方形の詰め込み最適化を求められましたが、これも長方形詰め込み問題と呼ばれる情報科学で有名な問題と似ていることがわかります。もちろんそのままの形式で出ることはあり得ませんが、知見が活きる可能性が高いです。そもそも出題者側には情報科学のバックグラウンドがあることは容易に想像できるため、教科書的な有名問題をもじったようなものは出題されやすいと思います。某講演でも、コンテスト期間中に論文を読みながら勉強するという話が出ていましたが、そのくらい巨人の肩に乗ることは重要だということだと思います。私自身学生時代の専門は生物学で、知見が不足している部分はありますが、情報科学に対するアンテナも常に張っておくべきだと感じています。

最も簡単な解

次に、最も簡単な解を書きます。経路最適化問題なら、直線で結ぶだけ、長方形配置なら、正方形を置くだけなど、とにかく正の得点が得られそうなものを書きます。この点数から上げていきましょう。ここで最も意識すべきことは、コードの再利用性と、拡張性です。先日の技育祭でchokudaiさんがマラソン実装の実演をしていましたが、そこでも強調されていました。最も簡単な解を得るからと言って、コードを雑に書くとすぐに後悔します。例えば長方形の配置をするなら、端の2点を入れたらセットできるメソッドを作ったり、長方形を管理する構造体も持つべきでしょう。こうすることで、余計な思考リソースを取られないようになります。向き合っている問題の中で、最も基本的な構造は何か考え、それにアクセスする回数が多そうなら、なるべくアクセスしやすいように書くのがコツです。

テキトーに書くと、改善する気がなくなります。触りにくいと、触らなくなります。最後には、触りたくても触れなくなります。私も何度も失敗して学びました。綺麗に書くと、愛着が湧きます。改善したくなります。長期型マラソンで最も大切なのはやめないことです。PDCAを高速に回すことです。2週間付き合っていくコードなので、スタートから未来を見据えて書いていきましょう。

単純な貪欲

最も基本的な解が構成できたら、山登り法や焼きなまし法を考える前に、単純な貪欲を考えます。貪欲が最も重要だと言っても過言ではないです。貪欲が弱いなら、後述する山登り法や焼きなましがうまくいくとは考えにくいです。マラソンマッチは制限時間内に全てのパターンを列挙できない問題から良さそうな一部の状態を探し当てる宝探しなのですから、闇雲に探しても見つかるわけがありません。数え上げお姉さんの二の舞になります。ある程度よいと思われるところに降りてから、探し始めましょう。

ハル研プロコンならダイクストラ法で距離を算出したり、AHC001なら目標面積目一杯、ギリギリまで広げるアルゴリズムを考えます。これだけでも十分よさそうな解が得られていそうなことに気づくでしょう。ただ、決定的アルゴリズムでは探しきれていない状態がたくさんあります。そこで、山登り法の出番です。

山登り法

山登り法は、状態にランダムな変異を入れて良くなったらそちらに進む方法です。ランダムな変異の取り方も無限にあるので、考えます。考える前にテキトーなところで手を打ってとりあえず実装するのも手です。それをベンチマークにして改善していきましょう。よく、ここで選んだ解法に固執してマラソンマッチ戦略の局所最適解に落ちてしまう人がいますが(私のことです)、無限にアイデアを試しても怒られることはないわけですから、遠慮せず解を壊しましょう。間違ってもここでパラメータガチャに走ってはいけません。パラメータガチャをするのは最後でも間に合います。稀にパラメータガチャで結果がめちゃくちゃ変わることもあるので、ある程度試す価値はありますが、固執すると時間だけが過ぎていきます。気をつけましょう。

山登り法の問題点は、局所最適解に落ちやすいことです。別にそこまでよくないのに居心地がいいから穴から出てきてくれなくなります。もっといい世界があるのに。まるでマラソン開始2日目でパラメータガチャに走る私のようです。局所最適解に落ちているかどうか判断する方法としては、実行時間を長くして、さらに解が改善するかどうかを見るというのがあります。5秒では見つからないけど、500秒で見つかるよりよい解があるなら、局所最適解に落ちてる可能性があります。救ってあげるにはどうしたらいいでしょうか。私はよく、突然変異を大きくしています。解の一部を壊して、局所最適解から逃してあげましょう。山登りなので、いい状態が見つかればそちらに向かってくれます。どういう変異を追加するべきかは、ビジュアライザをよく観察して考えます。「ここで改善できそうなのにいつまでも動かない」と思ったら改善のチャンスです。

その他

焼きなましは、局所最適解に落ちにくくなります、たぶん。焼きなましでスコアを伸ばしたことがないので言及を避けます。

以上、反省会でした。 これはあくまで個人的なメモなので、間違っていると思われる記述があったら教えていただきたいです。長期型マラソンでの注意点を意識し、楽しいマラソンライフを！