AHC022 参加記

AHC022 お疲れさまでした！
夏休みに入ったのでコンテスト期間中 (ほぼ) ずっとやってました。。

ほぼ自分のためのメモ書きなので読みづらい部分もあるかと思いますが、せっかくなので記録として残したいと思います。

問題概要

異世界への出口座標がわかっていて、異世界の温度は各マスごとに設定できる。
出口と 1:1 対応している入口があるので、対応する出口を当ててね。

注記

• 標準偏差として $\sigma, S$ を使っていますが、 $\sigma$ は一般論 (のつもり) で書くとき、 $S$ は今回の問題の設定として使い分けているつもりです
• 「○○ 点」は提出詳細から見える絶対スコアです
• 相対スコアは提出時点でのもので、最終的なものではないです
• ツイートの埋め込み多めですが、最近の仕様変更で読み込みがうまくいってないかも

やったこと

とりあえずリンク集です。

• 提出一覧
• GitHub ※コンテストが終わってから GitHub に上げました。

要約すると

• 「スポット」を真ん中に置く
• 出口を決め打って、入り口を全探索
• ベイズフィルタ的なことをして確率的に計測する
• 要約終わり。思考の詳細を飛ばして 結果と感想までスキップする

とりあえずやってみる

まずは、全部 0 で配置して 0 を出力するコードを書いた。
提出 #00

提出すると... TLE ...？
調べてみると、 Rust の proconio のせいらしい。

• rust で atcoder のインタラクティブな問題やるときの注意 - Qiita
• 解説 - AtCoder Beginner Contest 244

インタラクティブでは from を指定する必要がある、なるほど

いざ再提出！ 18386 点、優勝！w
提出 #01

平均をとってみる

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

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

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

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

ローカルで試していい感じだったので、 $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

ミスを直したので、乱択をもう一回取り入れてみる。
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

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

$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

入力として与えられる計測値は、 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

調べてみたところ、 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

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

初期状態では、 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 。

結果と感想

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

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

システムテストの結果、131 位に下がってしまった...。
$S$ が大きいところでは相対スコアが高かったものの、小さいところでは詰め切れていなかったみたいです。
場合分けをしておけばよかったなぁと...。

でもかなり楽しかったです！
以前 AHC016 に参加したときは最尤推定で止まっていたところ、今回はベイズフィルタを使ってみたり、乱択を使ってみたり、自分の中では成長したかなと思ったり。
しかしまだまだ初歩的なベイズの話しかできてないので、もっと勉強していきたいです。
次回の AHC も楽しみです！お疲れ様でした、ありがとうございました！