【AHC043】事前計算で高速化した貪欲法で頑張って戦う
初めに
2025年2月14日(金)から2025年2月24日(月)まで開催されていた、RECRUIT 日本橋ハーフマラソン 2025冬（AtCoder Heuristic Contest 043）にて、事前計算を工夫して高速化しつつ貪欲法で探索することで、本番258位を取ることができました。
順位としてはまだまだというところですが、事前計算などの工夫ができたため、個人的には満足しています。以下、思考の過程を残します。
問題
制約の設定「homeとworkplaceはペアで考える」
問題を考えやすくするために、いくつか制約条件を導入することにしました。
今回はあれこれ考えた結果、以下の4つを設定し、その中で問題を解くことを考えました。
(1) 必ずhome/workplaceはペアで考える。
(2) 2本目以降の線路は、必ず既設の線路に接続する。
(3) home/workplaceから伸ばした線路は、必ず最寄りの線路または駅に接続する。
(4) home/workplaceの周囲2距離のうち、どこに駅を作るかは任意とする。
制約(3)について補足します。home/workplaceから線路を建設していく際には、このような「最寄りの線路に接続する」ToRailパターンと、
このような「最寄りの駅に接続する」ToStationパターンがあります。
特に収入が少ない序盤のうちは、STATION_COSTが重いため、ToStationを選んだ方が効率的です。しかし収入が豊富になる終盤は、多少のコストには目をつぶって最速で最寄りの線路にToRailでつなぐ方が良いことも出てくるため、これらはどちらも探索して最適な方を選ぶのが良いと考えました。
評価関数「元が取れるのが一番早い路線に投資する」
貪欲法で解くために必要な評価関数ですが、今回の問題設定を鑑みて、以下のように設定しました。
要するに、「投資として元が取れるまでのターン数」をそのままスコアとして、それを最小にする選択肢を選び続けるというものです。
この評価関数の良いところは、ターン制限から見て元が取れない場合、例えば建設が間に合わない場合や、建設自体はできても残りターン数での収入増加が建設コストに見合わない場合、などの排除が簡単であるというところです。
score >= T - 現在ターン となったときには、元が取れないので「建設しない方が良い」と判断できます。
計算の高速化 (建設ターン数と建設コスト額)
さて、上記の評価関数を、毎ターン、全home/workplaceペアに対して計算できれば、貪欲法が成立しますが、計算が間に合うでしょうか。
制約(3)のオプションでhome/workplaceそれぞれ2通りずつ、さらに、制約(4)のオプションでhome/workplaceそれぞれ13通りずつを評価する必要があるため、最悪、上記の評価関数を T × M × 2 × 2 × 13 × 13 回計算することになります。
今回の問題設定の T=800、M<=1500 という制約では、これを計算すると8億回のループになります。さすがにMが大きい場合は制約(4)を緩めて探索マス数を減らすにしても、数GHzのPC × 3秒の制限時間では、1ループ当たりの計算回数は100回程度が上限になります。
これでは、愚直にシミュレーションしていると計算が間に合いません。
例えば、上記の評価関数の項目のうち、「建設ターン数」と「建設コスト額」は、ナイーブに考えるのであれば、毎回、各座標からBFSで最寄りの線路や駅を探索し、そこまでの建設ターンを求めることになります。
しかし、これではどう考えても間に合わないので、計算の高速化を考えます。つまり、あらかじめ最寄りの線路や駅までの距離を計算しておき、T × M のループの中では、計算結果を呼び出すだけにします。
これは、ターン終了時に、現在の全線路 (もしくは全駅) をキューに入れてBFSを1度だけ回し、N × N の全座標に対して最寄りの線路への距離を記録しておくことで実現できます。
この事前計算により、T × M のループ内で、O(1)で建設ターン数と建設コスト額を計算できるようになりました。
計算の高速化 (建設によるターン収入増加額)
続いて「建設によるターン収入増加額」についても、計算の高速化を考えます。こちらは、サンプルのUnion-findを使っても良い気もしたのですが、一応自分で実装しました。
こちらも毎ターン愚直にシミュレーションしていると時間が足りません。
そこで、「建設ターン数」と同様、ターン終了時に、N × N の全座標に対して、各座標から2距離以内にいるhome/workplaceを抽出し、現在の線路情報と照らし合わせて、「このhome/workplaceのペアを繋ぐと、ターン収入がどのくらい増加するか」を事前に計算して記録しておきます。
これにより、home/workplaceペアを選択した際に、O(1) (高々13回：事前計算以外に繋がる駅があるかの確認) で、収入増加を計算できます。
これらの計算の高速化により、T × M × 様々なオプションのループでも、高速に評価関数を計算し、貪欲に選択肢を選べる系が実現できました。
ビジュアライザ
せっかくなので、ビジュアライザを2つほど例示します。
まずSeed = 0の場合。そんなに悪くなさそう。
また、Seed = 13、M = 1475のパターンも示します。 こんな路線の電車で通勤させられるとかボイコット不可避では
最終結果
これが最終提出となり、結果は本番258位でした。
システムテストだとTLEが発生して、少し点数が落ちた模様です。
それでも、パフォーマンスは1695で、過去最高のレーティングに到達できました！
最後に
事前計算をがんばったこともあり、もう少し順位的には上がると思ったのですが、思ったより周りの追撃が激しかったです。明日のAHCラジオが楽しみですね。
AHCはこれで7度目の参加ですが、「比較的正しい評価関数を設計する」「乱択に頼らずしっかり高速化して貪欲法で戦う」「ルールベースだけで100位を取る」などの目標を掲げて参加しています。
今回のAHC043では、前半の2つに関しては達成できたので、そこそこ満足です。
AHCラジオを見てしっかり復習したいと思います。
追記：
uta_cccさん、allegrogikenさんやigaxxさんなど、貪欲×計算高速化でさらに上に行かれている方の参加記を観測したので、この方針でもまだまだ行けそうです。
allegrogikenさんの「1手先のスコアも貪欲に含める」「初期解の多様性を持たせる」などのアイデアや、uta_cccさんの「パラメータを乱択しながら貪欲する」という考えは、これからの貪欲法実装に参考になると感じました。
本記事は以上になります。ここまでご覧くださり、ありがとうございました！
Discussion