https://kiri8128.hatenablog.com/entry/2024/09/02/195000

AHC 036 に参加しました。

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

アイデア

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

木のイメージとメリット

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

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

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

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 をすることで各状態間で移り合うために必要なコスト（信号の切り替え回数）が求まる
さらにを「番目の目的地に到達した時点で状態がであるとき、残りの目的地をすべて辿るために必要なコスト」と定義するとこれは後ろから順に最適手順を計算できる。
- なお $s$ は $t$ を含むもののみを調べれば良いが、これは多くの $t$ についてあまり多くない

部分コピーが必要な場合

長さ $L_B$ の区間すべてではなく一部だけコピーしたい場合が存在する
これらの状態をすべて持つと状態が多すぎて $\mathrm{DP}$ ができない
よくあるのは、目的地に到達したあともとの道を引き返す場合なので、この場合だけ愚直に処理することにした

全体を複数回トライ

時間の範囲で全体をやり直して最も良いものを選ぶ
- （と言っても Python だと $1$ 周 $800$ ～ $1800$ ms ぐらいかかったので、 $2$ ～ $4$ 回ぐらいしか回らないが）

ビジュアライザ

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

$A$ の経路

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

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

感想・関連ポスト

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

#AHC036

順位表ビジュアライザ pic.twitter.com/AGckMBgvi7
— きり (@kiri8128) September 2, 2024

正の得点を得ました。#AHC036 pic.twitter.com/GpZhUsmTFz
— きり (@kiri8128) August 25, 2024

#AHC036 おつでした

プレテスト 43.7B で 5 位でした。

やったこと：
・根付き木構造にして、各葉と根を結びました（L_A に収まらない場合は類似のものを合体します）。
・後半は、長さ L_B 区間を使う前提なら DP で最適解が求まるのでそれをベースに。
— きり (@kiri8128) September 2, 2024

END

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