RECRUIT 日本橋ハーフマラソン 2023夏（AtCoder Heuristic Contest 022）265位でした. 初めに思いついた解法を3つ紹介し, その後何を考察したか時間経過ごとに長々と書きます.
最後に黄perf以上取るために何がAHCに必要なのか考えました.
解法①
placementパート いい感じに設定します.
meassureパート
それぞれの入口iの周囲9マスに対し, それぞれ1回推定する. (m_P[i][0][0] ~ m_P[i][2][2])
入口i, 出口j とすると, sum[i][j] = pow(m_P[i][0][0] - P[Y[j] - 1][X[j] - 1], 2) + ... + pow(m_P[i][2][2] - P[Y[j] + 1][X[j] + 1], 2)を計算し,
sum[0][E[0]] + ... + sum[N-1][E[N-1]]が最小となるEを求める. (最小コストフロー問題に帰着できると思っています。(AtCoder Libraryのを使う))
解法②
placementパート 一点のみを1000にし, その他は0にする.
meassureパート
それぞれの出口jから1000までのdy, dxを保存する. (dy, dxのサイズはN)
入口iからdy, dxを推定していき, 1000となる確率が高いものを答えとする.
解法③
出口に8bitの2進数を設定します.この2進数は出口ごとに異なる.
n番目のフラグ(0<=n<=7)ごとにdy[n], dx[n]を設定する.
placementパート
出口jに1010000と設定すると, (Y[j] + dy[5], X[j] + dx[5])と(Y[j]+dy[7], X[i]+dx[7])のPをMax_P, その他はMin_Pとする. (Max_P, Min_Pは1000, 0などマップの最大値, 最小値).
meassureパート
すべての入口iはそれぞれのdy, dxをm_N回推定する. (m_Nは10000 / (N * 8)で12~20となる)
同じところをm_N回推定すると, その平均値の分布の標準偏差が S / sqrt(m_N) となりSが大きくても正解できるようになる.
m_N回推定後, そこがMin_PかMax_Pかを判定する. 出口にごとに異なる2進数を設定しているので, ここを正確に判定できると間違えは0になる.
ひどい解説なのでわからないところがあれば言ってください！
考察
・1,2日目
解法①を実装し結果を見るとS >= 400でボロボロだったので, 設定するPを0, 1000にする案を考え, 解法②が思いつきました.
・3日目
解法②を実装し結果を見ると, 推定回数がN * Nとなり0か1000を区別するのに, 1~2回しか推定できないため, (実装は10000回上限を忘れてた)不可能だと判断し, この解法を捨てました. 設定回数を削減しようと考え, 入口ごとにN回するのがダメそうななので, 8回(logN + 1)にすると, 0か1000を区別するのに, 12~20回推定できるため良さそう. こんな感じで解法③を思いついた.
・3~最終日
入口ごとにN回 → 8回が天才だと思いましたがダメでした. この解法はplacement_costが5 * 10^7とかになり, いくらwaが少なくても満点には届きません.
placement_costを少なくするため, 色々しましたが, placemnt_costを下げるとwaが多くなり, トレードオフだなと思い, 最終日までここに固執しました.
・終了後
1位の人などは解法②を採用してました. (https://twitter.com/Jiro_tech15/status/1693203060821225548)
僕のように解法③に固執していた人は同じような感想を持ってました. (https://twitter.com/through__TH__/status/1693206079679910082)
黄perf以上を狙うため何が大事か
まず長期(1~2週間)コンテストを振り返る
・AHC013 90位
・詳細な解法提案をせず, コンテスト中盤でパラメータを調整 (大まかな解法はあっている)
・AHC014 138位, AHC017 198位
・詳細な解法を思いつかなかった (大まかな解法はあっている)
・AHC016 102位, AHC018 153位
・詳細な解法提案に固執, 他の大まかな解法すら考えていない (大まかな解法が違う)
・ AHC022 265位
・詳細な解法提案に固執, 他の大まかな解法を知識不足で捨てる (大まかな解法が違う)
上3つに, はまらないようにしましたが, 新しいパターンで失敗しました. AHC017と同じ流れかと思っていた.
それぞれの大まかな解法A, B, Cがあって, それぞれに詳細な解法a, ,b cが存在する.
Aaである程度のスコアをとれるとAb, Acを思いつくように時間を割く.
思い直してBaを考えるがダメそう. ここでBb, Bcを思いつくように時間を割くと今回では正解する. でも, 上から２つにはまるかもしれない.
今回の問題でいうと,
問題観察力 : Sが重要そう, score関数よりmeassure_costとplacement_costが重要そう, 入口iが独立している(?)など
解法提案力 : 上を意識して解法を考える.
とすると, プログラミング能力, 問題観察力, 解法提案力がある程度あれば青perfはとれそうですが, Bを捨てる判断や,正解のAb, Acが存在するなど何かしらの嗅覚(?)なのか, 経験値や知識なのか未だに何が必要なのかわかってないです.
解法②は最初からうまくいったのか, 途中からうまくいったのか, 解法③は思いついたけど捨てたのか, 捨てる理由は何なのか知りたいです.
また, 長期AHCは月1で開催してほしいです!!