RECRUIT 日本橋ハーフマラソン 2023夏(AHC022)に参加しました。
atcoder.jp
問題は盤面構築＋推定問題。
結果は提出1070人中、40位（事前テスト51位）でした。
問題
対応が不明な入口と出口があるよ。
出口側の世界（トーラス空間）全体に空調を置いて温度調節して、温度を元に出入口の対応を求めてね。
不正解数や温度測定数&距離、温度の崖が少ないほど高得点だよ。
ちなみに測定温度には、平均0、標準偏差1～900の正規分布誤差が付くよ。
考察
正規分布の95%信頼区間とかを使って統計でなんとかする感じかな。複数の測定はベイズ推定っぽい。統計何も分からん、ベイズの表面だけなんとなく理解してるつもりの感じなので、統計入門がてらちょっと頑張ってみる。ちなみに「独立した確率を順に掛けていけば事前確率から事後確率が求まって、それがつまり…ベイズってやつなんだろ？」くらいの乱暴な理解です。間違ったことを言っていたら、優しくご指導いただけると幸いです。
さて、出口を特定するためには温度に特徴を持たせる必要がある。ぱっと思いつくのはQRコード。ソースコードと混同しそうなので、以後"模様"と呼ぶ。しかし出口が密集している場合は、模様同士を重ね合わせてそれぞれがユニークな模様になるように組まないといけない。*1 また、模様は温度の分解能（温度が何段階か）とマス数で表現できるパターン数が決まる。何段階目かが離れていたり、S（誤差の標準偏差）が大きいと、離れた温度同士の隣接を強いられることがある。この辺りをクリアするのは大事そう。
他の温度配置としては、全体で大きな1つの模様を形成する方法。初期段階で浮かんだのは、チェック模様を作り、線の間隔やタイプ（二重線や太線など）で何処の線かを知る配置。この時点では必要な温度差や測定が分からず、配置コストや測定コストは感覚で考えている。
測定は、出入口の対応を得ること、そのために第一候補と第二候補以降の確率に大きな差を付けることを目的とし、より多くの情報が得られるように。黒いのは直吊りするから占わなくていい。*2
入口に対応する出口を絞り込んでいって、ある程度絞ったら組み合わせまで行けたら上等かな。*3
温度差は、段階ごとに4S離すと誤認識には誤差2Sが必要で、つまり95%で誤認識が発生しないことになる。*4現実的には4S離すのは大変で、2Sになることも多いかな…。というか、S >= 512だと、そもそも2Sも差を付けられない。
実装
まずは任意の誤差が出る確率を求めるところから。注意点として、0や1000で丸められること、ケース生成時の端数処理方法も考慮する。検索したりchatGPTに聞いたりしながら、CDFというやつを使えばいいことは分かったので、注意しながら実装する。ここは大事なので、単体テストも組んでしっかりやる。正しい値のソースにはkeisanを使った。初期考察から終盤までずっとお世話になった。*5なお、うっかり新ジャッジでしか使えないライブラリを使い、提出時には確率を埋め込む形に変更した。
サンプルコード同様に10℃差を付けるコードから始め、下記グラデーション配置も試す。全体に満遍なく温度差を付け、配置コストを最低にするにはこんな感じだろう。計測は出口＋4近傍で、おおよその位置は分かるが4近傍隣接や斜め隣接などには弱いと分かる。遠くの山や谷を測定すればそれでも識別出来そうだが、誤差が多いと無理そうか。大きめの崖が必要なのかもしれない。あとは縦横に線を引いてグリッドも作るが、あまり芳しくない。簡単な実験はここまで。
初期グラデーション
ちなみに測定は、入口を固定して出口を特定する探索を行う。まずは各出口の相対尤度*6を1.0とする。これに、出口ごとにその測定結果が出る確率を掛けていく。…と、値がアンダーフローして全てが0.0になってしまう。そのため、新しい確率を掛ける際には事前確率のMax値で割ることにした。つまり、今回測定前の最尤値(?)を1.0とした相対値になる。絶対確率を求めるときは、相対尤度の総和に対する、ある出口の尤度の割合を取る。これで良いのか訝しみつつ、ここはそんな感じ。
測定位置は、出口の尤度を重みとして、測定位置の温度の重み付き分散 / 計測コストを評価にした。候補を半々に分けられる方がいいよねというお気持ち。400℃vs600℃より200℃vs700℃が優先されやすいなどの良くない部分も感じつつ、最後まで位置決めはこれで通した。
そして、ある出口の絶対確率が0.999に達したら確定とし、測定を終える。回数オーバー（この解法の場合は入口ごとに100回）でも終える。0.999は一見高く見えるが、0.999^100は90.5%程度なので結構攻めている。入口と出口の対応は1:1に限定していないので、組み合わせによる補正も得られていない。
模様作りを開始。下図のように、出口と4近傍の計5マスを4段階の温度に設定する。4^5=1,024なので、余裕を持って割り当て出来る。模様同士が重なる部分は両立させる必要があるので、カツカツだとどちらかの模様を壊すことになる。
また、中央セルをチェックサムにすれば計測誤差に強くなるはず。*7
初期模様
これだけでは温度ムラが大きく配置コストが大きいので、同じ温度が固まるように配置したい。配置コストを下げるための大きい配置は…さっきやりましたね。グラデーションを目標にし、目標や配置済みの温度との差を評価にして貪欲する。そして適当に4近傍との温度を平均化する処理を何回も回して温度を均す。*8*9
時系列が逆転するけど、このままチューニングの話も。上図のような十字型では隣接するセルとの大きな温度差を吸収できない。なので隣接ではなく2マス先を使うと温度差を吸収しやすく、スコアが増加した。最終的には全てのS <= 25のケースで採用された。
ちなみに、測定位置は模様の構成部分に限定しない。*10万一の模様重複対策も兼ね、模様外でも利用できるなら利用してねのスタンス。
模様埋め込みグラデーション
ここで初提出。Sが大きいケースに弱いのは覚悟していたが、1位の25%程度の相対スコアしか出ない。相対スコアの内訳を調査したい要求を抑えつつ*11、別の解法にも着手。
全体で大きな模様を作る図
上図は最終的に採用されたパターン。左の方が小さいS向けでS={36, 49}、右側はSが64～121の全てと、144～841の一部ケースで採用された。まず足元の測定で自分が属するエリアを知って、その後隣のエリアの温度や境界位置を調べに行く。
境界位置をはっきりさせたいので、温度はある程度の崖が必要そう。温度差は抑えたいが、時に明確な温度差を引き立たせて武器にすることも出来る。なんか聞いたことのある話だなと思ったら、ラーメン発見伝のつけ麺の話だった。良い本なのでお勧めです。
このパターンについてはそんなに語ることもないので、次のパターンへ。の前に、コストについて。Sが上がると温度差も大きくする必要があり、設置コストは指数的に上がっていく。一方で測定コストは、今までのパターンだとN（出入口数）やL（盤面サイズ）に依存するくらいで大体線形。それなら、設置コストを測定コストと同程度まで下げて、それにより測定しにくくなって測定コストが上がるのは構わない、とするのが賢そう。*12幸い今回のtesterは、各コストも出力してくれる。1000ケース回した結果をExcelで表にするとこんな感じ。
コスト
S（横軸）が200以上で設置コストが重く、特にSが400以上は測定コストを倍にしてでも設置コストを軽くしたい状態。0と1000が4つ隣接するだけで4,000,000も設置コストがかかるのに、4,000,000くらいまで設置コストを下げる方法なんてあるのか…？
1か所だけ高温
あったわ。
1か所だけ高温にすると、設置コストが最大4,000,000になる。測定は各出口から高温座標への相対座標だけ調べればいいし、対応を1つずつ決めるなら最有力候補の検証だけすればいいのも計算量に優しい。*13
最大100:100の対応を調べるが、対応が終わったものを除外すると約5050ペア、平均半分で見つかると考えると更に余裕がある。*141測定で特定出来るわけではないのでSが大きいと厳しいが、とにかくSが大きめのケースをカバー可能になった。
ただ回してみると、Nに対して測定コストが異様に多いことがある。*15ビジュアライザで追ってみると、高温部分を測定したのに誤差でハズレと判断され他の候補に移ってしまい、そのまま他の全てがハズレだと思うまで戻ってこないようだ。その時長距離の測定が入るのでロスが大きい。そこで、この解法パターンの時だけは出口に対応する入口を探すことにした。また、測定は短距離のものから行う。こうすると序盤にロスが出ても距離が短い測定で1周するだけなので、ロスが小さくなる。長距離の測定ならば既に候補数が減っているので、このロスも怖くない。
これで解法は一通り出そろい、あとはチューニング。
最後の解法は出口に対応する入口を決める都合上、誤答があると入口が浮くことがある。*16そこで他の解法も含めて、浮いたものや自信が無い回答に対しては余りから再度選び直して割り振ることにした。単純な出力違反回避と、消去法運ゲーによる誤答数軽減。追加測定とかもして良かったんだけど、体力不足でそこまで出来なかった。
コスト（最終）
最終的なコストはこんな感じ。もうちょっと設置コストの高い天才解法があるかと思ったけど、見つからなかった。
あとは目ptunaして、S、N、Lに相性の良いパターンを選んだりしておしまい。
他の人の解法を見て
トップ層を見ると、1～少ない点だけ温度を上げる（下げる）方針はそのまま、割と崖は無くしているように見える。測定が重なれば、僅差の温度差まで見抜いてしまえるということか。うちでは似たことをしても改善されなかったので、測定との噛みあいかなぁ。
それから入口ごとに個別に推測ではなく、組み合わせで評価している人も多い。これは精度が良くなるのは当然。
あとは測定の位置決めかな。統計に基づいてやってる人もいて、これも強いのは当然。
色々調べたいけど、パラメータが多様なことや相対スコアがあって、何が強く効いているのかいまいち分かってない。＋知らない統計用語が飛び交っていて、流石に全てを追いかけるのは厳しい。理解できそうなものからコツコツ調べていく。
調べておきたいキーワード
・対数尤度
感想
大層な手法は使わなかったけど、すごくマラソンしたという感想。1つの手法を突き詰めた人も多いけど、私は無数の配置を検証したので無限に疲れた。多分まだまだ出来ることがあるので、人生のハーフをマラソンできる。
問題は正規分布の扱いがちょっと大変なものの、何を求めたいのかは分かりやすいので調べながら参加することも出来て楽しかったです。
