AHC043振り返り

はじめに

AtCoder Heuristic Contest 043に参加した。
暫定順位で300台後半と正直振るわなかったが、結構楽しめたと思う。

問題

問題は鉄道会社の運営ゲームという設定。家と職場を結ぶと、その距離に応じた収入がもらえる。人は2マス以内であれば歩くので、うまく駅を配置することと、収入になる駅同士を繋げるのがポイントかな？と考えて。駅建設のコストが5000と線路建設のコスト100と比較するとかなり大きいので駅の数を減らすのがポイントかと考える。

このため、以下のフローでやっていけばいいかと考えた。

1. 駅の配置を決める
2. 駅と線路を作る順番を決める
3. 実際に手順を決める

資金がないのに駅や線路を構築しようとするとゲームオーバーなので、3.で「待機」を入れつつ構築しないといけない。

最初のアイデア

駅の配置決定

まず、駅の配置を決めることにした。これは焼きなまし法を使ってみた。

初期値として、すべての家と職場のマスに駅を設置し、家と職場を線路で直接結んだ。これは、最大の収入が得られる一方で、沢山の駅と線路を構築する必要がある。実際に線路の経路を計算するのではなく、単純に家と職場のマンハッタン距離から必要な線路の数は導出した。評価式としては、時刻0でこの線路と駅を構築した時、時刻$T$に得られる資金額とした。つまり以下の式となる

$$\sum_{\{接続された家と職場\}} (家と職場の距離) \times T - (駅コスト)\times(駅の数) - (線路コスト)\times(線路の数)$$

近接解としては、以下の行動のいずれかを行なったものとした

• ランダムな駅$i$を消す
• ランダムな駅$i$を１マスか2マス動かす
• 2つの経路A $\rightarrow$ B, C $\rightarrow$ D を組み合わせてA $\rightarrow$ C $\rightarrow$ D $\rightarrow$ B という経路にする
• 経路$p$と$q$の順番を入れ替える

最後の順番はあまり意味がないように感じるが、[A $\rightarrow$ B, B $\rightarrow$ C, A $\rightarrow$ C]と経路が並んでいる時、最初の2つの経路で、AとCはBを経由して接続されているため、最後の経路に線路は引かれない。このため、線路長に差がでる。

これにより得られた駅の配置は以下のようになった。結構な数の駅と職場が外れているが、駅の数はかなり減らせた。

駅の配置の初期値と最適配置後

駅と線路の建設順決定

駅の位置と駅間の経路の一覧ができたので、構築する順番を決める事にした。このゲームの場合、最終的な資金がスコアになるので、ギリギリまで建設をやっていると、資金が少ない状態でターンエンドを迎えてしまい、スコアが低くなる。そのため、「今の盤面で、そのまま最終ターンまで待機した場合、資金がいくらになるか」を評価関数として、ビームサーチを行うこととした。

線路の数はマンハッタン距離で近似し、建設に必要なターン数と費用を算出。資金が不足している場合、待機するターン数も加算して評価関数を求めた。

手順の決定

手順はダイクストラを使って線路の配置した。最短距離で引けないこともあるため、資金をチェックしつつ「待機」を追加して資金がつきないようにした。

seed 0の結果 (Score: 507,920)

そこそこうまくいっているように見えるが、人の数が多いシナリオの場合、制限時間内に終わらずにTLEを起こしてしまう。駅と線路の建設順を決めるところで、選択肢が大きすぎるためである。時間で切ってもいいのだが、その場合少しの駅と線路しか建設できずに終わってしまう。

1つの木を作る

駅の配置決定時に、初期値として家と職場のペアを用いたので、後ろの処理でも連結していないグラフを想定していたが、最適解は「木」になっているので、シンプルに1つの木を作る問題として解くと収入の計算などはすごくシンプルになる。

駅の配置決定

適当に駅を固定数配置した後、近似解として最大2マス移動させるとして焼きなましを行なった。
駅の数は変動させなかったので、評価関数は収入の額とした。

駅と線路の建設順決定

ここはビームサーチで実施。次にどの駅を木に繋げるかを総当たりで決めて、最も近い木に含まれる駅と接続することとした。評価関数は「今の盤面で、そのまま最終ターンまで待機した場合、資金がいくらになるか」のままにした。初期値としては、駅を1つ設置した状態を、駅候補の数だけ用意している。

手順の決定

手順の決定手法は同様にした。

seed 3の結果 (Score: 2,164,648)

これで、人の数が多いシナリオにおいてもタイムアウトしなくなった。
最終的に駅候補の数やビームの幅などを調整して提出。終了した。

振り返り

フェーズを3つに分けて、それぞれの入力/出力を作っていたのでいろいろ試すことができた。一方で、最初のフェーズの焼きなまし、次のフェーズのビームサーチにこだわり過ぎたのかな？という気はする。他の人のを見ると駅候補として100以上を持ってきているので、もっと高速化するか、ビームサーチでなくて、単純な貪欲法ベースの方が良かったのかもしれない。