[AHC022] A - Exploring Another Space

[Q] https://atcoder.jp/contests/ahc022/tasks

暫定162位でした。絶対スコアは7.0億。
絶対スコア3.3億のときに260位くらいでした。

問題の誤読
・計測コスト = 100*(10+∣y∣+∣x∣)
質問でなげる|y|であって、座標上のyと勘違いしました。
終了前日の8/19夜にわかり、12時間チャレンジです。

考察
・盤面を4分割、値を3通りに分ける。
だいたい、{"500 - S*3", "500", "500 + S*3"}の値を割り振ります。

seed0 S=36

1. まず自分が0,1,2,3のどのエリアにいるかを判定。

2. 例えばエリア1とわかった場合。ワームホールのx座標はエリア0とエリア1の境目が分かればいい。
   また、ワームホールのy座標はエリア1とエリア3の境目が分かればいい。

3. 二分探索で境界を特定できる。

この方法だと、S <= 17^2までしか全問正解できないようで、S>=20^2くらいからスコアが1になってしまうこともあるようです。
値の振れ幅を大きくしたいと思う。

・値を2通りにしてみる
だいたい、["500 - S * 3", "500 + S * 3"]の値を割り振ります。

seed24 S=900

判定手順は、ほぼ同様。
例えばエリア3なら、座標を+L/2してエリア0との境界を得るようにするなど、小さい工夫は必要。
x座標とy座標でなにかしら境界線が存在しさえすれば、ワームホールの座標を特定できる。

値2分割なら、S = 30^2 でも、1より大きいスコアが得られました。

こんな感じの貪欲な解法を4通り作成し、約2000パターンシミュレート。Sごとに、スコアの良いアルゴリズムを選択しました。

実装
https://atcoder.jp/contests/ahc022/submissions/44789234