AHC003、参加しました。システス結果は1000人中20位でギリギリ順位表1ページ目。得点率は96.995%でした。

パフォーマンス（β）は2714で、レーティング（β）は2061 (+356)です。早々にアルゴのレート（2033）を超えてしまいました。最初のうちはレートがガンガン上がって楽しいですね。

f:id:terry_u16:20210603004237p:plain

問題概要
考えたこと
やったこと
日記
- 1日目
- 2日目
- 3日目
- 4～6日目
- 7日目
- 8～9日目
感想

問題概要

経路長とか全然測ってないけど道案内アプリリリースするぜ！
ユーザーを人柱にして精度向上させるからよろしくな！

atcoder.jp

この問題設定最悪すぎてめちゃくちゃ好きです。いや最悪とかそういうの抜きに純粋にとても面白い問題設定でした。普通に実社会に応用できそう。

考えたこと

「え、こんな問題も出るんだ……面白そう……！」というのが第一印象で、「でもどうやって解くんだ……？」というのが本音でした。

どうやって各辺の真の長さを推定するかという問題が非常に難しかったです。とりあえず与えられた情報を整理してみると、 $k$ 番目のクエリにおけるパス $P_k$ で通った辺 $E_l$ $(l=0, 1, \cdots, |P_k| - 1)$ の真の長さを $d_{E_l}$ 、ジャッジからのフィードバックを $F_k$ として、 $e_k(d_{E_0}+d_{E_1}+\cdots+d_{E_{|P_k|-1}})=F_k$ （ただし $e_k$ は $0.9\le e_k \le 1.1$ を満たす一様乱数）がクエリごとに与えられるので、これを制約式とみなして各辺の長さ $d_{E_l}$ を推定していけば良さそうです。

ここで、一様乱数 $e_k$ が仮に $1$ で固定だったとしても、辺の数は $30\times 29\times 2=1740$ 本なのに対し、条件式は最後までクエリに答えても $1000$ 本しか得られないので、制約式を単純に並べて連立方程式にしても不良設定問題となって解けなさそうです。ここをどう推定するかでかなり悩みました。

また最短経路問題部分はダイクストラでいいといえばいい*1のですが、探索と活用のバランスをどう取るかについても悩みどころでした。ちょうどCodinGame Spring Challenge 2021でDUCTを使ったので、同じノリでUCB1等が使えそうとは思ったのですが、いざ応用しようとするとモンテカルロ木探索のSelectionとは違って負辺が許容できなかったりでなかなか難しかったです。

やったこと

幸い入力生成方法が公開されているため、そのパラメータである $H_{i,p}, \delta_{i,j}, x_i,$ $V_{j,p}, \gamma_{i, j}, y_j$ （1920パラメータ）を全部力技で推定する回帰問題を解きました。 $M$ は $2$ で固定し（ $M=1$ のときは $H_{i, 0}=H_{i, 1}$ となることを期待しました）、 $D$ は気にしないことにします。

先ほど書いたように各クエリで制約式が与えられるので、 $e_k$ は無視してパスの推定値 $\sum_{l=0}^{|P_k|-1} d_{E_l}$ とフィードバック値 $F_k$ のMSEを最小化する問題を解くことにします。このままだと過学習を起こして $\delta_{i,j}$ や $\gamma_{i,j}$ の値が大変なことになるので、L2正則化項として $\lambda(||\boldsymbol{\delta}||_2+||\boldsymbol{\gamma}||_2)$ を入れて過学習しないよう調整しました。

MSEの最小化は数学的に解けるような気もしましたが、ただでさえよく分からないのに $x_i$ や $y_i$ が入ってきてかなり厳しい気持ちになったので、いつもの焼きなましで近似解を求めることにしました。ジャッジからフィードバックを受け取る度にオンラインで制約式を追加して、焼きなましを入れて推定値をアップデートします。近傍は $H_{i,p}, \delta_{i,j}, x_i,$ $V_{j,p}, \gamma_{i, j}, y_j$ それぞれの値の1点変更です。1クエリあたり2ms未満しか使えないはずですが、毎クエリだいたい $10^3$ ～ $10^4$ 回くらい回ってくれました。*2

また探索と活用のバランスですが、いろいろ試した挙句、「序盤*3は $k$ 番目のクエリで通った辺に $F_k/|P_k|$ を足していき、その総和+1を各辺のコストとみなす。中盤以降は各辺の推定コストをそのまま使う。」に落ち着きました。+1を付けるのは辺のコストが0になって変に遠回りするのを防ぐためです。多腕バンディット問題っぽくUCB1とかUCB1-TunedとかThompson Samplingとか色々試してみたんですが、微妙だったので泣きながら全部捨てました。

あとなんか画像のボケ除去っぽく逆フィルタを畳み込んだりできないかなーと調べましたが、うまく使えそうになく断念。

日記

1日目

問題を読むも何も分からず途方に暮れる。とりあえず $F_k/|P_k|$ の平均値を各辺のコストとみなしてダイクストラするコードを書いて暫定テスト89.33%（暫定31位）。

2日目

RMSEを最小化するような各辺のコスト（1740パラメータ）を直に焼きなましで求めようとするも、過学習を起こしてひどいことになる。*4各辺のコストの2乗をペナルティとして正則化するとようやくまともに動くようになって93.41%（暫定21位）。

3日目

せっかく入力生成方法が与えられているのでうまく活用したい気持ちになる。隣り合う辺同士のコストはあまり大きく変わらないはずなので、滑らかな分布になってほしいという願いを込めて隣り合う辺同士のコストの差の2乗をペナルティとするとスコアが上がって95.06%。10位に上がってはしゃぐ。

4～6日目

パラメータをいじいじするも大きく改善する気配がなく、本質改善しないとダメそうという気持ちになったので、いろいろ調べつつ考察だけ進める。あとから思えばここで立ち止まってじっくり考察できたのは良かった。調べ物は今回役に立たなかったけど、いつか使えるときのために覚えておきたい。

そしていつの間にか50位に落ちる。人々強い。

7日目

有給を取る。6日目までに $H_{i,p}, \delta_{i,j}, x_i, V_{j,p}, \gamma_{i, j}, y_j$ の全部を推定するゴリ押し解法の実装方針が固まったので、手始めに $\delta_{i,j}, \gamma_{i, j}$ 以外を推定するコードを書いて投げると95.97%で27位。 $\delta_{i,j}, \gamma_{i, j}$ の推定も入れると96.19%で20位。そこから人の手による温かみのあるパラメータ調整を入れると96.87%で8位に。

8～9日目

改善案が枯渇する。謎のヒューリスティック要素を入れたりダイクストラパートをちょっといじったりする。本質改善には繋がらず97.01%の19位でフィニッシュ。システスが回って96.995%の20位に。四捨五入して97%乗ったって言っていいですか？

感想

何度も言いますが、本当に面白い問題でした。そしてやっぱり統計とか機械学習の理論をちゃんと押さえてる人が強いなあという気持ちに。結局何もわからずゴリ押し焼きなまし解法で突き進んでしまいましたが、時間があるときにこの辺りを基礎から固めたいなあと思います。というかそもそも線形代数の知識から弱くて、 $\boldsymbol A \boldsymbol x - \boldsymbol b$ のL2ノルムの最小化だなーと思ってもどう解けばいいのか全然分からなかったのは反省点。勉強します……。