参加しながら考えたこと試したことの源泉かけ流し。

最終的な方針はまとめにまとめてあります。

問題概要

A - Exploring Another Space

1 日目

評価指標が複数ある系だ！最近流行ってるのかな。
これ系はやってみらんと分からんのでとりあえず簡単なコードを書いてみる。

温度は左上から順に線形に増やし、各ワームホールの出口セルを 100 回ずつ計測して一番近いものを答えるやつ。この時点では配置コストの方がかなり大きいな。0 と 1000 とかの温度差が隣り合うのはかなり痛いらしい。

画面の上と下の温度差も滑らかにしてみる。

全箇所で温度差を滑らかにすると配置コストが計測コストを下回るらしい。

ただ、出口セルが隣り合う場合とかは滑らかだと判別がめちゃキツくて、なんかそこだけ温度差をつけるみたいなことはした方が良いかもしれない。

あとこの温度差の付け方だと温度の傾きが盤面の上半分と下半分で一定なので、出口セルの周囲を見た時にあまり見分けがつかなそうだ。
円状の方が良さそう。

ひとまずはこれで。

さて、そろそろ正答率の改善をしていきたい。

測定値どれくらいブレるんだっけ。
正規分布に従って標準偏差が 1 から 30 くらいって書いてあったような ... アッ違うな、1 から 30²？
900！？！？エグない？自分の暗算ミスかと思って 30 * 30 でググったけど確かに 900 だった。
真の値が 0 でも 1000 って返ってくることは普通にあり得るよ〜ってことだよね。うへぇ。
あと端の方だと 0 以下とか 1000 以上の値が Trim されて情報量減るのがキツそう。
逆に S = 1 のケースはかなり無駄を削っていかないと相対スコアが終わりそうでそれはそれで厳しさがある。

0 と 1000 を見分けるのなら標準偏差 900 でも数回試せばさすがになんとかなるかな？
例えば、温度を一面 0 で一点だけ 1000 にして、各出口セルから温度 1000 のセルへの相対位置を調べに行くという調査方法ができそう。

さっき円状の滑らかの温度で行こうとしてたけど、むしろこっちの方が正攻法か？
S が小さいケースだと温度差は小さくても見分けられるので、判別用のセルをたくさん用意しても配置コストは小さく済み、各出口セルの周囲に特徴的な配置を施すことで距離による調査コスト増大を抑えつつ特定ができそうだ。

準備として標準偏差が 1² ~ 30² のときに測定値が真の値から x だけズレる確率のテーブルを python で計算して cpp のコードに埋め込んだ。
これで測定値から元の温度とか出口セルの最尤推定が高速にできる。

さすがに 200KB 近いテキストを埋め込むと IDE がめちゃ重になったので、埋め込み箇所は #include で差し込むことにした。
提出用に #include の部分を置換したコードを吐き出すシェルスクリプトは、埋め込むテキストに改行が含まれるので面倒そうだなぁと思っていたが ChatGPT に教えてもらったらすぐできた。かしこいなぁ。

ひとまず (0, 0) だけ温度 1000 にして各出口セルからの相対位置を調べに行くやつで seed=0 では全問正解できるようになった。

ただこれ問題なのが、（使用済み出口セルは端折れるとはいえ）ワームホール × 出口セルの N² 通りに対して相対位置が 0 or 1000 の推定をしなければならず、S が大きくなってくると計測 10000 回だと全然足りない...。
やはりいくつかの固定の相対位置の 0 or 1000 を推定すれば出口セルが特定できる形が望ましそう。
相対位置遠いと計測コストが馬鹿にならんというのもある。

N <= 100 なので、そういう温度 1000 セルの配置が可能かどうかを度外視すると、うまくやれば 8 種類の相対位置で特定可能になるはずなんだよな。（追記：2⁸ = 128 だと勘違いをしています）

8 種類の相対位置の温度を推定することで出口セルが特定できるとして、N = 100 のケースで 1 セルの温度推定にかけられる調査回数は 10000 / 100 / 8 で 12.5 回。うーん、際どい...。
実験してみたけど、S = 900 のときに 12 回の調査で温度 0 or 1000 を正しく推定できる確率は 92.5% くらいらしい。厳しいねえ。
なんやかんや 20 回使えるとしても 96.8%。

提出用の埋め込み部分置換の動作確認も兼ねて提出したら 7 位につけたので、絶対今やらなくて良いけど S が小さい時に左上のセルの温度を適度に下げるのをやって 4 位になっておいた。見栄張り。

↓ は 10 回の計測で温度 0 と温度 X をほぼ確実に推定できる（10000 回シミュレーションして全部推定成功した）最小の X。

S:1 X:3
S:4 X:11
S:9 X:22
S:16 X:35
S:25 X:60
S:36 X:86
S:49 X:112
S:64 X:148
S:81 X:186
S:100 X:225
S:121 X:283
S:144 X:323
S:169 X:384
S:196 X:435
S:225 X:507
S:256 X:542
S:289 X:659
S:324 X:731
S:361 X:851
S:400 X:947

温度 60 くらいならポンポン乱立させても良さそうに思えるけど、200 とかを超えてくると厳しい。
まぁ制約違反するわけではないし正答率上げるには仕方ないと踏んで同じ方針で進めるか...？

ちなみに今は 4 割くらいのケースの生スコアが 2 桁点以下であり、まず正答率を上げることを考えなければいけない。

ふと、0.8⁶⁰ ってどれくらいなんだろうと計算してみたら 0.00000153249 らしく、思ったよりデカい。
これもしかして無理めなケースは配置+調査コストを 0 にして諦めムーブをした方がスコア良くなったりする？

→ L=21 N=62 S=900 の seed=24 で 4 桁点が取れた。
ちゃんとやれば抜けそうなスコアには見えるが、終盤になってもダメだった時のための備忘録として。

2 日目

メモ: S が小さい場合は 0 or 高温の 1bit の情報じゃなく、温度を数段階に分けても判別できるので、それを活用するべき。

出口セルの周囲 9 マスに特徴的な温度配置をして、その 9 マスの温度を調べることで出口セルを特定するやつを書いた。

これは高温セルの温度を 100 にしてるのだけれど、それでも配置コストがデカくて昨日の 1 セルだけ高温セルを置く作戦に勝てないっぽい。

ただ全体的に見ると生スコアが 2 桁点のケースは消滅したので、正答率の改善には繋がっているらしい。

内部でシミュレーションして一番結果の良かった作戦・パラメータで本番に臨むようにするやつを書いた。投げて 26 位。

相対スコアの感触的に S が大きいケースでの手元での大幅スコア増があまり効いてない感じがするので、少なくともここらはまだ伸ばせるはず。

N-1 個目まで答え確定させたら残りの一つは調査無しでも余った出口セルで決め打ちできるなと思ったのだけど、実装したらちょっとスコア下がった。
よく考えたら 1 個不正解だったケースの傷口が確定で広がることになるからそれもそうだ。

逆に言うと(?)、1 個不正解なケースではどこかの回答が被ってるはずだから、被ってる部分について追試みたいなのをしても良さそう。また後ほど。

今は 1 セルごとに 0 or 高温を推定してからパターンに当てはめてるけど、パターン全体を丸ごと最尤推定するべきな気がしてきた。
→ 本当か？終盤は特定の相対位置のみ推定できればそれで OK なケースも多分あるよ。
→ どの相対位置から調査していくかは要検討そう。

それよりもまず解決すべきはパターン推定の方で配置コストがクソデカになる問題なんだよな。うーん。

3 日目

パターンで判別する方式は、別にチェックする相対位置は決め打ちじゃなくても良いことに気がついた。
要するに、盤面の半分くらいを高温にしておけば、どこかしらの相対位置の温度を調べることで候補を半分ずつくらい削っていくことができる...はず？

高温にする領域は一辺が L/sqrt(2) くらいの正方形が良さそう。
盤面の半分くらいの面積、かつ任意の出口セルのペアについて 2 つを判別可能な相対位置が存在する、かつ配置コストを最小限に抑えられるので。

できた。

このサイズの正方形の枠を盤面の良きところに当てて、その枠の中ですか外ですか？を調査により推定して出口セルの候補を絞り込んでいくイメージ。

調査の仕組みは昨日の出口セル周辺にパターンを作るやつと同じなので、配置コストの面で軍配が上がって S = 1 以外のケースではこちらが採用されるようになった。

書いてから気付いたけどこれと初日に書いた 1 点のみ高温にする戦略は高温にする領域のサイズが違うだけでやってることは同じなのね。
どちらも採用されるケースがあるからじゃあ間くらいのサイズも試した方が良い？ということで領域の一辺を L/4 の場合も試してみたら結構採用された。

領域サイズ小 → 配置コスト小、計測コスト大
領域サイズ大 → 配置コスト大、計測コスト小
というトレードオフがあるので、いい感じに調節ができると理想なのだが、それはまた後の話かな。今まだ順位表上のスコアが 18G 点なので根本的なところで改善ができるはず。

内部でシミュレーションして最適な温度パラメータ探す際、今は線形探索気味のこと（具体的には for (int t = 1000; t >= 5; t *= 0.9) ）をやっていて、スコアはこのパラメータに対して概ね凸関数になるので三分探索をしたいのだが、スコアが平坦気味な領域がありバグりそうな気がして手をつけられずにいる。
まぁ平坦なところはブレすらなく本当に平坦（1点）っぽいので何とかなるか...？

→ 平坦気味なら温度低い側を切り捨てる感じで実装してみたけどスコア微減しちゃった。
確信はないが、今各パラメータごとに 3 回しかシミュレーション回してないので、本来なら温度は 1000 が最適なんだけどたまたま 995 のシミュレーションで当たりを引いて採用されちゃった（そして本番で誤答）、みたいなことが起こってるような気がする。
まぁこれは本質じゃないのでいいか。

低温と高温の差として 100 空けたいとき、0 - 100 で設定していたところを 450 - 550 と設定するようにしてスコアを微増させた。

初日に言っていた「端の方だと 0 以下とか 1000 以上の値に Trim されて情報量減るのがキツそう」へのせめてもの対策。
低温 or 高温の調査をするとき、ある程度尤度に差がついたらそこで調査打ち切りをするようにしているので、こうすることでそれをほんの少し早く切り上げられるケースがきっとあるはず...と思っていたが、ちゃんと効果が出ると嬉しいね。

今は出口セルの候補の絞り込む際、既に使用済みの出口セルも候補から外さないようにしているのだけれど、これどうしようか悩ましいところ。
候補から外さない理由としては、誤答した際に後続の推定に影響が出る、1 回あたりの推定に使える調査回数を見積りやすい、あたり。
ただ、候補から外しちゃった方が 1 回あたりの推定に使える調査回数の上限が増えて、精度が上げられるというのがある。
後回し。

出口セルの周囲 9 マスに特徴的な温度配置をするやつ、S = 1 では最強なのでやることがなくなってきたら改善してあげたい。
具体的には

パターン配置先は 9 マスもいらない場合が多そう（盤面激せまとかじゃなければ 7 マスで OK なはず）
調査の際、既に使用した出口セルは候補から外す（これは流石に正解してる前提で OK なはず）
配置コストがより小さくなるようなパターンにする

→ 上 2 つは実装してちゃんと伸びた。S = 2 でも正方形で絞り込みに対し勝てるようになった。
3 つ目はパターン構築時の評価関数に配置コストのようなものも軽く加えてみたけど、なんかスコアが下がったのでやめた。

今日はもう寝るが、明日やりたいこととして正方形で出口セルを絞り込むやつを複数の温度で絞り込むようにするのを試してみたい。
今は決定木が二分木なのだが、これを三分木四分木にできると木の深さが減って（= 調査が必要なセルの数が減って）嬉しいはず。
当然配置コストは増加するが、なんか "回" の字のような入れ子にしてあげれば爆増ってほどでもないんじゃないだろうか。
とりあえず、現状この戦略では調査コストが配置コストを上回っているので、調査コストを減らす工夫を試しておきたい。

そういえば今高温の領域置く場所は左上固定にしてるけど、これの位置をズラすことで配置コスト削減できたりする？
まぁめちゃ改善するアイデアではないか。

4 日目

状況を整理しよう。

今は 3 つの戦略を内部でシミュレーションして最善だったもので本番に臨むという形になっている。

SinglePointSolver

左上の一点だけ高温にするやつ。グリッドが小さいかつ S が大きめの時にたまに採用されることがある。
採用頻度および改善余地的に放置で良いかなと思っている。
やるとすれば高温にするセルの位置を最適そうな位置に動かすくらいか。

UniquePatternSolver

こういうやつ。S = 1 or 2 で有効。
S = 1 においては調査コスト >>> 配置コストなので、1 セルに 2~3bit の情報を詰めることで改善が見込める。
どうしてもやることが思いつかない時にやる。

BinaryPatternSolver

正方形の領域の内外を判定して出口セルの候補を絞り込んでいくやつ。ほとんどのケースがこれ。
正方形の領域内の温度を数段階に分けることで調査コストを削減できるんじゃないかな...と思っていたが、よく見ると現状調査コストと配置コストが結構拮抗しているなぁ。どうだろう。

回の字に温度を分けるとして、二つの温度の領域の面積を同じくらいにしようとすると配置コストは 1.5 倍くらいになりそうな計算で、調査コストはというと、例えば 81 個の出口セルを完全二分木 / 完全三分木で絞り込めたとすると、その深さは 4/log2(81) ≒ 0.63 倍くらい。う〜〜〜ん...。

まぁ調査コストが配置コストの 2 倍くらいになってるケースもちらほらあるからそれらに対しては有効だと思う。拮抗してるケースにはあまり期待できないかもしれん。

調査コストと評価コストのバランス以外の観点として、数個誤答してるケースへの追試というのもある。

seed=0~99 ので 1 ミスが 6 ケース、2 ミスが 4 ケース、3 ミスが 2 ケースあるので、ボトルネックではないものの改善する価値はありそう。

やるとすれば高温にするセルの位置を最適そうな位置に動かすくらいか。

これ実は本質じゃないか？
よく考えたら x=5, y=5 での調査 1 回は x=0, y=0 での調査 2 回分なんだよな...。

これ多分 SinglePointSolver はまだ良くて、BinaryPatternSolver での決定木って事前に貪欲で構築してるんだけど、その貪欲の評価基準がいかに候補の出口セルを 2 等分にできてるか否か、タイブレークで距離、なので、一発目の判定で遠距離のやつを調査になってると毎回そこからスタートして目も当てられないことになってるんじゃないだろうか。

手始めにと思って SinglePointSolver で各出口セルからの距離の和が最小になるセルを高温セルにするようにしたらスコアが微減した。マジで何で？全完自体はできてるから計算間違いとかじゃないと思うんだけど...。
→ ビジュアライザ眺めてなんか辺鄙なところに高温セル置いてんな〜と思ったら距離計算する関数をバグらせていた。計算間違いです。トーラスがよ...。
ちゃんとやったらちゃんと微増した。

じゃあ本命の BinaryPatternSolver の方をね。

高温領域を 49 通りくらい平行移動させて二分木を作って一番良さそうな木を選ぶやつを書いてみて、確かに伸びるには伸びたのだが、手元での相対評価で 3% くらいしか伸びておらず、それだけ？感が否めない...。

うーん、どうも「一発目の判定で遠距離のやつを調査になってると毎回そこからスタートして目も当てられない」が嘘なのかもしれないな。
一発目で近距離やると結局後ろに皺寄せがいって総和としては同等な感じになるんだろう。

今は出口セルの候補の絞り込む際、既に使用済みの出口セルも候補から外さないようにしているのだけれど、これどうしようか悩ましいところ。

これ実装してみた方がはえ〜なと思って 5 分くらいで書いたら 10% くらい伸びた。
実装軽いアイデアは思考停止でさくさく手を動かした方が早いな。

ただ弊害として誤答が少し増えた。ただこの場合の 2 ミスは訂正のしようもないんだよねぇ...。

コード長にまだ余裕があるので埋め込んでる確率テーブルの精度を小数点二桁分増やしてみたがスコア落ちて草。誤差の範囲か？

BinaryPatternSolver、高温の領域から離れた 2 つの出口セルの判別には遠距離の調査を行うしかないので、そういうときに使ってもらえればと高温の領域から遠い位置にちっちゃい高温領域作ってみたけど普通にスコアが落ちた。ちぇっ。

結局領域の形は正方形が最適なんだろうか。

今はどの戦略も先頭のワームホールから順番に出口セルを確定させていく方式だけど、これが良くなかったりするのかな。
なんか全体的に調査していって確度の低いところを追試していく、みたいなのは可能だろうか。

1 セルを 3 回調査することと 3 セルを 1 回ずつ調査することの違いについて思いを馳せている。
なんか S が大きいケースだとどっちも同じじゃんという気持ちになるが、S が小さいケースだと確実に後者の方が情報量が多いので、多分 S が大きくても後者の方が嬉しいんだろうな。
だとすると 8 セルを 10 回ずつ調査するより 80 セルを 1 回ずつ調査する方が嬉しいのか？これってトリビアになりませんか？

5 日目

UniquePatternSolver で 1 セルで複数段階の温度を持つようにして S=1 のケースで 20% くらい伸びた。

SinglePointSolver で高温セルまでの距離の近い出口セルから順に試すようにして微増した。それはそう。

今は 1 ワームホールごとに出口セルを二分木辿って推定していっているが、全部のワームホールを同時に二分木辿っていくと調査の打ち切りとかが効率的にできそうな気がしてきた。

例えば 10 個の出口セルの候補を特定の相対位置の温度差で 3:7 に分けるとき、調査を進めていく中でそれぞれの候補が高温である確率をソートして並べると {0% 3% 8% 81% 84% 88% 90% 93% 99% 99%} みたいな感じになるので、境界線が十分にハッキリしたらそこで分割終了、みたいな。
調査は 50% に一番近い候補に対して行うと境界がいい感じに探れるはず。

→ 実装したら結構なケースで 20% くらい改善した！のはいいんだけど、度々本番クエリ中途中のノードで運悪く推定ミスしてその後の分割で一生境界が見つからないよ〜〜になりほぼ 0 点になるときがある。ブレイクスルーっぽいのは良かったけどこれめんどくさいな〜〜〜。

曖昧なやつは曖昧なまま次に進められたりすると良いのかなぁ。そうすると今の二分木ベースは相性が悪そうな気がする。
一旦ワームホール A は出口セル 1 と対応してそうっぽいと思ったけど、出口セル 2 と対応してるワームホール他から探したらそれっぽいのがなかったのでワームホール A が再浮上するみたいなのが理想なんだよなぁ。

というか今スコア 22G なのだけれど、本当にここからコスト半分以上削れるのか...？なかなかに信じ難い。

上の推定方法を SinglePointSolver にも適用するかと思ったが、こっちの戦略は高温が 1 つだけなので、境界を探すというより現時点で一番高温っぽいやつをひたすら叩いて本物を見つけ出すみたいな方法が良さそうな気がする。偽物なら叩いてるうちにボロが出るはずなので。
...これって別に二分木でも同じ考え方ができるな？一番高温っぽいやつをひたすら叩いて本物と認められたら次点を叩いて、高温セルの数だけ本物が見つかれば分割終了。

試してみたら 10% くらい伸びた。良いじゃないですか。

本番クエリ中にポカして 0 点になる問題、もしかしてと思って埋め込んでる確率テーブルの精度を小数点二桁分増やすやつを再びしてみたらかなり改善した。なるほどね。

それっぽいものをひたすら調査して確定させていく方針が筋として良いのかな。
だとすると、それぞれの出口セルにターゲットを絞ってそれっぽいワームホールを探して確定させていく方針もアリ？
これだともし途中で推定ミスって後半でこの出口セルに該当しそうな候補がないぞ！？ってなった場合にも対応がしやすいというメリットもある。

6 日目

BinaryPatternSolver の領域のサイズ、今まで領域の一片の長さを L / sqrt(2), L/3+1, L/5+1 の 3 通りしか試していなかったのをリファクタがてら L / sqrt(2) から下に 3 刻みで全部試すようにしてみたら引くほどスコア伸びた。平均 20% 弱の伸びだけど伸びてるケースは 1.5~2 倍のスコアが出ている。
提出したら 26G → 34G になった。は〜

実行時間が 3sec を超えてきて新しい試行の追加が難しくなってきたので、ボトルネックの改善とかスコアが低そうなパラメータのシミュレーションをスキップするようにして 2sec くらいに抑えた。

UniquePatternSolver、関係ないセルは全部温度 0 にしてたけど、冷静に考えたら中間の温度にしておく方が配置コストは小さくなるな。

→ やって S=1 のケースが 5~10% くらい伸びた。こういうのをちゃんと押さえとかないとね。

SinglePointSolver の高温セルの位置、全ての出口セルとの距離の総和が最小の点にしてたけど、実際は距離が近い順に調査していき徐々に調査すべき候補が減っていくので、N * (一番近い出口セルとの距離) + (N-1) * (二番目に近い出口セルとの距離) + ... で評価するようにしていくらか伸びた。

これもう S=169~ あたりから概ね SinglePointSolver が採用されちゃってるんだけどそういうものなんだろうか？
この戦略もう改善の余地がない気がしており...。

実装したくなさすぎて考えないことにしていた BinaryPatternSolver の温度を 3 段階に分けるやつをやってみるか。

→ 実装結構大変だったけどダメっぽいなぁ...。酸っぱい葡萄は酸っぱかった。ちゃんと期待通り動いてるんだけどスコアがいまいち。
最も高温の部分を一番活用できる（＝一番分割できる）ところに枠を動かそうとして、その分相対位置によるコストが大きくなってしまった？もうちょっと原因は掘り下げた方が良いかも。

7 日目

ワームホールを縦軸、出口セルを横軸にとった行列で確らしさみたいなのを管理したらどうかということを考えて「行列推定」とかでググってたらベイズ推定の話が出てきた。ベイズ推定！推定系の問題では毎度誰かがやってるなぁと思っていたのをすっかり忘れていた。

調べつつ、これ今から勉強して付け焼き刃でなんとかなるものなのか...？となっているが、terry さんが AHC018 で木曜にガウス過程回帰の本買って最終日までに仕上げてきたのを見てひっくり返っている。吸収力おばけ？

ベイズの定理の式を見て気付いたけど、今観測データからそのセルが低温か高温かの事後確率出す際、たとえ 10 個の候補から 1 個の高温セル見つけ出す場合でも事前確率一律 0.5 で計算していた。この場合なら高温の事前確率は 0.1 で計算するべきだろう。

→ ウキウキで修正したけどスコア微減した。なんでだよ...ッ！！

う〜ん、なんかよくわからないが、ここらの確率を厳密にやることって精度向上による調査回数削減に効いてくる部分なはずで、だとするともっと大枠の調査のやり方みたいなところを改善する方が良い気はしていて、じゃあ放っといても良いか...？う〜ん。

実行ごとにスコアが変わってデバッグがしんどいので 3.5 秒で打ち切り以外のタイマー関連処理を全部固定回数のループに置換したりしたが、まだなんか結果が変わるときがある。
~~→ タイマーの計測開始を L N S の入力直後に開始してたが、どうも Y, X 含め入力全て受け取ってからの方が安定するらしい？~~

これでだいぶ安定したのだがまだ微妙に結果がブレるときがあって、ログを比較すると実行ごとのランダム性を排除したはずのシミュレーションでかかった調査回数が途中からズレ始めてくる。
→ ひたすらログを吐かせて diff でズレ始めたところを眺めるみたいなことをしたら配列の境界外アクセスやってるところが 2 箇所見つかった。C++！って感じやね。

最上位との差が 33% くらいあってエグいので別の方針を検討した方が良い気はしている。

手元では今までで出せた各ケースの最大スコアを管理していて、ズルして全ケースでその最大スコア出せたとしても平均 10% くらいしか伸びないので。
じゃあどういう方針？さぁ...

8 日目

二分木辿る途中に齟齬が発生したら頭からやり直しにする簡易誤り訂正みたいなのを追加して 1% くらい改善した。

床に転がっていたところ、低温セルと高温セルの間は可能なら徐々に温度を変化させた方が配置コストが減るということを思い出した。

これみたいに高温セル 1 点の周囲 4 セルに緩和用セルを設ける場合、緩和用セルの温度を高温セルの 1/4 のにしてあげると配置コストは 25% 削減できるらしい。
緩和用の領域はあまり調査したくないため難しいかもしれないが、この緩和領域を広げればもっと配置コストの削減は見込めるだろう。
試しに距離 2 のセルまで使おうとするのも計算してみると、1000 - 347 - 130 - 0 みたいな緩和の仕方で 35% くらいの削減。まぁ 347 はあまりに中間すぎてアレだけど。

いや〜、正直小手先改善のアイデアすら尽きていたのでかなりホッとしている。さすがにこれはスコア伸ばせるポテンシャルのある気付きだろう。

雑に境界に間の温度を置いてみたりしている（本当は境界上の可能性がある調査はしないようにするのが理想なんだろけど特に考えてない）が、3.5% くらいは伸びてそうな雰囲気がある。
SinglePointSolver の方が改善のインパクトが大きいらしい。基本的にこれが採用されるのは S が大きいケースで、配置コストが大きめなので。
時間がアレなので続きはまた明日。

9 日目

BinaryPatternSolver の方も境界を中間の温度にすれば配置コスト半分くらいにはなるんだよなと思い色々ガチャガチャやってみていたが、なかなか思うようにスコアは伸びない。

唯一少しだけ伸びたのは、調査の計画上絶対に調査されることがないセルの温度を周囲 4 セルを見て最適な値に修正するというもの。
二分木で候補を分割して調査を進めていくので一つの出口セルにつき調査する可能性のある相対位置は高々十数程度に収まるのでそれなりに調査されないセルが発生し、それらのセルの温度を変更する分には調査の性能には全く影響を与えずに境界をぼやかすことができる。

ただスコアの伸びとしては 0.9% くらいなのでう〜んという感じ。
正直もう少しガツンと伸びることを期待していた。

上の修正は UniquePatternSolver にも適用できるのでやって各ケースで 2~5% くらい堅く改善、全体としては平均 0.2% アップくらい。
こっちの方はぼやかした後に割と非自明な柄になっていて見て楽しい。

10 日目

とうとう最終日なので、重い腰を上げて誤り訂正をちゃんとしようということになった。
と言っても実装の都合上 SinglePointSolver のみではあるのだけれど。

SinglePointSolver で誤答してるケース自体は 100 ケース中 2~3 ケース程度なのだけれど、誤り訂正入れると誤答を減らせるだけではなく、もう少し強気のパラメータで攻めれるようになるという副次的な効果もあると思うので、最後の望みとして結構期待している。

→ 平均 2.6% くらい伸びた。

やることがないので高速化でもするかと思って時間がかかってる乱数周り見てたら std:: normal_distribution というのがあるのを知った。えっ！？
正規分布に従う乱数取るとき 0.0 ~ 1.0 の乱数取って 0 から順に埋め込んだテーブルの確率見て...ということをしてたのをこれで置き換えたら比較するのも申し訳ないくらい速くなった。草

今までは各戦略・パラメータを 3 回ずつシミュレーション回してスコアの平均を取っていたが、これを 10 回ずつ回してもお釣りがくるくらい速くなった。
精度が上がりスコアも微増。スコア上がって気が付いたけどシミュレーションの精度上げたら本番クエリ中での事故も減って嬉しいね。

最後にパラメータ調整や TLE 対策をやって終わり。おつかれさまでした！

まとめ

暫定順位 / スコア

22 位 / 34,502,498,943

方針

後述の 3 つの戦略を内部でシミュレーションし、一番平均スコアが高かった戦略・パラメータで本場クエリに臨む。

3 つの戦略に共通する事項は下記の通り。

どの戦略も調査により「ある相対位置のセルが低温か高温か」を判定することにより出口セルを特定する。
計測値からそれぞれの温度に対する尤度を求め、その値が閾値を超えたらそのセルに対する調査を終了し温度の推定値を断定する。

1 点だけ高温戦略

1 点だけ極端に高温にし、各出口セルとその高温セルの相対位置が低温か高温かを調査することで出口セルの特定を行う。
上の図では配置コストを緩和する都合上高温セルの周囲にある程度の温度をもつセルが存在するが、これらは低温セルと同等の扱いをする。
高温セルとの距離が近い出口セルに対応するワームホールの特定から順に行っていくと調査コストが浮く。
概ね S = 100~ くらいでこの戦略が採用される

正方形型の高温領域戦略

正方形の領域を極端に高温にし、出口セルからの相対位置が低温か高温か（つまり、この領域内であるか否か）で出口セルの候補を絞っていく。
どの相対位置で絞り込んでいくかは事前に計算しておく。二分木を作っておき、低温 or 高温で木を辿っていくイメージ。
つまり、各出口セルから調査を行う相対位置の数は logN ~ 十数程度に収まり、絶対に調査を行わないセルがそれなりに発生する。それらのセルは温度を好きな値にしても調査の精度に影響を与えないため、高温セルと低温セルの境界をぼやかして配置コストを削減するのに使う。
- 境界のぼやかしは適当に山登りをする（各セルの温度を現時点での状態から貪欲に設定するのを何周かする）と良い感じなる。
概ね S = 9 ~ 100 くらいで採用される。

出口セルの周囲にパターン形成戦略

出口セルの（自身を含む）周囲 9 マスを使いユニークな温度パターンを形成し、そのパターンを調査することで出口セルを特定する。
この戦略だけは 1 セルでの温度を 2~5 段階に分ける。
- 例えば 5 段階に分ければ、5³ = 125 > 100 なのでうまくいけば 3 つの相対位置で各出口セルを特徴付けできる。
調査を出口セルの周辺で済ませられるので、距離による調査コストの増大が抑えられる。
例によって調査を行わないセルは良い感じに温度をなだらかにする。
S = 1, 4 で採用される。

iwashi31’s diary

RECRUIT 日本橋ハーフマラソン 2023夏（AtCoder Heuristic Contest 022）やったこと