こんにちは！スタッフエンジニアの kenkoooo です。lemondo さんと pes さんと「第二回マスターズ選手権」というチーム戦形式のプログラミングコンテストの決勝に参加してきました。
注意！
以下には問題のネタバレが含まれます。予選も決勝も面白い問題ですので、問題を解きたい方は解いた後また来てください。
予選
pes さんが汎用焼きなまし解法、lemondo さんが木を作ってrootに近いものから穴に入れる解法、kenkoooo がビジュアライザと岩を避けまくる解法をやりました。
中盤で pes さんの焼きなまし解法がABC各問題で得点を上げるようになり、予選通過の上位50チームにギリギリ入れるか…？という感じだったのですが、終盤で lemondo さんの解法が障害物のあるケース（AとC）で高得点を出して大幅に浮上し、予選23位で通過しました。
決勝
決勝戦は、同じ問題設定に対して
- A: プレイヤー1人で障害物あり
- B: プレイヤー2人で障害物なし
- C: プレイヤー2人で障害物あり、ただし、テストケースは決勝参加者が作る
という3つの問題が出題されました。参加者同士で問題を出し合うという、決勝でしかできなそうな問題で非常に面白かったです。
我々のチームでは以下のような方針で取り組みました。
- 各点をクラスタに分けて bounding box を作り、それらを巡回セールスマン問題 (TSP) として解く
- bounding box 内では対角線方向に移動する
- C問題のテストケースは、上記の解法が苦手とする複数種類の点が螺旋状に並ぶ配置にする
- 自分たちの解法は TSP 解法とルールベース解法を両方走らせる
A問題の様子 
B問題の様子 
C問題でルールベース解法が1手で仕留めている様子 
決勝最終スコア
- 自分たちの解法は TSP 解法とルールベース解法を両方走らせる
僕のミスでテストケース提出が間に合わないなどのトラブルもありました（反省しています）が、最後まで暇にならずに楽しめました。B問題で天才解法（いわゆるスキャン解法）に気づかず、最終順位は36位でした。懇親会でB問題の解法を聞いた時は膝から崩れ落ちました。
振り返って
僕自身はヒューリスティックコンテストは全然強くなく、lemondo さんと pes さんにキャリーしてもらった形ですが、決勝に参加し、日本一を争う人たちの才能を間近で感じることができて良かったです。
最後に
estie では競技プログラミングのレートを採用基準にしているわけではありませんが、競技プログラミングをやっている人がまあまあいます。もしご興味あればぜひ！
