2024/02/09 から 2024/02/19 までの期間に開催された THIRD プログラミングコンテスト (AHC 030) に参加した。 この記事では今回の参加について振り返る。
問題概要
https://atcoder.jp/contests/ahc030/tasks/ahc030_a
N x N マスの盤面に M 個の油田がある。 このとき、油田のあるマスを全て特定せよという問題。
油田の大きさと形は事前に全てわかっている。 油田は重なって配置されることもあり、その場合油田が重なっているマスは重なっている数と同じだけの埋蔵量があるとみなす。
インテラクティブな形式の問題で、ユーザーに許されている操作は以下の 3 つである。
- 1 マス指定して掘り、そのマスの埋蔵量を確定させる。(コスト 1)
- k (>= 2) マスの集合を指定して占い、その範囲の合計の埋蔵量を推定する。 (コスト 1/sqrt(k))
- 油田があるマスの集合を解答として提出する。正解すればそのまま終了し、間違えるとコスト 1 を払って続行
油田マスを全て特定しないと基本的に点数がもらえない。できるだけ低いコストで全ての油田マスを特定することを目指す。
結果
プレテスト 149 位, 最終 143 位 (パフォーマンス 1871)
結果は抜きにしても、久しぶりのマラソンはやっぱり楽しかった。 時間かけて考察したわりにはあまり伸ばせず悔しさはあるが、次回以降に生かしたい。
https://siman-man.github.io/ahc_statistics/030/index_m.html によれば、M=4 から M=6 ぐらいのやや小さい範囲が 60 位台で順位としては最も良かったようだ。
最終的な解法
M が小さいケース (M < 9) と大きいケース (M >= 9) で異なる解法を実装している。
M が小さいケースは縦横独立に解く解法。 最初に全ての行・列の占いを一通り行い、占いの結果をもとに縦方向と横方向配置の解集合をそれぞれ独立につくる。 全体解の候補は独立に解いた縦方向と横方向の配置を組み合わせてつくる。 これらの解集合の間で埋蔵量が異なるケースが多いマスを特定して 1 マス堀り、その結果をもとに解をフィルタリングしていく。 基本的には解候補がひとつになるまで1マス掘り + フィルタリングを繰り返し、最終的に出てきた解を提出する。 もし有効な解候補がなくなってしまったら、予測の改善のため行, 列の占いからやり直す。
M が大きいケースは BFS ベースの解法。 こちらは占いと1マス堀りで場所を特定することを諦め、油田があるマスは全部掘って確認するという考え方。 掘りはじめる際の 1マスだけは観測範囲を狭めていく 2分探索的なやり方の占いによって決める。 1 マス油田を見つけたら、後は BFS で広げるだけ。
提出コード
https://github.com/sankantsu/competitive-programming/blob/master/ahc/ahc030/src/main.cc
日記 + 考察過程
序盤
コンテストは 2/9 (金) から始まっていたが、自分が参加を決めたのは翌日の 2/10 (土)。 その日は外出していたのだが、電車の中で atcoder のサイトを開いていて長期 AHC をやっていることに気付き、なんとなく久しぶりに参加してみようかなと思った。 競プロ自体かなり久しぶりで、最後に参加したのは algorithm 形式は 2022/06/26, heuristic 形式は 2022/07/03 と約一年半ぶり。 電車内ではコードは書けないので、とりあえず問題文を熟読するところから始める。
占いのコストが明らかに安いので、基本的に掘らずに占いのみで油田の場所を特定したいなという感覚はあった。 一方で、同時に全部のマスを特定しないと全く点数が貰えない形式なので初期方針の決定まで結構迷った。 素直には盤面全体を 3x3 とか 4x4 ぐらいのグリッドに区切って順番に占って、おおまかな配置を推定できるんじゃないかと考えたが、1 マス単位で配置を特定できる方針になかなか結びつかない。
そのうちに思いついたのが、縦方向の位置と横方向の位置を独立に解くという方針だった。 2 次元的な配置を解くのはパターン数が多くて大変なので、1 次元化して解いてからそれらを組み合わせたほうが解きやすいのではないかと考えた。
とりあえず 各行,列の埋蔵量の分布が必要なのでこれを推定するために最初にすべての行と列を一通り占う。
この時点でのコストは盤面サイズ N について (1/sqrt(N)) * 2N = 2 * sqrt(N) なので、だいたい 6 から 9 マスぐらい掘るぐらいに相当する。
これで精度の良い予測が得られるのなら、石油が埋まっているマスを全部掘るよりは大幅に安いコストで済みそうである。
一次元方向の解の生成については、全列挙した場合のパターン数が N^M。N は最大でも 20 なので M も 3 ぐらいまでなら全列挙が効きそうである。
しかし、M が大きくなると全探索は厳しいのでその場合はビームサーチ化するのが良さそうに思った。
探索途中も含めた評価値としては、全部配置した時点で (予測値) - (仮説) ができるだけ 0 に近づいて欲しいので、マイナスになった行にペナルティをつけていくことにした。
観測誤差の分布からして、あまり真の値からかけ離れたずれは発生しづらいはずである。
そのため、マイナスの絶対値が大きくなった場合は線形よりペナルティを大きくしたいと考え、マイナスになった行の絶対値の 2乗和をペナルティに使ってみることにした。
もしこの探索で正しい解が得られなければ、予測精度を上げるためにもう一周行と列の占いを行い、更新された予測をもとに再び同じように探索を繰り返す。
2/12 (日) までには一通り動く実装が完成し、1 回目の提出を完了した。 M が大きいケースはとりあえず全マス掘る bruteforce のまま。
中盤
ひと通り動くようになった実装について、M = 3 程度の小さい問題でもうまく解けていないものがあることがわかった。 Visualizer を使って観察してみると、eps の大きいケースでは観測の精度が悪く、全くはずれているわけではないものの真の配置から数マスずれたような解答になってしまっている場合があることがわかった。
予測が間違っていそうな行および列の精度を上げるために、これらの行, 列だけ占いの回数を上げるようなことはできないかと考えていた。 上位の解候補で値が異なる場合が多いような行, 列が観測精度を上げる価値が高いのではないかと思い、上位の解候補の集合について分散が大きいような行, 列を重点的に占うといった実装を試してみたが、思ったように点数を伸ばすことができなかった。 予測が間違っている行, 列を特定するということ自体が難しい上、仮にそれを特定できてもそもそも eps が大きいようなケースでは繰り返し観測したところで大して予測が改善しないという問題もあったのではないかと思う。
このようなケースでは占いだけで特定するのは諦め、有望そうな部分を掘る実装に切り替える方針を固めた。 とりあえず分散が大きい行, 列の占いを繰り返す代わりに 1行分まとめて掘ってしまうことにした。 これなら一気に解の候補が狭まるので、何行か掘ればほとんど必ず正しい解答に辿りつける。
一方、M が小さいケースですらこんなに苦労しているのだから、M が大きいケースは占いだけで解答するのはかなり厳しいだろうと判断し、それなりの数掘ってもいいので bruteforce よりはましな実装を考えることにした。 基本的に、1マス油田を見つければ幅優先探索で広げていけば隣接する油田は全て見つけられる。 最初の1マスを見つけるのに工夫がいるが、ここは占いでやることにした。 具体的には、最初は盤面を N*N/2 マスずつに2分割してそれぞれ占い、埋蔵量が多そうな方を選ぶ。 選んだほうの集合をまた 2分割してそれぞれ占い、また埋蔵量が多そうな方を選ぶ... という感じで占い範囲をだんだん縮めていく。 M が大きいケースは明らかに難しそうだし、テストケースの生成方法から M が大きくなるケースは少ないことがわかっていたので、あまり深追いせずとりあえずこれで完成とみなすことにした。
2/15 (木) まででこのあたりの実装を一通り終え、再び提出
終盤
観測誤差により正解を見つけられない問題について 1 行まとめて掘る方法で対処していたが、それではさすがにコストが高すぎるだろうと思って、なんとか掘るマス数を減らせないか考えていた。 思い付いたのは、上位の解候補で盤面の状態を比較し、予測が食い違うマスだけをピンポイントで掘って解を絞りこむというやり方である。
例えば 100 通りの解候補を比較して、あるマスについて
- 40 通りは 0
- 30 通りは 1
- 30 通りは 2
であったとすれば、そのマスを掘ることで悪くとも 40 通りまで解が絞りこめる。 このやり方はそこそこうまくいってスコアを伸ばすことができた。
残る問題は結局最初の行/列の予測精度によって解候補の質が大きく影響されてしまい、特に油田の数が増えてくると解候補の数も増えてくるため真の解が解候補から外れてしまうことであった。 探索のビーム幅を上げると時間が足りないし、前述のように占い回数を増やしてみても思うように予測精度は上がらない。 また、解候補が油田の探索順に依存していたので、探索順序をシャッフルするといったこともしてみたが、効果があったかどうかは微妙。
ある程度有望かもしれないと思ったアイデアとして、一気に全部の油田の配置を求めようとするのではなく油田をいくつかのグループに分けてそれぞれ解いたあとで組み合わせるというものを考えていた。 例えば、M=6 の問題であれば油田 3 つのグループを 2 つつくり、それぞれ独立に解いてから解を組み合わせるという具合である。 こちらも実装してみたのだが、グループが大きいと思ったよりもうまく解が見つからず、グループが小さすぎる (例えばそれぞれの油田 1 つずつを全部独立なグループとみなす) と一応解けるが、候補の絞りこみのために掘るマスが多すぎて BFS 解法と大差無いスコアになってしまっていた。 調整次第では使えそうな感覚はあったのだが、実装し終わったのが結構ぎりぎりなこともあってこのアイデアについては提出は断念した。
終了後
上位陣と比べるとスコアに歴然とした差があるのは明らかだったので、どういう解法を使っているのかについて興味があった。 終了後に writer の wata さんや参加者トップの terry_u16 さんが簡単な解説を出してくださっていたので早速読んでいた。 どうやら、問題をきちんと定式化し直すと占いの結果から事後確率が最大となるような配置を見つけ出すベイズ推定の問題と見なすことができて、どのような占い範囲を採用すべきかの評価については、その占いから得られる相互情報量として定量化できるということらしい。
こういう統計的なアプローチが全く考察の範疇に入れられなかったことは悔しいが、非常に面白そうな解法でもある。 エントロピーとか相互情報量とか、大学の講義で昔習ってはいたものの、どうやって応用できるのかいまいち理解できていない部分があった。 AHC の問題を通してこういった理論の応用例に触れることができるというのもとても面白い体験だと思う。 次にこの種の問題が出たときには考察のレパートリーに加えられるように、延長戦でいろいろ試してみたいと思っている。
