はじめに
RECRUIT 日本橋 ハーフマラソン 2023冬（AtCoder Heuristic Contest 018）に参加した際、リアルタイムで書いた日記です。ヒューリスティック に参加するのは3回目ですが、多分ランダムな解を提出しただけとかそんな感じなのでほぼ初めてのようなものです。精一杯頑張りたいと思います。
ブログを書くのは正真正銘初めてです。間違い / 勘違いや表記揺れがかなり見られますが、日記の醍醐味ということで...
初日（17 : 00 ~）
問題文を見てきました。概要としては、『岩盤を掘ってすべての家が水源までつながるようにしよう！岩盤の硬さは知らんけど』みたいな感じです。岩盤の硬さは見た感じランダム。ランダムじゃない場合は隣の岩盤がやわらかければ、この岩盤もやわらかいかも、みたいな感じです。
この問題は『家と水源を結ぶのに必要な岩盤の数の最小値』と『岩盤を壊すために必要な回数の期待値の最小値（とそのためのパワー）』の二つを求めることになりそうです。
とりあえず適当に実装しようと思いましたが、なんかサンプルコードが与えられているみたいなのでそれをいじって正の得点を得てきます。ほな。
提出してきました。パワーが100になっているところを5000にするだけでした。ただ、サンプルコードが全部わかるような頭になっていないので、以降は自分でコードを書きます。変数に名前をつけるのが苦手なので、そこはサンプルをパクります。
アルゴリズム コンテストのほうには入力と出力（答え）のセットが例としてついできますが、ヒューリスティック のほうにはビジュアライザというものがついてくるそうです。入力と出力を可視化できますよってことだと思います。
....これ表示の模様を見る限り、完全なランダムじゃないですね。運ゲー 君になってしまうので当たり前といえば当たり前か...。
このときにビジュアライザの入力に対応してプログラムを作成して提出したのですが、ビジュアライザの入力と実際の入力が異なることに気づいていませんでした。皆さんも気をつけよう！
隣り合う岩盤の頑丈さにある程度の関連性があるとはいえ、一旦完全にランダムだった場合を考えます。『岩盤を壊すために必要な掘削回数の期待値の最小値（とそのためのパワー）』は C ごとに dp / 動的計画法 で求め、家と水源に関しては各家から一番近い水源に最短距離で掘り進むことにします。switch文を初めて使ったのですが、そのせいでWAになりました！わーい。
ビジュアライズ結果 (seed = 0) , cost = 600815
ペナルティとして30分間は提出できないので その間にもいろいろ考えます。何も各家と水源を直接つなげる必要はなく、その時点で出来ている道につなげば掘削回数を減らせそうです。
この時点での絶対得点は 13,437,966 点、相対得点は 19,388,644,841 点、順位は 46 位 でした。
ビジュアライズ結果 (seed = 0) , cost = 506281
ビジュアライザを見ると、色の薄いところが濃いところに比べて多く感じます。もし岩盤がやわらかいところが多いならば、完全にランダムなときより少ない体力で岩盤を壊せるかもしれません。岩盤の頑丈さの入力生成方法を元に、それぞれの頑丈さがどれくらいの頻度で現れるのかを調べてみた結果が以下です。
頑丈さ : 現れる頻度
10 : 1520097
...だいぶ偏っているようです。（実際の生成方法と自分の解釈があっているという前提になりますが、）どうやら既に与えたパワーを元に今から与えるパワーを変えた方がよさそうです。変えた結果、seed = 0 のコストは 506281 -> 503302 に減少しました。
そんなに変わりませんでしたが、一応提出します。絶対得点は 11,966,235 点、相対得点は 21,680,311,917 点、順位は 32 位 でした。結構順位が上がりました。ビジュアライザはいろんな seed 値に対して行った方がよさそうです。
二日目
順位を確認してみると 70 位になっていました。
初日はその岩盤を破壊すると決めたらすぐに破壊したのですが、破壊する岩盤を決めてから後でまとめて破壊しても同じなので、そのようにコードを変更します。
家と水源までつながっている岩盤（水路と呼ぼう）との距離が最短になるように掘っていますが、最短になる掘り方は複数あります。なので何らかの形で評価値を求め、それに従って掘り方を決めることにします。各ルートの評価値を、そのルートで掘ったときの各家から水路までの最短距離の合計としておきます。 44位まで上がりました。やったぜ。（後日追記 : ビジュアライズ結果を撮り忘れてしまった...）
今回の岩盤は、隣合う岩盤の頑丈さにはある程度の関連性が見受けられます（パーリンノイズってそういうものらしい）。硬い岩盤の隣を掘るときは最初からパワーを込めてもよさそうです。
この日は以上で終わりました。実装できそうなのが思いつかなかったんだからし ょうがない。
3日目
二つの岩盤の距離が近ければその頑丈さもおおよそ予想できそうというのが昨日の推測でした。またスタートと目標地点さえ決めれば通るルートは自由です。ならば、少し先の地点に調査隊を送り込んで岩盤の硬さを調べてもらい、硬い岩盤を避けるようなルートを通れば消費する体力は少なくなりそうです。
掘る道が直線であればそのまま真っすぐ進みますが、L字であれば 2 方向に調査隊を送り先に返ってきた方に進みます。
ビジュアライズ結果 (seed = 0) , cost = 380378
画像の右下に分かりやすく調査した残骸が残っています。初日のビジュアライズ結果と見比べてみると左側の硬い岩盤を避けていることが分かります。
いざ提出してみたら 3 個のテストケースで WA を吐きやがりました。本採点では 3000個のテストケースを処理するので 150 ~ 200 個の WA が出ます。もちろん、どこで間違っているかを探さねばなりませんが一目で分かるわけがなく...。ビジュアライズでエラーを吐く seed 値を見つけるところから始まります。6 % の旅へいざ。
見つけました。右の画像は掘削地点の仮組で、左の画像は調査を行って実際に掘った岩盤です。真ん中あたりにある家から『右に行って下に進む』という処理になるはずが『下に行って水源に向かう』という処理になっています。真ん中の家の到着地点は水源になっており、あり得るルート上に他の家からの到着地点 = 合流地点があれば一旦そこに向かうのですが、合流地点が二つあったようです。各マスごとに合流地点かどうかのフラグだけを持っていたので、i 番目の道の掘削予定地かどうかのフラグを持てば判断できそうです。勝ったなガハハ。
ビジュアライズ結果 (seed = 30)
負けました。1 個のテストケースで WA が出ました。2 % の旅か...。6 % の旅は結局 30個調べることになったので、今回は100個ぐらいでしょうか。
4日目 ~ 5日目
一つ一つ出力させてビジュアライザにぶち込んでエラーメッセージが出るものを探すのが非常に面倒な作業なので、水源からDFS / 深さ優先探索 を行ってすべての家にたどり着くかチェックして足りなければエラーを吐くという関数をつけました。まあ 200個調べてもエラー吐かなかったので諦めることにしますけど。
コンテスト終了後追記 : 3日目で見つけたミスと似たようなものでした。家 A →地点 B → 地点 C → 水源 D と向かうとき、処理する順番の間違いにより地点 B に向かわなくてもよいことになっていたようです。
いつの間にかコードの量が 5700 行になっていました。そのうち5000行が埋め込みなので、実質的には700行くらいです。量が多くなると整理したいのですが上手な整理の仕方が分かりません。
そんなこんなしているうちに順位が3桁になってしまいました。次の手を考えるとしましょう。家から水路までの最短距離とそのルートを求めるダイクストラ 法を用いることにします。現在いる地点からちょっと先を掘ったけど岩盤を破壊できなかった場合、該当箇所とその近辺のコストを少し上げます。そうすると別のルートを探してくれるかもしれない、という感じです。（伝わっているか不安になっているの図）
とりあえず、やってみた結果がこちらです。
ビジュアライズ結果 (seed = 0) cost = 380378 -> 273619
左の画像が昨日までのコードでの結果、右の画像がダイクストラ 法を使った結果です。右上のほうに違いが顕著に表れています。コストも大きく減りました。いざ提出！
ダメでした。以前のコードは "WA" を吐きやがったのでテストケースの絶対得点（の合計）が分からないですが、相対得点が2,000,000,000 点ほど下がっていました。順位にして50位分です。(113位 -> 169 位）
今回のプログラムでは掘削する回数が増えてしまい、Cが大きいとコストが増えてしまうようです。そのようなときの（雑かもしれないけど効果的ではある）対処法、場合分けを試してみるとしましょう。C が小さいときはダイクストラ 、大きいときは以前のプログラムという風にしてきます。これは勝ったべ。
ダメでした。絶対得点は下がりましたが、相対得点も下がりました。いろいろビジュアライザを見ていると、気になるものを見つけました。
ビジュアライズ結果 (seed = 8) cost = 44080, 209774
えー、右がダイクストラ を使ったものです。コストが4.5倍、つまりこのテストケースの相対得点は 4.5分の1です。多分まずいです。
おそらく、『該当箇所とその近辺のコストを上げる』という処理における近辺の範囲が小さいかったことに起因しそうです。遠回りするよりも突っ切った方が速いと思わせてしまったようです。入力生成方法的にはこの『色が濃い範囲の広さ』もテストケースごとにランダムなので、入力から伺い知ることはできません。どうにかしてきます....。
コンテスト後追記 : 局所的に頑丈さが小さい / 大きい箇所に引っかかった結果、悪い方向へ進んでしまったものと思われます。
どうにかしようとした結果 順位が 5 つだけ上がりました。焼石に水とかいうやつです。前のやつを提出しなおすことにして今日は寝ます。寝ないと口内炎 が 2 つできたりとかしますから、皆さんも気を付けてください。
6日目 ~ 終了
相変わらず WA が出るわ、なんか別のエラーも出始めるわでなんだかよくわかりません。尻切れトンボ感がありますが、別にやることがあるので（実質初めての）ヒューリスティック コンテストへの挑戦はここで終了することにします。無念...
解法
1. 準備
頑丈さの出現頻度をだいたいで計算します。noise = randf(-1.0 , 1.0) と仮定し入力生成法に従って計算するだけです。計算しといて埋め込んでおきます。
パワーを合計で i 与えても壊れなかったとき、次に与える最適なパワーを計算します。消費する体力の期待値が最小になるものを dp / 動的計画法 で求めればよいです。
2. ルートの仮組
各家から水源までのルートを仮に決めます。
K 個の（始点, 終点, 距離）の組を持っておきます。始点は K 個の家で、終点は水が存在するマスのうち始点からの最も距離が小さいマスです。最初は最も近い水源です。
距離が最も小さい始点と終点の組について、( x 方向に移動 -> y 方向に移動 -> x 方向に移動 ), ( y 方向に移動 -> x 方向に移動 -> y 方向に移動 ) のどちらかかなるルートのうち、K 個の距離の総和が最も近いルートを選択します。
各マスにはどのルートが通る予定かの情報と、終点になっているかの情報を持っておきます。
3. 実際のルート決め
仮組された一つのルートについて、途中に別のルートの終点がある場合は 2 つに分割します。(地点 A -> 地点 B を 地点 A -> 地点 C , 地点 C -> 地点 B に分ける。)
(sx, sy) から(gx, gy) に向かうとします。(sx < gx, sy < gy)
sx + a と sy + a を交互に掘って岩盤が先に壊れた方向に掘り進め、始点を更新します。gx < sx + a となる場合は最短となるルートを適当に掘ります。
4. 岩盤の掘り方
最後に岩盤を掘っていきます。隣接する 4 マスのどれも掘られていない場合は準備で決めたパワーに従って掘ります。
そうでない場合は各岩盤の頑丈さの下限と上限から推測される値の平均値で一回掘ります。C が大きいほど上限に近づけると掘り直しが少なくできそうでした。頑丈さはどれも一様に出るわけではないので準備のときに埋め込んだ値を使います。
岩盤が壊れなかった後の一回はちょっとだけパワーを弱めて掘り、以降は準備したパワーで掘ります。
暫定テスト : 相対スコア 20,901,814,958、順位 265 位
システムテスト : 相対スコア 1,184,581,986,143、順位 312 位
システムテスト の結果が暫定テストに比べて悪くなりました。暫定テストは 50 ケースだったので、上振れ下振れが大きくなるようですね。ローカル版のビジュアライザも用意したほうが良いのかしら。機械音痴なのでこういうのよくわからないんですけど。
それとシステムテスト の方でも WA は出ていました。seed値が公開されたらその理由を探ってみたいと思います。
