AHC 043 暫定112位 解法

AHC 043お疲れ様でした。暫定112位だった解法とそこまでの過程について述べます。（基本的により高順位の人の解法の方が役に立つと思いますが）誰かの参考になると嬉しく思います。

解法

提出コード

seed=0

seed=3

方針・実装上の工夫

• 最初の二駅は何が最適なのか決めかねたため、各人の家・職場のマンハッタン距離2以内の地点同士を候補にして、時間が許す限りシミュレーション
• 設置予定の駅がない場合は設置済みの駅からのダイクストラ法で各地点の最短経路を求めて、設置によって最終的に収益が見込める駅の決定
• 一番収益が見込める場所とそこまでに必要な線路を優先度つきキューに追加し、グラフが連結になるように線路・駅を設置
• 収益の計算に際して、すでに家（もしくは職場）が駅によってカバーされている場合は、そのままの収益でされていない場合は1/2くらいの収益を計算した。
• 線路を設置する際に今後の収益が見込める際は代わりに駅を設置
  • その際に次に設置する駅によってカバーできる場合はスキップ

最終的な局面においては駅を設置するべき・しないべきというのは計算によってわかりますが、途中時点での「今すぐに収益にはならないが将来的にはプラスになる」というポイントを1/2の収益が見込めるとみなすことでいい感じに拾えた気がします。

一方で終盤に、「線路を最短経路で敷くべきなのか、将来的に無駄に敷かないように周りの需要を見越して敷くべきなのか」という点を考慮しても良かったかもと思いましたが時間が足りませんでした。線路を敷くという行動は、線路代の損失以上に駅を序盤の方に設置できない機会損失という面が大きそうです。

反省・今後の課題・感想

前回は特定の値の場合に弱いという傾向に気づけなかったため、手元でのテストケースにK, Mの最小・中間・最大の3✖️3ケースで試すようにして、解法の弱点を見つけやすかったです。

GitHub Copilotのおかげで面倒な実装を省力化しつつ楽しめました。

前回は中途半端なランダム要素を導入したり、決めの値をチューニングしたりといったところに割と序盤の方からシフトしてしまい、本質的な貪欲解に大きく負けるという悔しい思いがあったため、最後まで考察に時間を割けました。特に何度も動きを観察するのは楽しかったです。

今回は特に焼きなましやビームサーチを活かす場面が見つけられず、「なとなくいい答えを出しそうなロジック」を見つけることで終わってしまったので、他の人の解法を参考にしたいです。