AHC 018 のおもいで（RECRUIT 日本橋ハーフマラソン 2023冬）
AHC 018 2/18(土)-2/26(日)
【概要】
水源がいくつかと、家がいくつかある200x200の土地がある。
水路を掘って、全ての家を水源と接続したい。
ただし、地面には隠しステータスとして「硬さ」があって、掘る時にそれに相応する「体力」を必要とする。
消費する「体力」がなるべく少なくなるように、水路を掘ってください。
掘り直しになるよりも掘り抜きすぎるほうが問題かもしれない。8日目。
おまけ：「Atcoder Heuristicのローカルテスタの使い方」
【難しそうなので手をつけるかどうか迷う、1日目。（2/18 土曜日)】
日中は他用で手をつけられず。開始したのは夕方。
インタラクティブきた
ABCとかでもインタラクティブはコンテスト時間内に解けたことがない。
インタラクティブはAtCoderの「コードテスト」が役に立たないし…
岩盤の硬さは与えられないと。
全くわからない状態から動きながら試行錯誤するのかー。
ビジュアライザでは硬さは緩やかに分布してそう。柔らかい真横にめちゃ硬いものがあるわけではない。
うーん。難しいな。やめとこうかな。
…
AIかなー…
ルンバ的な...
（寝落ち）
（ABCも寝過ごした）
【試し掘りでのマッピング戦略。初回提出の2日目。 (2/20 日曜日)】
問題文を再確認。
・斜めには接続できない。
・水源に直じゃなくて水路にも接続できる。
まったく硬さの情報がない状態から、「近道（でも柔らかいところ）を探しながら掘っていこう！」では難しそう。
連続した部分を掘らないといけない制約はないようだ。
硬さを先にちょっとテストして、硬さマップだけ先に取得してしまってはどうだろうか。
適当に20マスごとくらいに間隔をあけながら力200くらいで最大5回ずつ掘って、掘った回数をプロット。（掘りきれなかった時は５.5をあてる）
matplotlibの出番。
普段は計算速度で割を食ってるけど、この辺の視覚的にできる感じはpythonistが有利か？
元々の図がこれ。
仮掘削の結果のプロットがこれ。
その結果を周囲のマスにも伸ばしてみる。
元々の図にちょっと似てるぞ！
もう一息。
マンハッタン距離10マス範囲内の平均値を各マスの値にする。
それっぽくなった。
最初は逆プーリングとか考えたがスキル的にもできないのでやめる。
「力200くらいで」とか「掘りきれなかったときは5.5」とかは、再生した図と、元々の図を見比べて、何回か（手で）数字を書き換えてoptimizeした。面倒なのでseed0で過学習状態。
本当はoptimizerとかで回すのだろうが…
再現図が書けたところで、次は動き方。
点自体は4*(10**5)個で、何度かならO(N**2)でも回せるかもしれない。
でも、隣接するマス同士はそんなに変わらないから、間引いて近似できるかもしれない。
線に重みをつけると8*(10**5)個くらいになるけれども優先度付きキューやデックで回せるだろうか？
やったけどだめだったこと
・unionfindで水源と家が全部一つのグループになるまでくっつけ続ける。
・クラスカル法で最短全域路を作成する。
→水源でも家でもないマスまで全部くっついてよくわからないことになったのでボツ。
最終的によさそうだったこと
・ダイクストラ法で接続する。
全ての水源の上流に、「仮の総合水源」を作成する。そこからのそれぞれの家への最短距離（重み付き）を得る。一つ最短の家を見つけたら、一旦全ての重みをクリア。
そこまでに作る水路と、発見済みの家の座標を、全て水源として扱い直し、「仮の総合水源」に直接接続して、改めて残りの家に対してダイクストラを最初から行う。
を繰り返す。全ての家が接続されたら終了。
仮掘削で穴が既に開いているところはまた掘らないように気をつけて…。
完成。
Rustの環境構築にエラー出まくって大変だったのはまた別のお話。
５時間くらい、夜の２時までRust周りで格闘し、やっとローカルテストが通り、提出した。
ここまで遠かった。今回は諦めようと何度も思った。苦心の末の提出。わくわく。
な なんと！！！！
WA！！！！！
なんでやねーーーん
ローカルテスト通ってるのに。
エラー箇所がどこかを探しまくった結果、「numpyを使っているのにpypyで出した」が原因でした。
30分待って再提出した結果は。
score：1481万 順位：275位/正解550人
いつの間にか、とっくの昔にARCの時間は過ぎていた。
明日以降でパラメータチューニングしてみるか。
↑seed0の結果。
【綺麗なマップ作りは不要かも。3日目。(2/20 月曜日)】
問題の制約を再確認。
・システムテストでは、それぞれのCの値について、375個ずつのテストケースが存在する。
・水源と家の位置は、Sijに反比例する確率で選ぶ。（家と水源はほぼ柔らかい位置にある）
やったこと
ジャッジの役割をするクラスをつくり、google colabで延々とケースを読み込みながら採点結果を吐く関数を作成。その関数をbayesian optimizerに渡して、いくつかのパラメータを最適化する（グリッドサーチは夜が明けても終わらなそうなので諦めた）。
主にマッピングのための試し掘りについて、「どのくらいの間隔で」「最大何回まで」「どのくらいの力で」掘ればいいか。掘りきれなかったマスの硬さをどのくらいと仮置きするか。
といったところを一気に調整してしまう。
Cの値だけ不連続なうえに、７通りしかなく、しかもシステムテストでは均等に用意されるということで、Cの値ごとに分けてそれぞれ20ケースずつ、35回くらいのベイズ最適化を回す。
正直20ケースでは少ないが、今回の延べ140ケースでも3時間以上かかったので、無料のcolabではこれが限界（体力的にも）。
試し掘りの最適回数は、Cの値にかかわらず、「１」。意外。
一回適当な力で掘って、掘れなければ「硬い」。
その周りも「硬い」ので、適当に避けていけばいいようす。
綺麗なマップを作る必要はないことがわかった。
こんなふうに見えているようだけど結果はそれなりにいい。
score 1074万 334位→205位 / 正解621人
だいぶ改善。
試し掘りの結果からの予想図を、周辺の平均値でならしてみてよりスムーズにしてみる。
きっといい結果が！と思ったら、評価は悪くなった。
せっかく、「硬い」「柔らかい」で明確に２パターンに分けられるプロットをしたのに、それをぼかして「見栄え良く綺麗に」してしまうと動きにくくなるようだ。
pythonなのに実行時間が1200msで、まだ全然余裕なので、この辺で何かできそう。
水源からも家からも全く逆方向で、絶対にかすりもしないような場所がある場合、そこは試し掘削する意味はない。節約できないだろうか。
↑seed0の結果。掘る回数を１回ずつにしてもそれなりに山を避けている。
【やっぱりマップをなんとかしたくて迷走。4日目。（2/21 火曜日）】
"柔らかい"場所から一定距離以内の場所はまた"柔らかい"のではないか。
そんな考えで、"柔らかい"場所からのダイクストラを行い、マンハッタン距離が一定以内なら”柔らかい”、それ以上なら距離に比例して"硬い"としてマップを作成。各”柔らかい”グリッドに光源を置いて、明るさで各地点の”柔らかさ”を表すようなイメージ。
見た目は良い。
が、ローカルテストの結果はむしろ悪化。
この案は一旦ボツ。
前日の結果の、計算式が少し意図と違っていたところを修正して再提出。
240位。みんなすごい。
【Pの値を正確にしていきたい。5日目。 （2/22 水曜日）】
今回、実際に掘っていく時の"力"は、マッピングで置いた数値を「硬さ推定値」として、その値をそのままPとするようにしている。推定値をより正確にすることでPをより正解値に近づけたい。
適当なseedで推定値の最小値・最大値を取得してみると、50-800くらいになっていた。それを10-5000の範囲に線形に引き伸ばしてみる。
最大値を5000まで引き伸ばすと、「硬い」判定の部分が多い影響で、全体の値がだいぶ上にずれてしまうので、色々な値を試した結果、10-1500くらいに引き伸ばすのが良さそうということになった。試し掘りはCの値に関わらず、力200くらいでやるのが一番いい図ができそう。こういう処理は重くなるかと思ったが実行時間にほぼ影響はない。これが「定数倍は軽い」というやつか。
あと、x = 199 or y = 199の試し掘りは、近隣の試し掘りが近いことが多いので代用できそう。ここは試し掘りしないことにした。これで40回くらい試し掘りの回数が減る。
【実際に掘りながらPを修正していく方針をとる。6日目。（2/23 木曜日）】
硬さ予測値に対して、係数をかけて定数を足して、修正したもので提出（係数と定数は、スコアが最小化するように、最適化探索をして決定）。
score 950万 順位:290位→240位
思ったより変わらず。
入力の生成方法をよく読む。
「パーリンノイズ」を勉強する。格子点を作って、その距離によってマッピングするというのは、あながち外れてもいないようだ。
値は、その後ロジスティック変換で0〜1になり、2〜4乗され、線形に10-5000まで変換されている。
これに着想を得て、「柔らかい」ところからのユークリッド距離の3乗が一定以内なら「柔らかい」として1か0かの値だけのマップを作ってみる。
↑できた図。
↑内部データをそのまま描画した図。
何か近い…けれど今使っている図とあまり変わらない。ちょっと使いにくいので保留。
マップをいじくるのはあきらめて、掘りながらPを修正していく方針をとる。一回で掘り抜ける状況が続く場合、推測マッピングと実際値がずれていると考えて掘る力を節約するモードに入る。一回で掘りきれなかった場合、次のマス以降の何回かの掘削では掘る力を割り増しする。ということをしてくれるクラス"class MrX"を作成。
提出。むしろ下がる。308位/822人
ビジュアライザを見ると、硬いところ(硬さ3000あたり)を通ってしまうとき、ぎりぎり30とか残ってしまった時に２回目もフルパワーで掘っているのが問題のよう。
修正。岩盤の「最大残りHP」を5000に設定して、一箇所にとどまる限りそれを削っていく。「最大残りHP」以上の強さでは掘らないようにする。
提出。ちょっとだけ良くなる。でもMrXがいないときの方がよかった。
301位。
【Xさんに頑張ってほしい（気持ち）7日目。 (2/24 金曜日)】
なんとかMrX（掘る力をリアルタイムで修正していくクラス）に頑張ってもらうしかない。
掘ってきた結果を入力値、新たな予測硬さ値を出力値として、実際の硬さ値との差を埋めていくようなMLP（仮）を想定してみる。テストデータで学習させて、、と思ったが実装が厳しそうで断念。特に成果なし。
【掘り直しよりも掘り抜きすぎるほうが問題かもしれない。8日目。（2/25 土曜日）】
ビジュアライザを見ていると、掘削結果として-600とか-1000とかが出ていることが頻回にあることに気づく。
-600ということは、Cが1だとしたら、600回掘り直ししないと起こり得ない損失なわけで、このあたりは改善できそう。
一発で掘れなかったときにもう一度Cのコストが乗せられるのがもったいないと思っていたが、Pが必要以上に高すぎるほうがもったいないのかもしれない。
・一発で掘りきれなくて、掘り直しするときには、勢いあまって-1000まで掘り抜いてしまわないように、同じ岩盤を掘り直す際は、n回目(n>=2)以降は元の硬さ予測値のn分の1のPで掘る。
・class MrXが力割り増しモードに入っていないときに、連続で一発掘りの状況が続く場合、オーバーキルと判断して、次回以降、一発掘りではなくなるまで、次のPをmax(C*2,予測値//(1+オーバーキル連続回数))にする。
score:837万 順位:290位/正解884人
200位台を奪還（？）した！
参加者は996人！ほんとにみんなすごい。
【力尽きた9日目。(2/26 日曜日)】
もうアイデアは出し尽くした感があり、細かくステータスをいじって何度か提出するが大きな改善はなし。順位は350位近くまでになってしまった。上位の人は自分の３倍(1/3)近いスコアをとっているわけで、一体何をやっているのか、解説が楽しみ。”試し掘り”の方針自体が違うのかも。
提出者数は1000人に達する勢い！自分の提出までの実装が重かったから参加者は増えないのではと勝手に思っていたけどそんなことはなかった。
夢の中まで考え続けて楽しい９日間でした。皆様お疲れ様でした。
↑最終結果。scoreは836万。気持ち程度に迂回してくれている。
【おまけ】
「Atcoder Heuristicのローカルテスタの使い方がわからない！」
と、調べたけれど、解説記事がほとんどないので、自分なりに書きます。
確かに、プログラミングコンテストで「ソフトの使い方がわかりません！」というのもなんだとは思うが、実際に自分が困ったので仕方がない。
参加者の多くがパソコンが得意だから困ることがないのだろうか？
大事なこと
1. 「Windows用のコンパイル済みバイナリ」だけダウンロードしても使えない。
2. READMEをちゃんと読む。
3. 自分の使用言語はローカルでも環境を構築しておく。
1.「 Windows用のコンパイル済みバイナリ」だけダウンロードしても使えない。
Q:「わーいコンパイル済みだー ダウンロードしてダブルクリック。
あれ？開かないな？ダブルクリック。あれ？ダブルクリック。あれ？あれ？」
A:綺麗なUIの整ったソフトが提供されるわけがなく、コマンドプロンプト（Macならターミナル）で操作する必要があります。ファイルを置く場所やらなんやらと色々決まっています。コンテストページから、「ローカル版」の方もしっかりいただいて、解凍しましょう。
2. READMEをちゃんと読む。
Q:「で、どこにファイルを置けばいいの？コマンドプロンプトとかわかんない。」
A:READMEに、どこに実行ファイルを置けばいいか、書いてあります。丁寧に実行コマンドまで書いてくれています。
コマンドプロンプトはwindowsならウィンドウズボタンの検索窓からcmdで検索すればいいよ！カレントディレクトリの変更はcdコマンドですよ！
3. 自分の使用言語はローカルでも環境を構築しておく。
Q:「実行したのになんかエラーで終了するんだけど」
A:その言語はローカル環境で実行できていますか？私の場合は、普段google colabかatcoderの「コードテスト」で実行していたので、今回は久しぶりのローカル実行でした。windowsではそもそもpython環境を作っておらず、macではanacondaがいつのまにか他の設定とconflictを起こしていて、どちらでもうまくいかずに戸惑いました。一回Hello worldでもローカルで実行して、動くことを確かめましょう。
自分の場合、結局MacにRustを入れて実行するのが一番うまくいきました。
Rustはcurlコマンドでは自己証明書のエラーで導入できず、配布ページから.pkgをダウンロードしました。conflictはエラー番号で検索して、解消させるコマンドを探して実行しました（コマンドの実行後、Macが唸り続けて2時間ほどかかって解消）。
心が折れかけましたが。
できなくて困っている方の参考になれば。cargo runできますように。
