AHC 018 - Kiri8128の日記

AHC 018 に関する考察・日記です。

Pretest 40.4B で暫定 13 位です。

（Seed 0 の結果）

動画は一番下のツイートリンクを参照 *1

問題ページ

戦略概要

ざっくり言うとこんな感じです。最後にもう少し正確に書きます。

10 マス刻みで 20 × 20 のグリッド（格子点を基地と呼ぶ）を考え、このグリッド上で最小全域木を求めるようなことをする
各基地の評価を「次の攻撃でそこが破壊された場合に、その基地を通って 2 つの連結成分を結ぶために必要な期待コストの最小値」とし、評価が小さいものを優先に攻撃する
ただし期待コストは「移動距離 × 両端の基地を破壊するのにかかったコストの平均」としている *2
結んだあとは、追加点ありのクラスカル法に帰着できる。追加点は貪欲に選ぶ
基地間を結ぶのは、左右の高さが同じなら真ん中から、そうでなければ低い方から順に試す

1 日目～ 2 日目

考察

ビジュアライザを見る感じだと、高い山 *3 が途中にあることがあるので避けるのが大事
山の大きさや尾根の幅は 20 程度のものが多い
つまり幅 10～20 刻みぐらいで山の高さを調べておくとある程度の地形が分かるはず

高さの調べ方

高さを厳密に調べようとすると 1 ずつ壊していく必要があるが、これは効率が悪い。固定コスト（問題文中の $C$ ）の数倍ぐらいが目安になるか。
1 点の高さを完全に調べる必要はなく、ある程度高いと分かったら *4 別の場所を調べる方が良い。
例えば、「幅 20 刻みで格子状に $10 \times 10=100$ 個の点（基地と呼ぶことにします）を選ぶ → 高さを 100 刻みぐらいで低い方から調べる → 全部が連結になったら終了 → 格子点の間の移動コストを、両端の高さの和半として、最小全域木の容量で結ぶ」のような解法がありそう
低い道で行けない場所はもう少し細かくしていく（幅 20 → 10 → 5 みたいに順にせばめる）方法もあるが実装むずそう。
ただし端っこの方など、明らかに使いそうにない場所も高さを調べるのは無駄なのでうまく省きたい
省く方法は、孤立成分から水源または別の家に近付く方向に進めたいが（間に山があって）遠回りするのが良い可能性もあるので難しい。簡便に、孤立成分の隣接する箇所をすべて調べる手もあるかも。
高さを少しずつ上げていくとき、早めに全部が連結になれば嬉しいけど、例えば水源や家自体が高い場所にあるときなどはどうしようもなさそう。
あと水源や家が基地と一致するわけではないので、最寄りの基地まで結ぶ必要がある。これは水源・家から候補の 4 点を結ぶ辺を張っておけば良さそう（実装めんどそう）

はじめての提出

まずは（上の考察はいったん置いといて）適当な水源に縦→横でつないでみよう → 9.1B で 362 位 *5

#AHC018

参加することに意義がある pic.twitter.com/q1zQiGdiia
— きり (@kiri8128) February 19, 2023

連結の管理

各家について、最も近い水源または（まだ連結でない）家に向かって縦→横でつないでみよう → 18.2B で 78 位。

ちなみに Perlin Noise について調べようと思ったけどよくわからなかったので特に性質は使ってません。ランダム生成もできなかったので、 Seed 0～999 までダウンロードして直接読み込みました。

3 日目（2/20）

考察（アドホック）

でも格子状のやつなんかはだれでも思いつきそうだし、上位に入るにはもう少し奇抜な方法を取らないと・・・
格子状じゃなくて基地をアドホックに作れるようにできれば柔軟になりそう。幅を 20 → 10 → 5 みたいにせばめるやつのさらに柔軟バージョン。
その場合全部の基地の間に辺を張るとたいへんなことになるので、ある程度近くで、途中付近にほかの基地がないものに限れば良さそう。「途中付近」の判定は、角度が○○度（例えば 150 度とか 165 度とか）以上みたいにすればできそう。 *6

考察（シャボン膜問題）

もうひとつ考慮するべきことがあって、実はよく考えると最小全域木がそのままでは使えない点。つまりシャボン膜の最小化みたいなことを考えないといけない *7
水源・家については、水源同士を長さゼロの道で結んでおいて、基地のうちいくつかを好きに含めたときの最小全域木でいけそう。基地の選び方は焼きなましとかでできるのかな。あるいは貪欲に「その時点で追加した方が良い基地は追加する」でもそれなりにはなるかも。

戦略（案）

たとえばこんな戦略はどうか *8 。

掘るパワーは、マスごとに徐々に大きくする方式にする *9 。破壊されたマスの「コスト」は、 1 ステップごとに攻撃した場合の破壊までにかかるコストとする。
幅 20 ごとの格子点を基地とする。
水源・家・基地を頂点とする重み付きグラフ G を作成する
水源・基地がある地点は破壊できるまでする（何ステップで破壊できたかは記録する）
その最寄りの 4 点も破壊。水源→最寄りの 4 点には、重みが「長さ × 両端のコストの平均」である辺を張る
ステップ数 $i$ を増やしながら次を行う
G の連結成分のうち家を含み水源を含まないもの Z すべてについて次を行う
Z に属する基地の隣接基地でまだ破壊されていないところをステップ $i$ まで攻撃する。破壊されたらその頂点と隣接基地に辺を張る。重みは頂点のコストの平均。
すべての家がその連結成分内に水源を含むようになったらループを抜ける
基地の数を $B$ とすると、 $W + K + B$ 頂点の変則最小全域木 *10 になる。選ぶ頂点の集合を焼きなましで決める。
最小全域木を貪欲に結ぶ

頑張って実装するとだいぶ改善してそう。出してみると全ケース WA 。。

4 日目（2/21）

一か所間違いを見つけて修正すると 4 ケース WA 。でも相対順位には反映されるらしくて 20.5B ぐらい。

ループのところ、ステップ数を一回増やしたら戻さないようにしていたので、山を越えて平地に出た時もやまの高さで掘っていることに気付いた。

掘るパワーは、マスごとに徐々に大きくする方式にする *11 。破壊されたマスの「コスト」は、 1 ステップごとに攻撃した場合の破壊までにかかるコストとする。
幅 20 ごとの格子点を基地とする。
水源・家・基地を頂点とする重み付きグラフ G を作成する
水源・基地がある地点は破壊できるまでする（何ステップで破壊できたかは記録する）
その最寄りの 4 点も破壊。水源→最寄りの 4 点には、重みが「長さ × 両端のコストの平均」である辺を張る
ステップ数上限 step_limit を増やしながら次を行う
G の連結成分のうち家を含み水源を含まないもの Z すべてについて次を行う
Z に属する基地の隣接基地でまだ破壊されていないところをステップ step_limit まで攻撃する。破壊されたらその頂点と隣接基地に辺を張る。重みは頂点のコストの平均。
破壊したらステップ数を $1$ に戻して続行
すべての家がその連結成分内に水源を含むようになったらループを抜ける
基地の数を $B$ とすると、 $W + K + B$ 頂点の変則最小全域木 *12 になる。選ぶ頂点の集合を焼きなましで決める。
最小全域木を貪欲に結ぶ

変則最小全域木は追加頂点なしで雑に実装。あとついでに幅を 10 にした方が良さそうだったのでして出してみた。なぜか WA は増えた（6 WA）けど 26.5G で 43 位。

#AHC018

50 位入れた pic.twitter.com/xZaOcpGwb1
— きり (@kiri8128) February 21, 2023

あとやるべきことは追加頂点ありバージョンと、有効頂点を優先的に追加する方式。

行きたい方向優先評価

未完成連結成分（A とする）から、行きたい連結成分（B とする）に対して、「近付く」マスを優先的に埋めたいです。

A の頂点 v1 から v1 の隣接未開拓マス v2 に掘り進むアクションの評価を、 B および B の頂点 v3 をすべて動かすときの次の値の最小値とします（小さいほど優先度が高い）。

v2 があと一回で掘れたとしたとき、（途中ですでに開拓されたマスを通らずに） v1 → v2 → v3 と進むときのコスト

ただし、v2 から v3 へ進むコストは「（v2 の発掘コストと v3 の発掘コストの和半） × （v2 から v3 への距離）」とします。 v1 から v2 へ進むコストも同様です。

例えば、下記は Seed 1 の途中ですが、右上の 2 つが近いので、近付く方向に進んでいます。左下の家は、ふたつの水源に近いですが、高い山を通らなくて良い右側を優先的に目指しています。

ここまで頑張って実装すると 32.7B で 23 位。

#AHC018
ちょい伸び pic.twitter.com/KA0OvVZmLA
— きり (@kiri8128) February 21, 2023

手元実行の評価について

相対評価スコアなので、テストケースごとのの単純平均を取るとコストが大きいケースを重く評価してしまいます。そこでコストの対数を取ってその合計で評価しました *13 。

対数を使うことは、自分のコストと最高点プレイヤーのコストがほぼ比例すると想定すれば妥当性があります。本問ではケースによって比率が大きく変わることはなさそうなので、指標として十分機能しそうです *14 。

私の場合は、絶対スコア（コスト）を $score$ として、 $\log_2 score - 16$ を指標として使っていました *15 。ただしスコアはケースのパラメータによる影響が大きいので、同じケースで比較しました *16 *17 。例えば最初の 10 ケースで $-0.052$ 、最初の 100 ケースで $0.220$ のようにメモっておいて、そこからどれぐらい変動したかで変更の効果を図ります。

5 日目（2/22）

その後相対スコアは上がったりしたけど 23 位からは上がらず（むしろ放っておくとどんどん下がる）。

ひとつの懸念は現状の方法だと計算量が悪すぎて TLE が危ない *18 。 $C$ が小さいときは小刻みに攻撃するのが無駄が少ないんだけど、 TLE とトレードオフになるのがちょっと困るところ。時間計測しながらどれぐらい刻むかを決める方法もありそうだけど、いいロジックが思いつかない。

手元環境

ここで時間計測と AtCoder のコードテストでの実行環境を導入

まったく同じコードで複数環境での動作をしたい（パラメタ書き換えミスによるペナがもったいないので）ので、それ用にコードを書き換える。

モードの種類は次の通り

手元実行（1 回）
手元実行（複数ケースのループ）
Submission 用
コードテスト用

1. と 2. は実行後にパラメタを与える方式にしている *19 。手元環境課どうかの判定は、 LOCAL という変数を事前に初期化しておく方法にしている *20 。

1. の場合はデバッグ情報や Visualizer に渡す情報を吐き出す *21 。

3. は本番。 4. は時間計測用に AtCoder 環境で流すためのもの。

3. と 4. は 1 行目の入力で判定する *22

時間軽減策

現状では次に攻撃する対象を選ぶ際に

g in G

v in g

next_v in neighvour(g)

dijkstra()

で、攻撃する場所とコストを所持し、 priority queue でコストが低いものから攻撃している。さらに破壊が発生したらコストをすべて再計算している *23 *24 。

この計算量は、基地（水源・家含む）の数を $B$ として $B^2 \log B$ 程度。さらに破壊による更新が最大で $B \times \mathrm{maxstep}$ オーダーで必要になるが、 $\mathrm{max step}$ は $C=1$ のとき $250$ 程度なのでそこそこ重い。

そこで破壊が発生しても、コストがあまり変わらない場合は更新せず続けることにした。具体的には、直近の更新から採用された攻撃のコストの最小値を $cost_{min}$ として、 $cost$ が $cost_{min} * (1 + \alpha)$ 以下の場合は攻撃を続けることにした。 $\alpha$ はとりあえず $0.05$ にしておいた。

すると実行時間が短くなり、なぜか得点も伸びた！？

再提出すると 20 位に！

#AHC018

うおおおお！！（1 枚目に入れた！の意） pic.twitter.com/IUhGL2rxBp
— きり (@kiri8128) February 22, 2023

6 日目（2/23）

新しくグループが結合したらさすがに再計算した方が良い気がしたので実装

→ 手元でも提出でも悪くなったので却下 *25

パラメータ調整もやろうとしたけどあんまり良くならないので却下 *26

あとパラメータ調整以外でできそうなことは、「なかなか破壊できないときは、周辺の基地を増やして細かく探索する」ぐらいしか思いつかない。ただこれは基地が固定でなくなることによって実装やロジックがめんどくさくなりそうなので今のところ敬遠している。そもそも高い山に囲まれた家がある場合などは、やみくもにたくさん探すより一点集中で突っ切る方がコストが低いこともあるし。

水源が 1 つだけの場合、結局 $1+K$ 個の水源と家を結ぶゲームなので、水源と家の関係は対等になる。現状、家側からしか探索してないので、 $W=1$ の場合は水源側からも探索を進めることにした。しかし点数はほぼ変わらず *27 。。

その後 Web 版ビジュアライザを眺めまくってると極端に無駄な動きをしているケースがあった。調べるとバグがあったので修正 *28 。

7 日目（2/24）

そろそろやることがなくなってきた。

最後の結ぶところの効率化

道を決めたあと、基地間を結ぶときの攻撃力をより細かいステップでやると良さそうなのでやってみた。

具体的には、次のようにしました。

① 両端の基地が同じステップまで掘っているとき

真ん中を少しずつ掘る
破壊できた強さで両側に広げていく
破壊できないときは一段階上げて伸ばす（一旦強くしたら戻さない）

② 両端の基地のステップに差があるとき

低い基地に近い方から、まずは低い方の基地を破壊した強さで掘る
破壊できないときは一段階上げてもう片方に伸ばす（一旦強くしたら戻さない）

「一段階」は、① では最後の攻撃の強さ、② ではふたつの基地の高さの差を $h$ 、基地間のマンハッタン距離を $k$ として $\sqrt{\displaystyle\frac{2hC}{k}}$ 程度にしています *29 。

図で表すと次のような感じです。左右の黒部分は高さがこれ以上であることが確定していて、灰色部分のどこかが真の高さであることを示します *30 。黄色が真の高さ、数字は攻撃する強さと順番です。

提出すると 38.6B で 13 位。その後順位変わらず 39.2B までいけた。

#AHC018
39B pic.twitter.com/34Yil4sHgr
— きり (@kiri8128) February 24, 2023

ところでこれ出したときに上位スコアチェックしてみたけど、自分のジャッジが終わる直前（数秒前）と直後（数秒後）で上位陣の得点が動いてて嬉しいね。ほぼ一律 0.02% 程度ずつぐらい下がってるので、きっとどれかのケースで私の結果が私以外の最上位の人を 1% ぐらい上回っているはず *31 。

（ジャッジ確定直前）

（ジャッジ確定直後）

その後バグを見つけて再送信 → 10 位！？

#AHC018

10 位！！！ pic.twitter.com/q8rhgrRgGZ
— きり (@kiri8128) February 24, 2023

通らなくて良い経路

連結成分 G の隣接基地を攻撃するときの評価を計算するとき、 G 内を通らないとしてよかったですが、 G の隣接マスも通らないとして良い場合があります。より正確には 1 ステップで破壊できたマスの隣接部分（下のピンク）は通らないとして良いです *32 。これにより、遠ざかる側を無駄に掘るコストを減らせます。費用対効果を考えて（1 ステップだけじゃなく） 3 ステップ以下のマスの隣接マスは通らないことにしました。

破壊時のリスト差分更新

マスを破壊したときに、そのマスから出る道が最善であることがわりとあるので、ここからスタートする分を入れると良さげ。 → 入れたら 41.1B で 6 位まで来た。

#AHC018

6 位？？？！！！ pic.twitter.com/CmDHOAhOhT
— きり (@kiri8128) February 24, 2023

8 日目（2/25）

保育園イベント *33 → ゆるふわオンサイト → ARC （爆死）

9 日目（2/26）

高い水源

家があるマスは全部破壊する必要がありますが、水源は必ずしも破壊する必要はありません。特に、水源のうちひとつが高い場所にある場合は、その水源を全部掘るコストが高くついてしまう可能性があります *34 。水源自体も Priority Queue に入れて、順番が来たら攻撃することにしました *35 。

2 基地間の平均の高さ

特に距離が長い場合、高い山がずっと続いている可能性は低いので、単純平均だと若干高めに評価してしまっている可能性がある。高さが指数関数になっていると思ってその積分を使うと点数が少し良かったので採用した。

具体的には、高さ $a$ と高さ $b$ の 2 地点が距離 $d$ だけ離れているとすると、単純平均だと $\displaystyle\frac{a+b}{2} d$ になるが、この方法だと $\displaystyle\frac{b-a}{\log b - \log a}d$ になる。

最終提出

ちょっと早いけど誤提出も怖いのでいったんこれで完成にします *36 ！

#AHC018
若干下がっちゃったけどやむなし。勝負です！！ pic.twitter.com/0ytmEhV0EI
— きり (@kiri8128) February 26, 2023

AHC に取り組むにあたって

いつもそうだけど、いきなり実装に入ると混乱しますね。

まずはやりたいことを明文化して、やりたいことが言語可できたら実装に移るのが個人的にはやりやすいです。

今回はこのブログの下書きを書くことで頭が整理されて、実装にも役立ちました *37 。

主要ケースの得点

最終提出直前の結果なので、最終提出とは少しずれるかも。

Seed 0: Cost = 121,139
Seed 1: Cost = 17,207
Seed 2: Cost = 213,380
Seed 3: Cost = 11,651
Seed 4: Cost = 66,967
Seed 5: Cost = 139,475
Seed 6: Cost = 296,528
Seed 7: Cost = 60,132
Seed 8: Cost = 20,719
Seed 9: Cost = 57,148

Seed 20: Cost = 18,082

最終ロジック

戦略

$20\times 20$ のグリッド（基地と呼ぶ）上で、すべての家を水源と連結にしたいです。より厳密には、水源・家・基地の間に辺を追加していきます。最小全域木を求めるクラスカル法の要領で、近いものから *38 結んでいくと良さそうです。

基地開拓フェイズ

最初にすべての家を破壊するまで攻撃します。その後は、クラスカル法の要領で、「水源と連結でない家を含むグループ（※）」について、最も近い「水源を含むグループ（☆）」またはほかの「水源と連結でない家を含むグループ（☆）」と連結にしたいです *39 。

どの基地を攻撃するのが良いでしょうか。ある ※ の基地 A からその隣接基地 B を攻撃することを考えます。 B から ※ を通らずいずれかの ☆ の基地 C に到達するときに、到達しやすいところを選びたいです。

この攻撃の評価を「A から B への移動コスト＋ B から C への移動コスト」で定義します。移動コストは、「両端マスの高さの調整平均 × 移動距離」です *40 。 $a$ と $b$ の調整平均は、 $\displaystyle\frac{b - a}{\log b - \log a}$ で表されます（詳細は記事中）。

この評価が小さいものから順に攻撃していきます。

水源側からも歩み寄りたいですが、水源側は必ずしもつなげる必要がないので評価に調整を加えます。具体的には、水源側の評価には $\sqrt{W}$ をかけています *41 。

経由地最適化フェイズ

グリッド上で連結になったらこれらを結ぶことを考えます。これは、水源・家に必要な基地を追加してそれらを連結にする *42 ときの辺のコスト合計を最小化する変則最小全域木に帰着できます。追加する基地を貪欲に選びました *43 *44 。

最終結合フェイズ

つなげる道順はすでに決まっているので、あとは基地間を掘るのみです。各マスでの攻撃の強さを決める必要がありますが、両側の基地の高さが同じ場合は真ん中から、異なる場合は低い方からみて、前のマスを破壊できた強さで攻撃する、破壊できなければ一段階上げる、の繰り返しにしました（詳細は記事中の図）。

解法・関連 Tweet

#AHC018 おつでした。
Pretest 40.4B で暫定 13 位です。
20×20 のグリッド上でクラスカル法みたいに連結成分をくっ付けていく感じでやりました。
重みは「次に破壊した場合に隣のグループと連結にできる期待コスト（≒両端点の高さの平均×距離）」です。
画像は Seed 0 の完成図と途中図（結ぶ前） pic.twitter.com/wu1b44qC4P
— きり (@kiri8128) February 26, 2023

推定、一切してません！
— きり (@kiri8128) February 26, 2023

End

*1:うまく上げられなかったので・・

*2:両端は破壊される前提なので、「予測」を行う必要がない

*3: 問題文中の「頑丈さ」を本記事では「高さ」と表現することがあります。また高い場所の周辺を「山」と呼びます。

*4:その周辺は使わない可能性が高いので

*5:この時点ではサンプルコードがあるのに気付いてなかったが、あとで見るとほぼ同じ感じっぽい

*6: より厳密には、基地 A と基地 B の間に辺を張る条件は、「AB 間のマンハッタン距離が 30 以下で、かつ基地 C であって角 ACB が 150 度以上であるようなものが存在しない」のようにする

*7: 今回はマンハッタン距離なので 120 度みたいなのは出てこないが

*8:「アドホック」はいったん忘れて

*9: 1 ステップ目は C + 10 、 2 ステップ目は 2C + 20 、など

*10:基地は選んでも選ばなくてもよい

*11: 1 ステップ目は C + 10 、 2 ステップ目は 2C + 20 、など

*12:基地は選んでも選ばなくてもよい

*13:本当はパラメータごとに調整した方が良いけどざっくりやりたいときは合計評価が欲しくなる

*14:AHC 016 のように特定のケースで上位者と下位者の得点の比率が大きく開くような場合は、そのようなケースの重要度を下げる調整が必要になります

*15:この指標が 0.01 小さくなると、相対スコアが約 0.7% （≒ $\log 2 / 100$ ）程度改善するという目安にできます。

*16:そもそもランダムケースが作れなかったので・・

*17:最初の 10 ケースは特によく比較するので（たくさん一気に流せないので）、若干過学習気味になっている可能性はあります

*18:TLE したのもあるし、 3 s ぐらいで終わるのもある

*19:非負の整数を入力すると seed を表し、負の整数 $x$ を入力すると seed が 0 以上 $x$ 未満のケースをループする

*20:LOCAL が 1 なら手元実行モード、定義されていなければ Submission モードまたはコードテストモード

*21:そのまま全部貼り付けられるように、デバッグ情報にもすべて頭に "#" を付けると楽になった

*22:1 行目に "Code Test" を与えるとコードテスト環境であると判定する。コードテスト時もジャッジは $S_{ij}$ を使って判定している。なおコードテスト時も本番と同様にジャッジを入力から受け取る方式も考えたが、その場合手元で流してからコードテストみたいな二度手間が発生してめんどいので断念した。ジャッジや入出力の違いは時間計測にはあまり影響を与えないはず。

*23:差分計算苦手

*24:厳密には破壊が発生しなくても攻撃により残りの高さが変わると動くが、影響が小さいと信じて無視している

*25:手元は 20 ケース、提出も 50 ケースしかないので誤差程度かもしれないが

*26:手元 20 ケースでずっと見てるので若干過学習になってる可能性はあるが・・・

*27:手元実行でもほぼ変わらず。よくなりそうなら $W \ge 2$ の場合も少しロジック入れようと思ったがやめた

*28:基地を掘るとき、破壊できなかったときの差分更新で 2 で割るところを 2 で 2 回割ってたのを修正。影響はほぼなさそう

*29:一段階を $s$ にすると、毎回の「余り」が約 $s/2$ 程度、無駄に攻撃する回数が約 $h/s$ 程度なので、 $\displaystyle\frac{sk}{2} + \displaystyle\frac{hC}{s}$ を最小化すればよいが、相加相乗平均を使うとこれは $\sqrt{\displaystyle\frac{2hC}{k}}$ のときに最小になることが分かる。地形によって若干変わるがまあ