3行でまとめると
- AHC 参加 4 回目なので今回こそは Heuristic な解法を実装したかった
- 始めてみたら非合法解連発で WA の山
- バグを潰しても計算量の削減ができずTLE連発で貪欲法すら実装できなかった【完】
低レベルな内容なので、技術的な情報をお探しのかたは申し訳ありませんが、ブラウザをそっ閉じしていただくようお願いします。
問題の要約
- 50*50の正方形のマップがあります
- 1000人ぐらいの市民が住んでいて、それぞれの家と職場が別々にあります
- 駅を設置して線路で繋ぐと、家と職場の両方が駅近の市民は電車通勤します
- 電車通勤する市民からは運賃が徴収できます
- 駅と線路を設置するにはお金と1ターンの時間が必要です
- 800ターン経過後の所持金をできるだけ大きくしてください
序盤：ルールを誤解して時間を浪費する
まずはこちらを御覧ください。参加した人が見ると、なんだこれって感じですね。
これは私が最初に提出してみたプログラムで生成した解です。内容としては「市民の一人だけを通勤させてあとは放置。最終的に一番スコアが高くなる人を探して間を最短距離で繋ぐ」です。
一応これだけでも、サンプルプログラムよりは良いスコアになるんですけどね。
お察しの通り、この時点で私は問題に対して、大きな勘違いを2つやらかしていました。
私が思い込んでいたルールが↓こちら。
- 市民の家か職場があるマスには駅や線路を設置できない
- 市民から得られる運賃は乗車した距離(線路の数)に従う
こんな制限はない。
この時点で、次の段階で作ろうとしていたロジックが「適当に駅を作ってつなげて、最終的に一番スコアが高くなる組み合わせを探す」でした。これなら最初に作ったプログラムを少し直すだけでいいと思ってたんですが、上のような勘違いをしていたせいで、盤面によって連列可能か判定できるように駅の情報を持たないとダメだなぁとか余計なことに脳みそを使ってました。
中盤：計算量の削減に失敗して処理時間に苦しむ
次のステップとして、駅の場所とそのとき圏内に入る市民の情報をリストアップして、最終的なスコアが一番大きくなる駅を探す処理を作り始めました。
そして、この作業中のバグのおかげで、民家や会社があろうが線路や駅を敷設可能であることに気づきました。これが確か、2/18、火曜日あたり。バグもたまには役に立ちます。
自分の勘違いに気づかせてくれた解のビジュアライズが↓こちらです。
これを見て数秒ぐらい 「あれ？ ビジュアライザのバグか？」 とか思ってた自分が不遜すぎて面白いです。慌てて問題文を読み直して、自分の思い込みと無駄に時間を費やした実装の量に心が折れかけましたが、なんとか奮起。
じゃあ、基本的にすべてのマスに駅を作った場合を検討しないとダメじゃん。組みあわせが最悪、$2500 * 2499 = 6,247,500$ あるけど、計算量どうしよう？ と思いつつ、いったん愚直に全パターンを比較検討するコードを書いてみます。結果、スコアは少し上がったものの、処理時間が1秒を超えました。
事実上の一手を探すだけでこんなに時間がかかるようでは、山登り法とか焼きなまし法みたいなヒューリスティックなアルゴリズムの適用は絶望的です。しかし、こんな複雑な判定をどうやったらそれができそうな処理速度までもっていけるのか自分のスキルではまるで分かりません。
データの受け渡しで無駄なコピーコンストラクタが動いている箇所を切り詰めるなど、小手先の改善で処理時間を30%ぐらい減らせましたが焼け石に水。諦めて今回は貪欲法で求められる1パターンを作ることを目指そうと舵を切りなおしました。
ここまでで 2/20(木)。残すは週末の三連休。
終盤：実装の面倒さとTLEの嵐に泣く
最初の2駅だけなら、収入の判定も敷設のコストも単純なんですが、ここにもう1路線足すとなると途端に面倒なことが増えます。
まず、今の2駅とは関係ない駅2個と路線を作るのと、今の路線を延伸して新しい駅を1つ作るのでは大違い。まず敷設のコストが駅一つ分違います。これを適当に処理して増設用のコマンドを出力すると、途中で所持金が足りなくなって不正解、解なし、WA になって 0 点です。
新しい路線を作った場合の収入の見積もりを正確に出すには、駅が連結しているかどうかを考慮しないとダメですし、それによってどの市民が通勤可能になるのかもグルーピングして判定しないといけない。
加えて、すでに線路が敷かれているマスを超えて路線を繋ぐ場合は、そこに駅を作る必要があるので、最初の更地に線路を敷くのとは必要なコストが変わります。コスト不足や不可能な操作を出力しないようにするには、更新後の盤面によって敷設のコストを再計算しないといけません。ちなみに、すでに駅があるマスに重ねて駅を作るコマンドを出力してしまうと WA になって 0 点です。 マジで面倒。
最初の一手に1秒以上かかるようなノリのコードでこれを処理しようとすると、当然 TLE 連発です。それだけでもダメですが一番良くないのが、一手に時間がかかりすぎて最終的な処理時間が読めないこと。予選の暫定 50 サンプルがギリギリ3秒以内で通ったとしても、本番のシステムテスト 2000 サンプルではボロボロの可能性があります。
仕方ないので、駅自体もその組み合わせに対して、見積もりする数の上限を決めて探索を途中で打ち切ることで、一定以上の時間はかからないようにしました。
以下、詳細は端折りますが、駅の連結とそこに属する市民を管理するために Union-Find 木をどうこうしようとして無限ループや絶望的な処理時間の増加など、山のようなバグを乗り越えて、なんとかかんとか暫定サンプルの範囲では、2手目をWAにもTLEにもならないように出力できるコードが完成しました。
残念ながら増設後の収入の見積もりがバグっているようで、マップによっては実際には収入は増えない、敷設コスト分のスコアを下げるだけの操作を選んだりします。ここが正しければ（処理時間を無視すれば）N+1手目以降も検討できるように作っていたのですが、間に合いませんでした。
WAで0点になるリスクはとれないので、探索は2手目で終了、それでも平均するとちょっとだけスコアが上がるので、今回はこれを提出版にしました。
ちなみに、こんな解を平気で作ります。自分が市民だったら暴れてますね。
結果（暫定）
そんなこんなで暫定の結果はこちらです。
有効回答の提出者が 1241 名なので、ちょうど真ん中あたりですね。自分的にはやりたいことのほとんどができなかったので、その割にはマシな成績という感想です。
次こそは、なんとかヒューリスティックな世界に片足を突っ込みたいので、強い人のコードを読んで、多少なりとも理解を進めておきたいと思います。
最終結果
システムテスト(2000サンプル)の結果が出ました。
1266 でギリギリ水色でした。いやぁ、前回に続いて、これで水色perf取れるんだ、という感想しかないです。なんかアルゴリズム部門との温度差に風邪をひきそう。
古いABCの問題をやってみると、今だと茶diff程度の問題が水色diffになってることがあるので、ヒューリスティック部門はまだ普及の途上ってことなんでしょうね。アルゴ部門と比べて、学習環境があまり整備されてないっていうのもあるのかな。
短期でも4時間ありますんで、大会の期間は長いですが、どれだけ時間を注ぎ込むかは個人の自由なので、一度試しにやってみると、意外と面白いかもですよ。私は楽しいです。（勝てないけど）
次は頑張ります😌