AHC 036

 

AHC 036 に参加しました。

プレテスト 43,711,795,647 点で暫定 5 位です。やったことをメモがてら残しておきます。

 

 

アイデア

 

  • A の構築
    • 頂点のうち 1 つを「ターミナル」として、各頂点からターミナルに最短でつなぐ *1
    • これはターミナルを根とする木構造にすることで、各葉について「根→葉」のパスを持つことで達成できる
    • 長さがはみ出してしまう場合は類似パスを合体する
  • A を決めたあとの戦略
    • A のうち連続 L_B マスを使う方法のみを考えると、 \mathrm{DP} で最適解が求まる
    • これを基本として推移しつつ、 L_B 未満のマスだけ変えた方が得になる場合にはそれを採用する

 

木のイメージとメリット

こんな感じで、真ん中付近にあるターミナルから各頂点を最短で結びます。

木のイメージ
  • 仮にすべての頂点をターミナルから L_B 以内の長さで結べれば、どの遷移もコスト 1 以内で到達できる（総コスト 600 以内が達成できる）。
    • l_B が大きい場合 *2
  • L_B より長くなってしまっても、一旦ターミナルを経由することでどの頂点にも効率よく到達できる。

 

 

実際のケースの木のイメージ

Seed 0 ではこんなような感じ。

Seed 0 の木構造

 

  • 黄色がターミナル
  • 黒太線が木の辺
  • 青の頂点は葉
  • 灰色の頂点は不要なので使わない（ A に含めない）もの
  • ピンクの頂点は行き先にはならないが使うもの
  • 頂点の横の数字はターミナルからの距離

 

 

最終方針

A の構築

  • ターミナルの選定
    • 行き先となる各頂点までの距離の総和（行き先になる回数で重み付け）が最小となるものをターミナルとする
  • 木構造化
    • ターミナルを根とする部分木であって、ターミナルまでの距離を大きくしないものを選ぶ *3 
    • 各頂点から、ターミナルに近付く辺をひとつ選べば良い
    • ここで不要な頂点（行き先にならない頂点であって、中継点にもならないもの）は無視する
  • パスを抽出
    • できた木について、葉からターミナル（根）までの最短路（パス）を結ぶ
  • パスを合体（長さの節約）
    • これを愚直に並べたものを A としたいが、そのままだと L_A を超えてしまうので近いものを合体する
    • 具体的には、ターミナルを T として、 T \to a \to b \to c \to d \to e と T \to a \to b \to c \to f \to g \to h という 2 つのパスがあったら T \to a \to b \to c \to d \to e \to f \to g \to h のように合体する。
    • 共通部分の長さを x （この例だと x=3 ）、共通でない部分の長さをそれぞれ l_1 および l_2 として（この例だと l_1=2 、 l_2=3 ）、それらが行き先になる回数を c_1 および c_2 とする。
    • ターミナルからの到達時間は、約 l_1 \times c_2 / l_b だけ遅くなり、全体の長さが x だけ短くできる。この効率が良い（つまり x / (l_1 \times c_2) が大きい）ものから貪欲に合体させる
  • パスの連結
    • できたパスを連結して 1 本にする
    • 連結する際は、 2 つをペアにして根を 1 つ省略する感じで
    • 連結の順番は次の指標で雑に焼く
      • ターミナルをまたぐふたつは、なるべく連続目的地になるものを含める
      • ターミナルをまたがないふたつは、なるべく互いに隣接するものを選ぶ
    • 繋げたものを A とする

 

合計の長さを短くするため、類似パスを合体する

 

「根から葉」のパスたちをペアにして繋げる

 

A を決めたあとの戦略

DP による理論値
  • 常に幅 L_B の区間の信号を使うと決めた場合、信号の状態としてありえるものは L_A - L_B + 1 通り
  • 状態としては、 L_B の区間内にある頂点が連結でない場合はそれらを区別する必要があるが、下位互換を無視すれば（実験すると） 500 ～ 1000 程度になることが分かる。
  • これらの間の辺の数は 4 万から 40 万程度なので、 BFS をすることで各状態間で移り合うために必要なコスト（信号の切り替え回数）が求まる
  • さらに \mathrm{DP}[t][s] を「 t 番目の目的地に到達した時点で状態が s であるとき、残りの目的地をすべて辿るために必要なコスト」と定義するとこれは後ろから順に最適手順を計算できる。
    • なお s は t を含むもののみを調べれば良いが、これは多くの t についてあまり多くない

 

部分コピーが必要な場合
  • 長さ L_B の区間すべてではなく一部だけコピーしたい場合が存在する
  • これらの状態をすべて持つと状態が多すぎて \mathrm{DP} ができない
  • よくあるのは、目的地に到達したあともとの道を引き返す場合なので、この場合だけ愚直に処理することにした
全体を複数回トライ
  • 時間の範囲で全体をやり直して最も良いものを選ぶ
    • （と言っても Python だと 1 周 800 ～ 1800 ms ぐらいかかったので、 2 ～ 4 回ぐらいしか回らないが）

 

ビジュアライザ

Seed 0 と Seed 23 の結果はこんな感じ（長いので最後の部分のみ）。

Seed 0 ビジュアライザ

Seed 23 ビジュアライザ




A の経路

Seed 0 の A に現れる頂点を順に結ぶとこんな感じ。隣接していない頂点に移動する場合は緑線で示しています。

（なんか緑が多くて汚い気がしたけどいい方法が思いつかず・・・）

A の経路

感想・関連ポスト

  • 初サブはどれぐらいかなーと思って投げただけだが思いのほか 2 位が取れてびびった
  • そこから序盤元気マンをやるつもりだったが思ったより耐えた
  • 最後の方は小手先でちょっと改善するぐらいしかできなかった（上位勢は何やってるんだ・・）

 

 

 

 

END

*1:ターミナルの個数は 1 または 3 が良さそうだったが、最終的には 1 にすることにした

*2:Seed 23 など

*3:例外として、ひとつの頂点の距離を 1 伸ばす代わりに 1 つの頂点を「不要」とすることができる場合は採用した