今まで統計・推定系の知識がほとんど無いままマラソン系のコンテストを戦って来たのですが、ACH022を経てさすがにこのままじゃ不味いなって気持ち*1になりました。
しかし、公式の解説動画を見ても(私の前提知識が足りなさすぎて)いまいち理解できず、どうしたものかなと思っていたところで、bowwowforeachさんの推定部分を重点的に解説してくれている記事を見つけました。 bowwowforeach.hatenablog.com
こちらがとても分かりやすく、この記事と合わせて改めて公式解説動画を見直したらそちらもある程度ピンと来ました。 おかげで実装できそうな気持ちになったので実際にやってみたら、ありがたいことにコンテスト時の8位相当のスコア*2を出すことができました。
ただ正直、上記２つの資料に沿って実装しただけで、かつ資料の出来もそもそも良いので、正直改めて書く内容も取り立ててはないんですが、 一応実装を通して得た、
- どの程度のことをするとどのくらいの順位になるかの情報
- もうちょっと具体的に、どう実装するかみたいな話
- 配置や計測の回し方の例
といった、本筋である推定の理論・説明以外のところの情報は提示することができそうなので、 補足的な立ち位置の資料として、同じように勉強する人の助けにならないかな、みたいな期待からその辺りを記述した今回の記事を作りました*3。
やったことと、その順位
やったことの内、ある程度スコア*4が向上した内容を節単位で列挙しています。
節タイトルは やったことの概要 (暫定テスト順位) って感じで振ってます。
以降の記述は、前述したbowwowforeachさんの解説記事（以降は「参考記事」と呼びます）の内容を把握していることが前提になります。
参考記事に書かれていることを素直にやる。配置や計測順序は割と適当。 (42位)
参考記事にある、「累積分布関数を使って入口出口の接続確率テーブルを作る」を素直にやると、配置や計測順序で大した工夫をせずともこの順位が取れました。（凄い）
以降は、配置と計測を具体的にどうしたかを書いていきます。
配置
公式解説動画にも出てきた、一点高温を作ってそこを頂点の山にする配置をしました。 以下の画像のような感じになります。
もうちょっと具体的には、
頂点の温度を1,000、その四方を500とし、以降は頂点からのマンハッタン距離が1離れるごとに 1000/L ずつ温度を下げていきました。
山の頂点の座標は、各出口からのマンハッタン距離の総和が一番小さいセルを選んでいます*5。
Sに応じたチューニングとかは特に無いです。
計測の回し方
入口をID順に計測対象にしながら*6、以下の手順を繰り返します。全ての行で最大値が閾値を超えたら終了します。
- 入口出口の接続確率テーブル(以降は「確率テーブル」と呼びます)の、対象入口の行の最大値が閾値を超えていない場合、
2以降を行う。 - 対象入口行の最大値の出口の座標から山の頂点に向けて計測を実行し、参考記事のやり方に沿って確率テーブルを更新する
- 確率テーブルの横方向の正規化を、全ての行に対して行う
閾値は98%にしました（seed 0~99で試して、誤回答が出なかったのがこの辺りのラインでした）。
縦方向の正規化 (24位)
公式解説動画*7や参考記事の最後の節に書かれていた内容になります。 実装が楽そうだったのでとりあえずやってみたら、かなりスコアが伸びました。
具体的には、計測ごとに以下を実施しました。
- 横方向の正規化を全行に
- 縦方向の正規化を全列に
- 横方向の正規化を全行に
（正規化の掛け方として適切なのかは不明です。）
閾値の変更 (20位)
42位解の計測の周し方節内で出てくる閾値の値を98%から95%に下げました。
縦方向の正規化を入れたお陰なのか、閾値を下げても誤回答が出なくなったので*8、計測コストを下げるためにこうしました。
計測序盤は山の頂点に近い出口を優先して扱う (17位)
公式解説動画で出てきた、近い出口から扱う手法*9を部分的に導入しました。
具体的には、
- 頂点からのマンハッタン距離が10以下の出口を列挙する。
- 手順
1で列挙した出口に対して、距離が小さい順に手順3を実行する - 対象の出口の確率テーブル列の最大値が95%を超えるまで、「その列の最大尤度の入口を計測対象として、出口座標から山の頂点を指す計測」を繰り返す。
- この際正規化は、24位解の手順から
3を省いたものを行う*10
- この際正規化は、24位解の手順から
上記の手順を終えた後は、前節までと同様の手順で計測を進めて完了です。
情報が少ない序盤ほど、確定までに計測回数がかかるはずなので、序盤に距離の短い計測が集まるようにこうしました。
元々は、「距離が10以下の出口」ではなく「全ての出口」を対象にするつもりだったんですが、やってみたところ期待通りにはいかず23位に落ちてしまいました*11。
2024/03/14 追記
実装をミスっていて、対象の出口をきちんと列挙できていないバグが埋まっていたことに気づきました。
8位解に対してここの修正を入れたら、6位に上がりました。確認はしていないですが、この時点でも17位より良い順位になるかもしれません。
Sが小さいケースで山を緩やかにする (8位)
ここまで配置の仕方は42位解のもののままで固定していましたが、
手元の試行結果を見ると、Sが小さいケースで配置コストがネックになっていたので、計測容易さよりも配置コストの低さを優先するようにしました。
大筋の方針は節タイトルの通り、Sが小さいケースで山を緩やかにする感じです。
具体的には、42位解の配置をベースに、Sの大きさごとに以下の変更を加えました。
S <= 36- 山の頂点の高さを600に下げる
- 傾斜の温度を
1000/Lずつ下げていたところを、500/Lずつに変更*12
49 <= S <= 100- 山の頂点の高さを700に下げる
- 傾斜は
1000/Lのまま変更なし
S >= 121- 変更なし
これで8位スコアを取ることができました*13。
もう少し調整は頑張れる気もしましたが、一桁順位を取れて満足したのと、統計・推定系の知識を学ぶっていう復習の趣旨から外れつつあったので、ここで復習を終えることにしました。
終わりに
率直にやるだけでも42位が取れてびっくりしました。やっぱり知識って大事だな、とか数学の力って凄いな、とかを思いました*14。 コンテスト時に必死こいて作った自作解法はなんだったのだろう、みたいな気持ちにもちょっとなりました*15。
統計・推定の知見が元々ほとんどなかったのですが、分かりやすい資料の存在のおかげで無事に実装することができました。本当にありがたいです。
今回の取り組みを通して、推定系問題への苦手意識もある程度取り除けた気がします。 次に推定系の問題が出たときは良い順位を取りたいな。
*1:レートの伸び悩みだったり、コンテスト後Twitterタイムラインの理解できなさだったり。思ってたより統計・推定の知識が求められる問題の出題頻度高いな、とかも思いました。
*2:暫定テストで
*3:あとは単純に、良いスコアが出たのが嬉しくて何か書きたくなったというのもあります。
*4:暫定テスト順位を基準に見てます
*5:計測コスト削減のため
*6:ID末尾を迎えたら先頭に戻ってループする
*7:51:40~ あたり
*8:100ケースしか試していないので、たまたまそうだっただけかもしれないです。
*9:37:20~ あたり
*10:横->縦->横 でなく、横->縦 で終える。
*11:手元で見た感じ、Sが大きいケースで計測コストが上がっている傾向があるように見えました（100ケースしか試してないですが）。
*12:緩やかかつ範囲を広くするイメージ。
*13:暫定テストのスコアを指標にチューニングした感はあるので、本番テストの順位はこれより低い気がします。
*14:小並感
*15:ちなみにコンテスト時の暫定テスト順位は134位でした。
