# AHC018 リクルートハーフマラソン 2023/02/18 12:00 ～ 02/26 19:00

https://atcoder.jp/contests/ahc018/

## 1日目
## 所感
水路を作る問題。
複数の水源から複数の家に向かって、水路を整備する。
土地の硬さが異なって、硬い部分には体力を使う。
なるべく体力を使わないように水路を整備する。

家や水路は比較的柔らかい地盤に存在するっぽい。
掘削は、飛び飛びに掘っても問題なさそう。
ざっくり掘りながら、地盤の柔らかいルートを見つける問題っぽい。
スコアは消費した体力量なので、特にルートがまずいと解が無いというわけではなさそう。

地盤の硬さが 10～5000 なので、かなりの幅がある。
一回の掘削にベースの消費体力Cがかかって、これが 1～128 。
つまり、大局的に最小ルートを見つける部分と、個別の掘削の体力最小化がある。
地盤の硬さを適切に予測して、ルートと個々の掘削を最小化する最適化問題と定義。

よって、地盤の硬さの予測を真剣に考える。
ベースの濃淡はパーリンノイズで生成されるらしい。これはあるセルの近傍がなだらかな事が保証されてるっぽい。
濃淡を出した後、地盤の柔らかい所を重視して家と水源の場所を確率的に選ぶ。
盤面は200x200なので、あんまり広くない。

■問題文より
水源が存在するセルの岩盤を破壊すると、そのセルに水が流れます。
また、水が流れているセルの上下左右に隣接する岩盤が破壊されたセルにも水が流れます。
→つまりマンハッタン距離の問題。斜めは考慮しない。
→ん？でも濃淡側はある程度現実距離で生成されてそう。ここのギャップがひとつポイントかも。

全ての水源同士のペア・全ての家同士のペア・全ての水源と家のペアは、マンハッタン距離で
round(400/(W+K)) 以上離れていることが保証されます。
→びっくりパターンが無いだけで、普通に解くので良さそう。

やることがわかりやすくて、確率を真面目に解きにいかないとダメそう。
確率も、山が大きなパターンと細かなパターンがあって、そこの予測も大事そう。

地盤の柔らかい所が、10ちょっとのseedと、100くらいのseedとでも分かれる。
ベースの地盤の硬さも注意かも。

全部の地盤の硬さがわかった状態なら、厳密解出せる？
→出せそう。ただ、それを相対評価のベースとするのは違いそう。
→参考として、求めておきたい。

これ、伝家の宝刀二分探索をすると死ぬ問題で笑った。

家と水源は必ず掘るので、その分布を集計して初期パワーの最適化は図れそう。

勝ちに行くなら、ケース数を確認する？
パワーC毎のジャッジケースを確認して、ケース毎に上位との乖離を図るか。

地盤の硬さに応じて、周囲の地盤の硬さの変化は一定ではない。
柔らかいところは、周囲もなだらかに変わるが、硬い所は一気に変わる。

ルートは水源に近い家から考えるのがよい。
家からだんだん周囲の地盤の状況がクリアになっていくイメージ。
→これvisualizerイマイチだから、自作した方がいいな。しよう。
　各ターン毎の全体の硬度分布を可視化。

愚直解について、ある程度骨組みになるものを作りたい。
→水源からの予測したコストによるダイクストラで最短距離を取る。
→家の中で最もコストが低いやつからやる。(最小全域木的な)
→パワーはまずはルートを見たいので1000でいいや。(回数を削減)

実行時間5秒だし、わりと愚直計算でいいかも。
→実際よさそう。2秒くらいで結果出る。

visualizer作る。
あー、AtCoder上のwasmを使うから、html落として来てもあれ解除しないといけないな。
あった、CORS突破するやつ。
https://minerva.mamansoft.net/Notes/Google+Chrome%E3%81%A7CORS%E3%82%92%E7%84%A1%E5%8A%B9%E5%8C%96

うーん、wasm内で画像を作っちゃっているからいじれない。自分でjs書くか？
とりあえずinputをそのまま描画。あってそう。
掘削した部分の硬さだけ推測してみた。できた！適当に要素も圧縮した。

ちょっと硬さを周囲に伝搬させてみる。
みた。おお！面白い！しかもseed=0だと、スコア結構上がった。

いいじゃん。あとは間引きながらやる感じだな。
間引いてみたけど、これだとダメ。
勾配を意識できていなくて、すぐ周囲に抜け道があると思っちゃう。
こんな感じ。

初期硬度は低くしているが、逆に高くして、そこから下げていく方向がいいか？
勾配の推察が大事。少し硬いということは、その先はもっと硬い。
→少し先を倍の硬さで見積るとか？
→本当は判明した情報を元に勾配を作り直した方がいい。

ざっくり掘る時、斜め移動をさせない。
水源から近いところまで掘ったら、そこで止めて繋ぎに行く。

**TODO**
~~入出力作成~~
~~愚直解出力~~
~~バッチ処理(内部でシミュレータを持つ)~~
~~スコア計算(ベストを保存する機構)~~
内部情報を読んで、最適解を求める
家と水源の硬さを調査集計
暫定ジャッジのケース数をはかる
~~visualizerを自作~~
勾配の推察（簡易）
勾配を真面目に推察する
ざっくり掘りで斜めを禁止

## 2日目
02/19 10時、順位はこんな。

5マス飛ばし、斜め禁止でやったらこうなった。
やはり全体勾配を先に求めちゃおう。

全体勾配
家から飛ばし飛ばしで探っても、掘れないと実際の硬さがわからない。
頑張った向こうが柔らかいのか、硬いのかがわからないと、結構付近を満遍なく叩く
柔らかい所ならすぐ掘れるので、全体を叩いて具合を見るのが大事。
※予測の精度もわかりやすい。

とりあえず10マス間隔。ちょっと細かそうだけど一旦これで予測。
→際を調べるためには、一旦1回ずつ叩いて全体分布を求めてから、その上で際を求めに再度叩くのが良さそう。
こんな感じ。どうも角ばるなぁとおもったら、硬度はマンハッタン距離じゃなくて自然距離で変化するんだった。
自然距離にした。2段階にかけていて、直接硬度を編集しちゃうのと、ぼわっと広めに軟化させた。

seed=1が、愚直解に負ける。なぜ？
→平地のコストが20とかだから。初期解放から、一回に叩くベースラインを調整。

ん？seed=1のここ、硬い所で3000しかない。
もしかして、ベースが低いやつは最高硬度も低くなる？調べたい。

今んとこ、20sくらいかかるケースもあるけど、
時間で切ると作業中のスコアがブレるからまぁいいや。

試し堀りのラインを考える
今は100で固定している。でももっと少ないケースもある。20とか。
初期配置物の平均でやった。結構いい感じ。
こういうのがだめ。seed=7。powerが低くて、殆ど空いてない。
power200までのラインでやるか。
power100までのラインでこれ。相対75%。
左下なんかは、上手くルートを見つけれていない。試し堀りのコスト減が必要そう。

seed=9、初期配置が2つの最小構成で、一方が465なのでaveが高くなる。
基本的にどのケースも低い所は低い。初期掘削から試し堀ラインを決めるのは愚策では？
→やめて15固定にした。もっと低くしてもいいかも。一旦置き。

seed=0、ガリガリしちゃう。試し掘りで掘れた点の間をなだらかにしないといけない。
seed=1、こっちはざっくりルートとは違う所からいっちゃう。
どちらも、勾配計算ができていないから。勾配計算をちゃんとやる。
勾配計算、判明した事実に対して山登りで調整するのが良さそう。
勾配の傾斜に応じて、穴がありそうな地点を見つかれるといいかも。今だとseed=7の左上のスペースを見つけるのが難しい。

ただ、点数あげたいので試し掘りのコスト減からやる。
→まず15で全体をなめる、掘れなかった所は掘れた所の周囲だけやる。
できた。seed=0は結構コスト削減した。
逆にseed=9は見つけられず結構な痛手。
とはいえ、結構全体的に更新したケースが多い。

これ、全体を叩いてから、初期配置を掘削した方がいいのでは？

意外と愚直解がいい場合も多い。あとで確認する。
seed=20、こんなんもあるのか。これは水源全部空けないでいいかも。

勾配計算を山登りでする
うー、流石にしんどい。全然手が伸びない。個々の部品からやるかー。
~~上限下限の配列を用意~~
ベースとして、周囲10マスの平均をそのマスの値にする
→試し掘りを起点に十字を作って、下図の順番で埋める。
→雑に埋めた。seed=0。
これを初期値に勾配をなだらかにしたい。

ちょっとだけ高速化
各家のmaxよりもダイクストラ距離が大きくなったら打ち切り
→30秒のやつが1秒くらい早くなった。
マスの破壊時、距離をresetせずにダイクストラを破壊したマスから再開する。
→半分に。
非破壊時にダイクストラし直すのを、4ターン毎にした。
→1/4に。これでseed=0が6sくらいで終わる。スコアはズレるが試行回数が増えるので一旦こうしておく。

勾配ちゃんとしたいけど、スコアを上げておいたほうが違和感に気づけるので、試し掘り削減からやる。

**TODO**
内部情報を読んで、最適解を求める
家と水源の硬さを調査集計
暫定ジャッジのケース数をはかる
~~勾配の推察（簡易）~~
勾配を真面目に推察する
→山登りで勾配を調整する
~~ざっくり掘りで斜めを禁止~~
~~全体分布を測るための試し掘りのコスト減~~
→中空(周囲は硬いが中は柔らかい)の可能性を模索
~~試し堀りのラインを初期解放から設定~~
平地に対する最高硬度の対応関係を調査
~~試し掘りの結果から平地をなだらかにする~~
試し掘りと初期掘削の順序を考える
~~愚直解がいいseedを確認する~~
硬い所の水源を諦める
試し掘りが不要な部分をやらない

## 3日目
02/20 9時半、順位はこんな。Psyhoさんがわりと仕上げて来てる印象。

試し掘りの削減をする
家から最寄りの水路までの短形内を試し掘りで良さそう。
家と水源のペアを作り、その間を試し掘り。
一定いないの硬度しか出てこないならOK。その家を仮想水源にする。
繰り返し実施して、全ての家が仮想水源になればOK。
仮想水源にならないときは？
→中空の模索で回収するので、今は突っ込んでしまおう。

うーん、今の一括試し掘り、結局どこかで捨てるし作り直すか。
各家から水源への経路探索。
個別にやるより、全体で一気にやる方が良さそう。
1.純粋距離に応じて最適な水路を敷く
　→まずは最小全域木を組むまででいい。あとでジャンクションは考える。
　→確度が低いところは硬度10でいい。硬度10に戻るよう、勾配計算をする。
2.その水路を水源から飛ばし飛ばし試し掘り
　→家から考える。(水源は使わないものもあり、水源自体を掘らないこともある。)
　→確度が低い所を掘る
3.試し掘りから周囲の硬度の確度を決める
　→確度、布をかぶせて押しピンで止めるイメージ。
　硬度が柔らかければ柔らかいほど、しっかり確度が出ている。(周囲の変化が少ない)
　 実は間隔空けるよりは、勾配がキツい部分を正確に求めるのも大事。
4.ルートのコストが高そうな時、確度の低い別ルートで水路を敷く
5.繰り返す
試し掘り高度化と呼ぶ。

結構下の値(10,11,12,13)は厳密に求める価値がある。(傾斜の傾向を察知できる)
10は、下がないからやりすぎだけど、11であることを見つけるのは価値。
一回統計取るか。seed毎の統計を求めるプログラムを書く。
書いた。勾配の変化の度合いを調べて、8%～116%まで分布。(変化のmaxでなので個別は0%～ではある)
元のマスの硬度によらず、変化が激しいケースはどのマスの最大変化も大きく、逆は小さかった。
最小8%のケース。seed=4。全体がボワッと広がっている。
最大116%のケース、seed=92。変化が強すぎて極所的に硬い。

基本は変化が鈍いと仮定して、徐々に上限上げるのが良さそう。
ある方向が上がるなら、ある方向は下がる。
勾配傾向を見るために上下左右を叩くのはあり。
勾配変化は10～50付近がきつく、数字が大きくなると緩やかになる様子。

試し掘り高度化をする
要素に分ける
・調べる最短路を導出する※あとで全体最適化
→最短路は直角じゃなくて、斜めに移動したい
→同値の場合自然距離を短くする方にすすむ　できた。
・最短路に対して試し掘りの箇所を決める
→とりあえず5マス毎に掘った
→スコア更新がちょいちょい出た
→ルートが構築できなくても1回で完了しているので、高度化が必要。
・試し掘りの結果から、勾配を予測する

今回、間隔を空けて掘るより、前後を正確に掘って傾きを求めるのが重要なのが面白い。

**TODO**
内部情報を読んで、最適解を求める
~~家と水源の硬さを調査集計~~→そもそもの勾配を集計可能にした
暫定ジャッジのケース数をはかる
勾配を真面目に推察する
→山登りで勾配を調整する
→中空(周囲は硬いが中は柔らかい)の可能性を模索
~~平地に対する最高硬度の対応関係を調査~~→そもそもの勾配を集計可能にした
~~試し掘りと初期掘削の順序を考える~~→試し掘り高度化に内包
~~硬い所の水源を諦める~~→試し掘り高度化に内包
試し掘りが不要な部分をやらない=試し掘り高度化
→試し掘りの結果から勾配予測
→勾配を加味してルート構築
勾配変化を仮定して考える

## 4日目
2/21 9:30時点。

仕事で何もできないが？考察だけでもしておく。

山登りでの勾配調整
こんな感じで縦横に分けて持てる。
ただ、この持ち方だと横変化と縦変化とで、勾配差異がなだらかになるように近似しにくいな。
あるマスから見た時、上下左右の勾配からその差異のMaxをgridで保持して、これの最小化をする。
最小化のためのスコアは、単純合計か2乗和か。単純合計のが良さそう。(極所的に変化を大きくする)

max-min、一番傾斜のきついseed=92、硬度10～25だと以下。最大で硬度42=307%を確認。
0.20,0.45,0.83,1.08,1.07,1.40,1.44,1.76,1.83,1.79,1.75,2.10,2.09,2.09,2.21,2.48

aveからの差だと、最大で190%、seed=92、硬度10～30がこれ。
0.13,0.25,0.52,0.59,0.55,0.72,0.76,0.94,0.93,0.88,0.95,1.03,1.05,1.04,1.12,1.20,1.15,1.18,1.08,1.14,0.95

推測時は、全力で最小の硬度10になるよう、勾配変化を調整する。
掘れた硬度をアテにするのではなく勾配をアテにする。
そうすると、実は家も最初に全部空けるのは違っていて、最初に空いた家から勾配を上手く求めた方がいいかも。
水源も空くなら空けたほうがいい。
→家と水源はそれぞれ空けていって、最小で空いたやつから勾配を求めにいく。

データ生成時は小数点以下も持ってるので、予測硬度も同様に持った方がいい。

動きも見やすいから、1マスずつ進むのを考える。飛ばして平地を探さずに、勾配変化を察知してルートを変える。

## 5日目
11:30。まだそこまで詰まってきてない。

山登りでの勾配調整
→1マスずつ進む。掘れたマスの値のみでこんな感じ。
勾配変化を無邪気にやると、どんどん倍率が発散してやばいことになった。
算出元の距離を入れて、距離が近いやつを優先するようにする。
あー、左右の勾配と上下の勾配混ぜるのだめだ。完全に頭バグってる。

これをやろう。確定した勾配に応じて、仮の値を入れる。
仮の値から勾配が不自然にならないように10に近づける、で。

## 6日目(祝日)
11:00
Psyhoさんが仕上げてきた感じがある。

勾配予測つづき
勾配の縦横で別評価にした。
seed=3、探索の様子がよくわかる。
まだ勾配が筋のように入ってしまう。予測元からの距離に応じるので、縦横変化だけ反映される。
ぼかす処理が必要。
seed=3、ぼかした。いい感じ。
seed=1
seed=0、かっけぇ！

いまだと壁の向こうが空いているかわからないので、少し飛ばして向こう側を見るのが大事そう。

現在、100ケースでローカル比Ave=54.8%。悪く無さそう。
0=0.4177 K=9 C=2 s=386118 T=20361
1=0.2371 K=2 C=1 s=106452 T=3000
2=0.2708 K=4 C=32 s=1079038 T=16887
3=0.8555 K=1 C=1 s=40259 T=2839
4=0.6248 K=6 C=1 s=131585 T=3603
5=0.5502 K=9 C=128 s=455219 T=1788
6=0.3548 K=7 C=4 s=730330 T=18515
7=0.4658 K=6 C=2 s=256439 T=8864
8=1.0000 K=2 C=4 s=40914 T=1682
9=0.3955 K=1 C=64 s=158412 T=1172

(以前の全体試し打ちで72.8%)

うーん、勾配予想、やはり速度だけでなく加速度までもとめないとよく無さそう。
結局ある程度硬い所を掘って初めて諦める動きになる。
→山登り勾配調整へ

今日は動きが多いので、20時時点。

試し掘りを飛ばし飛ばしする
まずは最短ルートのうち、予測コストが小さいマスから叩いてみた。
蟻コロニーっぽい挙動になった。seed=2

予測コストが小さいマスだけだと、一度掘れちゃうと周囲を掘りまくるので、
掘れた周囲は制限をかける。
seed=3、いいかんじ！
seed=4、スコア低め、45%。
seed=79、もっと低いやつ、27%。

ざっと回して79%！おお！
もとの全体叩きが66%まで落ちたからかなりいい感じ。

パワーそろそろ整えてみる。
→あんまうまくいかない。やはり勾配を適正にするのが一番効果的。

高速化と、勾配の山登りが必須。
ある程度したら力技で突破するでもいいけど。

高速化
・固定の家に対してのみ距離を再計算。
・掘れなかった時、あまり大きく変化してないなら距離の再計算はしない。
→これでとりあえず倍の速度になった。まだ、重いやつは30秒かかる。

ざっくりルート、山を超えてから考えた方がいい場所に対してかなり無駄に叩いてしまう。
→いくつか開通済を通ったら打ち切る？
→根本的に勾配が読めてないのが問題。山登り仕上げる。

そろそろ提出しておきたい。
→8割完成で打ち切りはあり。あとはなぞるだけなので更新不要。
→8割完成してたら、時間切れで愚直やるのもそこまで破綻しなさそう。
→とりあえずこれやるか。

**TODO**
内部情報を読んで、最適解を求める
暫定ジャッジのケース数をはかる
勾配を真面目に推察する
→山登りで勾配を調整する
~~→中空(周囲は硬いが中は柔らかい)の可能性を模索~~
試し掘りが不要な部分をやらない=試し掘り高度化
~~→試し掘りの結果から勾配予測~~
~~→勾配を加味してルート構築~~
~~→1マスずつから飛ばし飛ばしにする~~
勾配変化を仮定して考える
~~家と水源をうち単一起点でのmap把握~~
~~硬度予測は不動小数点で持つ。~~
時間が無くなったら貪欲にゴールする

## 7日目(金曜)
11時時点。
　

2000件くらい回して、エラー無いのでよい。

8割ドメ対応
→した。が、そんなに早くならない20%upくらい。

高速化
いつかのAHCみたく、全然時間間に合わない事態は避けたい。
まずは計測する。
した、ほぼほぼコスト計算のダイクストラ。ここの呼ぶ回数を減らせばその分減る。
→ダイクストラを PriorityQueue でコスト低いものからに探索。これで40%削減。
→結局無駄な盤面叩きを減らせば自然と早くなりそう。勾配予測に戻る。

power調整して、Cに応じてバッファ増やしたら露骨にスコアあがった。
0=0.8024 K=9 C=2 s=201006 T=6186
1=0.7371 K=2 C=1 s=30485 T=1063
2=0.7504 K=4 C=32 s=389459 T=7158
3=0.8411 K=1 C=1 s=20256 T=816
4=0.4618 K=6 C=1 s=178046 T=5751
5=0.9625 K=9 C=128 s=260221 T=1705
6=0.4281 K=7 C=4 s=605228 T=12099
7=1.0000 K=6 C=2 s=101683 T=3557
8=1.0000 K=2 C=4 s=27794 T=934
9=1.0000 K=1 C=64 s=59707 T=480
10=0.7990 K=9 C=32 s=353483 T=7052

うーん、87%が出たけど、これは元がよくなさすぎたかも。
全体叩きに少し入れてみるか。いま60%まで落ちてる。
うーん、元に入ってたやつでベストだった。
スコア上がった分、速度も上がった。seed=6が17sかかっているのでこいつを最後間に合わせる。
調整して、全体たたきを58.6まで下げて、87.6%がでた。

**TODO**
内部情報を読んで、最適解を求める
暫定ジャッジのケース数をはかる
勾配を真面目に推察する
→山登りで勾配を調整する
勾配変化を仮定して考える
時間が無くなったら貪欲にゴールする
~~8割ドメ~~
~~powerの見直し~~

## 8日目
9時時点。今回kiriさん大爆発。
13時、tekさんだ。72%か。

案：めっちゃ賢くやるなら、この硬さならこの傾きだからこのルートは無理、みたいなのを予測して叩けるといい。

あれ？今予測値の少数点以下切り捨てちゃってるけど、これ四捨五入した方が正確だな。

時間、手元で6.7秒があっとこサーバ上で9.4秒。ざっくり1.5倍かかるので、3秒ちょいに収めたい。
(今回はメモリの使用頻度が低いので、手元と大きく差がないっぽい。)

確度が高いマスは、あまり予測値から下げて叩かないでいい。
→だめだった。

勾配予測、いい加減やるぞ。
→とりあえずターン毎になだらかにするようにした。
→90.57%。これで上がるのまじか、ちょっと時間かかるようになった距離ダイクストラの半分くらい。
→必要な所だけかける。じゃないと全体的にぼやかしてしまう。

→必要な所だけかけると悪化した。もとのまま、diffが小さいなら打ち切りにした。

序盤はまだ十分伝搬してないせいか、何度も均すとスコアがあがる。
2回がいいっぽい。どうせなら行きと帰りで逆からかける。→悪化した。まぁいいや。
→ちゃんと山登りで合わせにいく。

そろそろ提出しとくか。今7秒くらいかかっている。
やはり距離ダイクストラをどうにかしたい。
暫定最短ルートは持ってるから、それをもとにざっと上限だけ決めちゃうか？
→早くならなかった。ちょっと早いこともある？お守りとして置いとく。
→どこからダイクストラされたか記憶しておいて、差分だけ更新？
→うーん、途中だけど早くならなそう。

ざっくり叩き、Cを考慮してなかった。
→微減？よくなるやつもある。やらない。

20時提出前
提出後
うぐー、思った以上に遠い。全く上位削れて無いし。
実行時間は 4911msなので、これが限界かも。

やはり先に勾配を求めにいくか。
・家から最寄りの水源までの最短距離の矩形内をざっと叩く
　→まずは家と水源を囲う、少し広めの矩形内をざっと叩く
　→あとで段階的に叩くようにする
・掘削できなかった所を少し硬めのエリアとして設定する。
・家から最短路を引いてみて、横切る硬めのエリアについて勾配を求めにいく
・あとは今のざっくりルートにまかせてみる

現在地
手元で、87.37%、以前の全体叩きが49.28%。
手元のやつを70%代まで下げるのをまずは目標にする。
やはりスコアが小さいケースを上げきるのが大事。
うーん、あがくか。ケース数特定しにいく。
K=1、おっと、WAだと点数でないのか。
とりあえず4ケースありそう？TLEってなんだ？あ、ローカル用の設定で普通に時間切れっぽい。
K=1でこれ。5ケースあるから、平均50%を切ってる。
やはり小さいケースで取れてない。

seed=3、手元bestが17037、これを更新する。

C=1の時、60%×8ケース？9ケースだった。じゃあやっぱりだめ。

**TODO**
内部情報を読んで、最適解を求める
暫定ジャッジのケース数をはかる
勾配を真面目に推察する
→山登りで勾配を調整する
勾配変化を仮定して考える
~~時間が無くなったら貪欲にゴールする~~
ルート変更のラインを考慮した叩き
予測値を四捨五入して使う

## 9日目(最終日)
11時、強い人はちゃんと詰めてくるなぁ。

無駄な叩きをやめる。
→適当に減らした

硬い可能性のある所は、直前と連続で空ける（傾きを出す）。
→できなそう。

謎のWAが出る。うーん、ケース7～9くらいで落ちるっぽい。それ以外はACしてるのに。。。
あー、0で割る可能性あるな。直す。
なおった。うーん修正範囲が影響したのかわからんけど良かった。
30Gはのった。

はじめに全体のうち必要そうな所だけ叩く。
空いた所から離れる毎に1.1倍ずつ硬度を上げて全体外観を作る
→これやる。そもそも制限時間足りない問題もある。
→制限時間来た時、未掘削エリアの硬度をちょっとあげておく。
→時間考慮で84.1%
ちゃんと上がる。うぅ。。。もっと速度上げれば上がりそうだが。。。

seed=3、手元bestが17037→15636にはした。全体たたきが47.15%→46.39%
水源は繋いでから空けるやつやる。
→あかん、なんか変な影響あるからやめ。

最後時間の調整だけして提出。う、点数落ちたけど仕方がない。終わり。

**TODO**
内部情報を読んで、最適解を求める
暫定ジャッジのケース数をはかる
勾配を真面目に推察する
→山登りで勾配を調整する
勾配変化を仮定して考える
ルート変更のラインを考慮した叩き
予測値を四捨五入して使う
~~無駄な叩きをやめる。~~
硬い可能性のある所は、直前と連続で空ける（傾きを出す）。
水源は繋いでから空ける。

## 反省会
優先順位間違えた。
全体でそれとなく把握していくより、ちゃんと1手1手で得られる情報を使うことを重視しないと、
実装量に対して点数比のでかい小さいケースで大損をする。
勾配予測もずっと放置してしまった。が、これは元気が無くて手が出せなかったかも。
そういう時に変に粘って手の動くやつをやるのがよくない。

上位は12×12の格子状の代表点を取って、それをもとにルートを決めてたらしい。
シンプルだし、それで点が出るのは気が付かないといけなかった。。。
https://twitter.com/kiri8128/status/1629846228392620032
特に勾配の傾きとかはいらなかったっぽい。
CNNとがガウス過程？が使えるらしいけど、それらは2p以降の人が多かった印象。
yos1upさんがガウス過程で高順位。
https://twitter.com/yos1up/status/1629827983187013632
Psyhoさんが200msしか時間使ってない。めっちゃコードも短いので、
アルゴリズムでどうにかしたっぽい。

みんなoptunaすごい言ってる。
流石に使うかぁ。