AHC022 参加記

13:14 · Aug 11, 2023 (GMT+9)

AHC022 正の得点を獲得、優勝！

平均をとってみる

次、正規分布なので、平均取ったらまあ真値に近づくやろなぁ

5,151,128 点、だけどなんか相対評価は下がった
提出 #02

標準偏差大きいところでスコア低いんだろうなーと予想。

最尤法

とりあえず最尤法するかぁ
試しにローカルで... あの、標準偏差がでかすぎて話にならないんですが
まあいったん出してみると 5,135,203 点、それほど変わらず
提出 #03

線形補間する

標準偏差が小さいものを最適化してみる？
標準偏差だと上下 $3 \sigma$ で 99% はカバーできるので、差が $6 S$ 以上となるようにしてみる
出口の温度を決めたら、 $L, N$ の関係と鳩ノ巣原理から、縦横に線形補間を繰り返して全体を埋められそう？

とりあえず、 $6 S$ のギャップがあくようにしてみて、それができない (1000 を超える) ようであれば、完全に無視してみる (全部 0 で配置し、すべて 0 と推測する) ことに。

14,655,822 点。 3 倍くらいには上がってるけど、相対順位はまだまだ変わらず。
提出 #04

またまた最尤法

範囲を $\sigma$ → 上下 70% くらいだけカバーするようにしてみる。
差を $2 S$ にして、何回かサンプリングすることで最尤法をしてみよう作戦。
これで placement cost は下がるはず。
その分精度は落ちてしまうので、回数は 6 回にしてみる

51,679,687 点、相対順位も割と上がった。
提出 #05

温度の置き方を変える

トーラス型なので、外側の温度は互いに近いほうがよさそう。
とりあえず、中心の温度が低くなるように設定してみる。
実装としては、真ん中からのマンハッタン距離が短いほうから、温度を高くしていくようにする。

70,746,673 点、相対順位は +40 位くらい上昇
提出 #06

線形補間を改善

線形補間を、「横 → 縦 → 横 →...」とやっていたので、まず横が優先されてしまうのではと考えたので、「縦 → 横 → 縦 →...」の結果との平均にしてみる

82,405,355 点、相対順位もあまり変わらず。
提出 #07

移動も用いる

ひらめいた。真ん中に 1 つだけ温度高い「スポット」を配置して、移動+計測で位置をあてに行ってみよう。
最大で $S = 900$ なので、「500 以上で 1000、500 未満で 0 」と判定することにすると、 $S = 900$ に対してはだいたい $0.5 \sigma$ → 30% くらいずれそう。

3 回計測した場合を考えると、対称性と条件付き確率から、 2 回 500 以上だったら 70.0 %、 3 回だったら 92.7% でそれは 1000 だろうということが推測できる。(計算ずれてるかも)

ここで疑問。 3 回チェックできるの？
各 $i$ について、出口を全部調査すると $N^2 \le 10000$ になって 1 回しかできなさそうでは？
でも、確信の持てたやつを候補から消していくと $N + (N - 1) + ... + 1 = \dfrac{N (N+1)}{2} \le 5050$ となって、 2 回くらい調査できそう。
さらにランダム性を仮定すると、回数は半分になってくれるはず？
よって 4 回くらい調査できるんじゃね？まあ怖いので一応 3 回にしておく。

実装してみてローカル 100 ケースで試してみたところ、計測回数制限には引っかからなかった。
ちょっと怖いけど提出！

207,454,243 点、問題なく通り、順位も 200 位ほど上昇！相対スコアも 3B に乗った！
提出 #08

15:46 · Aug 13, 2023 (GMT+9)

#AHC022 3B 突破！もっとやるぞ！

さらに、全ケースで中央 1000 固定なので、 $S$ の値に応じて変えるようにしてみる。
一応余裕をもって $\min(1000, 6 S)$ にすると、 230,425,912 点。
提出 #09

ここから少し変え、「 3 回やって 500 以上になった回数」で計算するのではなく、「 3 回やった総和がスポットの値 ×1.5 を超えるか」で計算してみる
247,050,850 点、相対スコアが 4B に乗った。
提出 #10

17:50 · Aug 13, 2023 (GMT+9)

#AHC022 ちょっと変えただけで 4B！うおおお

Asa

@a01sa01to

#AHC022 3B 突破！もっとやるぞ！

ローカルで試していい感じだったので、 $6 S$ を $5 S$ にしてみる
250,541,971 点、相対も少しだけ上がった。
提出 #11

とりあえず様子見する

調べてみると、 $S = 400$ くらい以上でスコア 1000 を超えないので、これについてはまた別の方針を考える。
とりあえず様子見で全部温度 0 の出口も全部 0 にしてみる。
251,720,688 点、微増。
提出 #12

計測回数を $S$ に応じて変える

そっか、全出口を調査できなくてもある程度の出口を何回も調査してやったほうが得点は高くなりそう...？
ということで標準偏差に応じて計測回数を変更してみる。
$\max \left( \lfloor \frac{\sqrt{S}}{4} \rfloor , 3 \right)$ 回探索してみる。この値はただの勘。
ちなみに、問題文から $S$ は平方数が保証されてる。
266,923,975 点、相対スコアは 4.8B。
提出 #13

調査する順番を乱択で決めてみるとよさそう？
267,073,274 点、相対スコアは下がっちゃった。
提出 #14

逆に、入口を決め打つんじゃなくて、中心に近い順に出口を決め打ったら計測コストは下がりそう？
261,169,107 点、相対スコアは微増。
提出 #15

上の実装はミスってたので、直す。
284,313,362 点、相対スコアも 5B に到達！
提出 #16

17:05 · Aug 15, 2023 (GMT+9)

#AHC022 5B 到達！

ミスを直したので、乱択をもう一回取り入れてみる。
285,350,954 点、相対スコアは数万点のまじで誤差レベルな微増。
提出 #17

微調整 1

割とよく当たるようになってきたので、真ん中の値を $5 S$ から $4 S$ にしてみる。
250,945,259 点、相対は 4.5B 。かなり下がってしまったので Revert。
提出 #18

見るからに計測コストが高いので、やっぱり $6 S$ にして当てに行く方向でやってみる。
280,887,274 点。
提出 #19

少し理論的に考えてみる

$6 S$ として設定できるんであれば、別に 1 回の計測でも割といい性能出るんじゃない？
ローカルで爆増したので提出！
266,204,800 点。相対スコア激減。なんでや。
提出 #20

あー、誕生日のパラドックス的なやつかな...？

$10 S$ にしてみる。これでかなり抑えられるはず。
$5 \sigma$ で正規分布表見た感じ $2.87 \times 10^{-7}$ っぽいので、ざっくり衝突起きるのが $\sqrt{x}$ で見積もったとしても 1% には満たないでしょという判断。

さらに、戦略 1 (線形補間のやつ) がこの戦略 2 の条件分岐を内包してしまっていたので、どんな場合もこの戦略 2 で戦うようにしてみる。

390,688,855 点。相対スコアもほぼ 7B に爆増！
(順位はもう 20 位くらいしか変わらず...)
提出 #21

19:52 · Aug 15, 2023 (GMT+9)

#AHC022 ほぼ 7B ！うれしい～！

ひとまずもう使わなくなったコードを消して整理。

$10 \sigma > 1000$ 、つまり $S > 100$ の場合は $\lceil \frac{S}{100} \rceil$ 回計測して精度を高めたい
392,060,168 点。あまり変わらず、相対は微減。
提出 #22

中心極限定理的に、 $n$ 回計測すれば標準偏差は ~~$\frac{\sigma}{n}$ になりそう？~~ $\frac{\sigma}{\sqrt{n}}$ らしいですなので、 $\mathrm{round} \left( \frac{S}{100} \right)$ 回計測してみる
382,392,506 点。下がってるなぁ...
提出 #23

微調整 2

round から $\lceil \frac{S}{100} \rceil$ にしてみる
397,956,695 点。
提出 #24

$\lceil \frac{S}{125} \rceil$ にしてみる
375,679,947 点。
提出 #25

$\lceil \frac{S}{100} \rceil$ に戻し、 $8 \sigma$ にして placement cost を減らす作戦。
415,129,829 点。
提出 #26

計測回数を可変にする

こっちで回数を指定せず、 0 か 1000 である確率が 0.995 を超えるまで計測するようにしてみる。
ベイズフィルタ的なかんじ？
ローカルでかなり増えたので提出！
454,801,180 点、相対スコアが 8.2B に到達！
提出 #27

17:46 · Aug 16, 2023 (GMT+9)

#AHC022 8B きた！

入力として与えられる計測値は、 0 未満になるような場合は 0 に、 1000 を超えるような場合は 1000 になってしまう。
この場合確率がずれそうなので、累積分布関数を使って補正してみる。
Rust では累積分布関数はない？ので、 Wolfram に求めさせた $P(X \le x) = \dfrac{1}{2} \mathrm{erfc} \left( - \dfrac{x}{S \sqrt{2}} \right)$ を使って確率を求めた (erfc の実装は Wikipedia を参考に近似値を前計算させて使った)
508,203,383 点、相対スコアは一気に 11B に到達！順位も 76 位に！
提出 #28

20:04 · Aug 16, 2023 (GMT+9)

#AHC022 9B, 10B を飛ばして 11B を突破！暫定 100 位に入った！！！

調べてみたところ、 Rust には libm という標準ライブラリ？があり、その中に erfc 実装があった。
そのほうが精度がよさそうだったので、こっちに切りかえてみる。

また、特定の $x$ が出たときに、それが出る確率を $\dfrac{1}{\sqrt{2 \pi \sigma^2}} \exp \left( - \dfrac{(x - c)^2}{2 \sigma^2} \right)$ としていた。 ( $c$ はスポットの値)
でも実際は round されているので、こっちも erfc を使って、 $P(x - 0.5 \le X \le x + 0.5) = P(X \le x + 0.5) - P(X \le x - 0.5)$ として確率を補正する。

499,738,117 点、絶対スコアは下がったけど相対スコアは上がったのでヨシ！
提出 #29

標準偏差が大きい場合の対策

ここまでで、スコアが 1000 を下回っているのは $\sqrt{S} \le 27$ のときになった (seed 1 ～ 100 でチェック)
なので、 $\sqrt{S} \le 25$ くらいのスコアを上げたい！

質問回数が上限に達してるっぽかったので、 0 か 1000 である確率が 0.995 を超えるまで計測していたところを、 0 は 0.9 に減らし、 1000 はそのまま 0.995 にしてみる。
これはある程度確率が低い状態から再起することはないでしょという想定。
一部のケースではスコアが下がってしまっていたけど、ローカル全体としてみればかなり上がっていたので提出！
524,976,711 点、相対スコアはいうほど変わらず...。
提出 #30

上がっているケースもある一方で、下がっているケースもそれなりにあるせいだと考えた。
なので、 $S < 400$ のときは 0 の許容を 0.99 にして、それ以外のときは 0.90 にしてみる。
508,892,229 点。下がった。
提出 #31

これあながち間違ってないと思うんだけどなー。
$S < 450$ なら 0.99 でそれ以外は 0.90 にしてみる。
499,293,338 点。うーん、なんもわからん。
提出 #32

微調整 3

割と当たるようになってきたので、 $8 \sigma$ から $6 \sigma$ にしてみる。
0 の許容度の場合分けもなくした。
502,613,113 点。相対スコアもさらに下がる...。
提出 #33

選ばれていないものを対処

10000 回計測終わった後、計測できなかった場合はすべて 0 にしてしまっていたので、選ばれていない出口から 1 つ選んでその値にする。
1 つでも答えをあてに行く作戦。
505,230,387 点。相対スコアも 11B に戻った！
提出 #34

11:50 · Aug 19, 2023 (GMT+9)

なんとか 2 桁順位に戻ってきた...！

初期状態での確率を変える

初期状態では、 1000 である確率を 0.5 から 0.3 にしてみる。
1000 であるマスの個数は 0 よりかなり少ないのでね...
ローカルだと最低点で 3 万点ゲット！ (seed 44: 36432 点)
506,758,659 点、相対スコアは下がった。なんで？？
提出 #35

0.35 にしてみる
498,157,365 点、でも相対スコアはあがった。
提出 #36

微調整 4

1000 である確率が 0.995 になるまで計測していたところを、 0.999 にしてみる。
542,744,221 点。 100 位まで下がってたけど、何とか 2 桁順位に戻ってきた！
提出 #37

1000 の確率を 0.9999 にして、 0 の確率を 0.85 にしてみる。
519,959,713 点。かなり下がったので、 Revert。
提出 #38

#37 に戻す。521,084,141 点

スコア変わったのは乱数使ってるからだろうなー。下がったのはかなしい。
提出 #39

もうこうなったら乱択なくすぞ！
523,540,449 点。相対スコアも微増。
提出 #40

この後いろいろやってみたけどうまくいかず、最終提出は #40 。

結果と感想

21:56 · Aug 20, 2023 (GMT+9)

#rcl_procon #AHC022 お疲れさまでした！暫定 11.4B 120 位でした！自分の方針は、真ん中に 1 つだけ温度の高い「スポット」を作っておいて、ベイズフィルタっぽいことをしながら、出口決め打ち入口全探索(?) です！みなさん温度が滑らかだなぁと思うなどしました...w 尖がってる自分のとは大違い

Read 1 reply

暫定 120 位でした！最後に 2 桁順位に行きたかったけど、これはシステムテストに期待...。

ほかの方のツイートを見てみると、盤面をちゃんと滑らかにしている方が多いですね。
自分はほんとにスポットを 1 か所だけ建ててそこから移動して計測、みたいなことをしていたので、そこらへんを改善すればもう少し上がったかも...？

09:12 · Aug 21, 2023 (GMT+9)

うわぁぁぁぁ落ちてるー ><

Asa

@a01sa01to

20:49 · Aug 21, 2023 (GMT+9)

a01sa01toさんのRECRUIT 日本橋ハーフマラソン 2023夏（AtCoder Heuristic Contest 022）での成績：131位パフォーマンス：1917相当レーティング：1627→1681 (+54) :) Highestを更新しました！ #AtCoder #RECRUIT日本橋ハーフマラソン2023夏（AtCoderHeuristicContest022） atcoder.jp/users/a01sa01t…