こんにちは。競技プログラミングのコンテストに参加しているyunixです。 HACK TO THE FUTURE 2023本戦(https://atcoder.jp/contests/future-contest-2023-final)に参加して3位でした！競プロを始めてから2年半、初めてのオンサイトのコンテストでとても楽しかったです。運営・参加された方々ありがとうございました。

コンテスト中にやっていたことを、提出履歴を見て思い出しながら書いていこうと思います。

問題の概要

めちゃくちゃでかい無人島(半径10⁹の円)に50個の財宝が埋まっています
どこに埋まっているかわからないので、高橋くんはダウジングマシンみたいな木の棒を使って宝を探すことにしました。木の棒は以下のような性能をしています:
- 木の棒は無人島の好きな位置に立てることができます
- 木の棒から10⁶以内の位置に財宝がある場合には木の棒は倒れずに、財宝がそこにあることがわかります
- そうでない場合には、財宝のどれかの方角に棒が倒れます。ある財宝が選ばれる確率は木の棒との位置の距離の2乗に反比例します。
  - 方角には微妙に誤差があり、σ(0.001 ~ 0.1 rad)の正規分布で誤差が乗ります
最大で1000回棒を立てることができるので、できるだけ多くの財宝を見つけてください
- 50個全部見つけることができたら、クエリの回数をQとして10,000 - 5Q点
- F(<50)個しか見つけることができなかったら100*F点が得られます。

最初にやったこと: (~1:00) 1,100点

問題文を読んで、ビジュアライザのマニュアルモードで遊んで何をやればいいかふんわりと把握しました。

ぽちぽちビジュアライザで遊んでいると、以下のような探し方の規則を見つけました:

① 棒の倒れた方向から、その近くの財宝のありそうな場所の推測がつきます。
② その方向にある程度すすんで、逆方向に棒が倒れたら宝が2つの木の棒の間にありそうだということがわかります
③ 移動距離を小さくしながら①, ②を繰り返します
④ 最終的に財宝を見つけることができます

このように二分探索の要領で範囲を絞っていけばうまく財宝を見つけられそうです。もちろんこれだけだと幾つか懸念があって、

毎回最寄りの宝の方向に矢印が向くとは限らない(特に探索の初期フェーズでは)
どのくらい進むかの調整が難しくないか

などの点を解決しなければいけなさそうです。

ここまで考察したところでまずは正の得点を取ることにして、とりあえずランダムに棒を立ててみました。無人島の半径が10⁹、棒の守備範囲が10⁶なので、1つの棒が宝に当たる確率は大体50 * 10^-6です(50は宝の数)。 1回の問題で1000回棒を立てることができ、採点されるテストケースが200問あるので、

$200*1000*50 * 10 ^{-6} = 10$

となり、全体で10回くらい宝を見つけて、1000点くらいもらえそうです。これで提出したところ、1100点といかにもそれらしい点数がついて、問題の理解等が正しいことが確認できて安心しました*1。

次にやったこと(~1:30) 435,500点

前の考察から、とりあえず矢印の方向に向かうと良さそうだということがわかります。以下のような方針を実装してみました:

ランダムに位置を選ぶ
矢印が倒れた方向にランダムな距離を進む(10⁶ ~ 2*10⁷の範囲)
財宝を見つけたら最初に戻る
これを制限いっぱい繰り返す

前の棒が倒れた方向に10⁶ ~ 2*10⁷までの距離をランダムに選択して進む(10⁶単位)

進み方は遅々とした感じですが、きちんと最寄りの財宝のところまで吸い込まれて行ってくれています。これで大体問題につき20個くらい財宝を見つけることができるようになりました。順位表のスコアは400,000点くらいで当時10位くらいに入っていたような気がします(細かいところは覚えていない)。

お昼ご飯(~2:00)

ちょうど区切りが良いところまで進んだのでお昼を食べることにしました。 HTTF本戦では主催者のフューチャーさんがお昼ご飯のお弁当を用意してくれていました。サンドイッチ弁当やハンバーグ弁当など何種類か用意してくれていたのですが、青椒肉絲弁当をいただくことにしました。美味しかったです。

二分探索的な探索を実装(~4:00) 1.2M点 <-これが最終解の基本方針になりました

次に最初にビジュアライザで遊んでいた時の方法を実装することにしました。これができれば大体人間と同レベルになれそう。大まかな方針は以下のような感じです:

宝箱を一つずつ探していきます
ランダムに棒を立てます
前の棒が倒れた方向に、比較的大きめなステップ(2*10⁸)で進んで、2本目の棒を立てます
- 2本目の棒が1本目の棒の方向に倒れたらその間に財宝がありそうです。このような向かい合う方向に倒れる棒のペアを作成することができれば次のフェーズに進みます。
  - 向かい合うの正確な定義は、2本目の棒が倒れた方向を $\theta_0$ 、2本目の棒から見た1本目の棒の方向を $\theta_1$ としたとき、 $|\theta_0 - \theta_1 | \lt 3 \sigma$ としました。
  - これは誤差こみで考えたときに、2本目の倒れた方向に1本目があるか、というような考え方になっています。
- 2本目の棒が1本目の棒と違う方向に倒れた場合、2本目の棒を1本目の棒だと思って処理をやり直します
1本目と2本目の棒の間に宝がありそうです。したがってこの間を二分探索します。
- $d$ を1本目と2本目の間の距離とします
- 以下の処理を財宝を見つけるまで繰り返します
  - d = max(10⁶, d/2)とします(二分探索の要領で探索幅を小さくしていく。ただし10⁶より小さくしても無駄なのでそれよりも小さくしない)
  - 最後に置いた棒の倒れた方向にdだけ進んだ場所に棒を立てます。
  - 財宝を見つけたら処理は終了。財宝が見つからなかったら繰り返しの最初に戻ります。
  - $d$ が最小の状態が3回以上連続した時も探索を終了します。これは一度間違えた方向に進んでしまうと探索はばが小さくなっていく一方なので、変なところに収束してしまうことがあり、それを打ち切るための処理です。

他にも色々考えたのですが、これがシンプルで実装しやすかったのでまずはやってみることにしました。思ったよりも良いスコアを出すことができて、この時点で5位くらいとか?でした(記憶が曖昧..)。全部やらせるとこんな感じでした。669ターンで探索が完了していました。

袋小路からの脱出・パラメータ調整(~5:00) 1.33M

前の節の解だと以下のような状況で無駄になってしまうことがありました: このような状況に陥ると、探索回数の上限に引っかかって打ち切られるまで無駄に探索を続けることになってしまいます(10回くらい)。

このような状況を防ぐために、2回連続で同じ方向に移動するときには、移動距離を半減させることはせずに、逆に倍にするようにしました(ただし上限を10⁷)。これを入れると以下のような効果があります:

コンテスト後に調べたところ、この処理を入れると点数が1.20M -> 1.28Mくらいまで伸びるようです。また、コンテスト中には同時にハイパーパラメータの調整(最初の移動距離など)も行ったので、1.33Mくらいになりました。一瞬だけトップになったこともありました*2。

探索の初期距離を可変にした(~6:00) 1.37M

探索の初期の距離を常に一定にし続けるのはあまり良くない気がして*3、

序盤では大きなステップで動かすと、幾つも宝の候補があるので、矢印がなかなかペアを作らない。探索幅は小さい方が好ましい。
終盤では残りの宝が少なくなっているので、ランダムに選んだ初期位置から宝の位置までが遠く、また他の宝が少ないので矢印が同じ方向を向きやすい。したがってこの場合は探索幅が大きい方が好ましそう。

このように考えて、探索の最初のステップをKを見つけた財宝の数として、 $A_0 + A_1 * K$ としました。 optunaにパラメータを選択させたら $A_0$ ~ 5*10⁷, $A_1$ ~ 4*10⁶ となりました。初期の頃には5*10⁷, 終盤では2.5*10⁸とかなり大きくステップ幅を変えるような感じに落ち着きました。

この他にも各種ハイパーパラメータを調整させてスコアが少し伸びました(1.37M)。この時点で2位か3位くらいだったと思います。

虚無 + 乱数調整 (~8:00) 1.388M

改善策を色々考えて試してみたのですが、いまいち有効に働かず、スコアが伸びませんでした。有力な改善策だと思われたのは、探索途中の棒の情報を再利用するもので、探索の途中でそっぽを向いた棒(つまり見つけた宝とは別のところを指していたような棒)を集めて、それから見つかっていない宝の方向を推測するような感じです。実装がいまいちだったのか、スコアを伸ばすことができませんでした*4。

これを実装している間、1.37Mの解の乱数の種を変えて上振れを期待して提出していました*5。運よく1.388M点になるシードが引けて、これが最終的なスコアになりました。

最後に

結果的に3位という信じられないくらい良い成績を取ることができました。自分がまさかAtCoderのコンテストで一桁の順位を取ることができるなんて少し前までは想像もできませんでした。

ただ、コンテスト後の懇親会の際にwriterのwataさんが解説をしてくれたのですが*6、それを聞くと自分の考察が浅くてアドホックな解決策に頼りがちだなあと反省することしきりでした。今回はたまたま良い順位を出すことができましたが、まだまだ頑張らないといけないなあと思いました(小並感)。

tsukammoさんはじめ、フューチャーさんの多くの方のおかげでコンテストをとても楽しむことができました。ありがとうございます。来年も本戦に出れるように頑張りたいと思います。

次回も対戦よろしくお願いします*7。

追記: writer解について

コンテスト後の懇親会でwriterのwataさんの解説を聞く時間を設けていただきました。解説がとてもわかりやすかったのと、凄まじいスコア(154M???)を出しているのでビビりました。主に(1)宝の探索方針 (2)宝の位置を統計的に推定するの2つの工夫をされていました。会場で話されていたこととwriter解を読んで理解したことを簡単に書こうと思います。

宝の探索方針

本記事の方法だと、上図の左側のように矢印が挟んだ比較的広い領域のどこかにあることしかわかりません。 wataさんはこの方法だと効率が悪いよね、というようなことを話されていて、右側のような探索方針を採ったそうです。

1本目の棒を立てて、財宝はその方向にありそうだとあたりをつける
2本目の棒を1本目の棒の方向とはちょっとずらしたところに置き、1本目の棒と直交するような方向を向かせる

図を見るとわかるようにこの方法だと2回のクエリでかなり狭い領域に限定することができています。この方法だけで152Mの点数が出るそうです。

実際にやろうとすると2本目の棒をどれだけ離した位置に置くんだとか、2本目の棒がそっぽを向いてしまった時にいつ探索を諦めるんだとか細かい話を詰めないといけませんが、確かに合理的な方法に思えます。言われてみれば簡単に思えるし、思いつけなかったのが今となっては結構悔しいような気がします。wataさん以外にも最上位層はこの方針を採用しているのではないかと思います(ちょっと確信なし)。

宝の位置の統計的推定

上記の探索だけでもかなりの点数は出ますが、ルールベースなので処理が一瞬で終わってしまいます。時間を有効に使おうとした時に採用したのが、40個の宝を見つけた時点でそれまでのクエリを再利用して残り10個の宝の位置を推定する、ということだったそうです。

ひと目でわかる、wataさん解法のヤバさ。154代らしい。 pic.twitter.com/WBSc1H4P4b
— ツカモ (@tsukammo) 2022年12月10日

上の図はwataさんが解説で最後の10個の推定位置を赤点で表示した時の様子です。白い十字が宝が埋まっている地点なので、かなりの精度で推定ができていることがわかると思います*8。

解説では詳細について触れていなかったのですが、writer解を読んだところ最尤推定をしているようでした。 twitterには簡単に投稿をしておきました。詳しく聞きたいところがあったらコメントに書いてください。

やったぜ #HTTF2023
writer解を読んで残り10個の場所を推定するやつそれっぽくなりました。半分くらいは推定できている気がします。
気がかりだったやつができて満足。宿題ができたので安心して年を越せる。
本業の北海道の農業の最適化を頑張ります。 pic.twitter.com/jB0PlhsvBM
— yunix (@yunix91201367) 2022年12月27日

*1:つまらないバグを作ってしまって無駄に30分くらい使ってしまったのですが...

*2:今からでも5時間1分20秒のコンテストにするのはどうでしょうか?

*3:writer解も似たような工夫をしていてちょっと嬉しかった

*4:方向性は悪くない気がするので、実際のやり方が悪かったんだと思うのですが...

*5:短期コン典型

*6:wataさん解: https://atcoder.jp/contests/future-contest-2023-final/submissions/37130892

*7:年末はKaggleのサンタコン、コドゲ、日立北大コンなどマラソンが多くありますね(MM142は出れなさそうです...ごめんなさい)。どれに出るか決めていないのですが、頑張りたいです。

*8:会場ではどよめきが起きていました...

yunix_kyopro’s blog

HTTF2023 Dowsing Rod 本戦参加記録