AHC025 解説
AtCoder Heuristic Contest 025 のコンテスト中に考えたこと、あと提出での改善内容について書いています。
暫定で順位スコアが89,650,691,241点で72位、システムテストは順位スコアが448,637,004,602点で69位相当の解法になります。
方針立て
問題文を読んだ感じは、確率分布が与えられているのでベイズ推定するのかと思いましたが、クエリの発行回数がかなり少なく難しそうだという印象でした。
全てのアイテムについての重さの順位づけをするだけでも最悪$${N\log{N}}$$程度かかるので、$${Q}$$の値が小さいパターンだと確率分布からの推定が到底出来そうにないと感じました。
逆に$${Q}$$が多い場合では、全てのアイテムについての重さの順位づけをした上でまだたくさんクエリを発行できるような状態になります。
全てのアイテムについての重さの順位づけさえ出来てしまえば、確率分布をもとに実際に値を生成して、その値をアイテムの実際の重さだと思って$${D}$$個の集合の初期化ができるようになります。
順序づけの後に残ったクエリについては、絶対スコアをなるべく小さくするために「一番重い集合」から「一番軽い集合」へアイテムを渡して、大小関係が変わらなければOKとする、で改善していけそうです。
$${Q}$$が少ない場合については前述の通り全部を順番づけすることは出来ないので、絶対スコアに影響の大きい、重いアイテムから決めていくことにして、比較回数が足りなかったらそこで順序づけを止めてそれっぽく順序を決めればいいか、と考えていました。
ただ、それでは$${Q}$$の少ない場合では他の人より順位スコアが悪いだろう、ということも認識していました。
色々考えていましたが初日は収拾がつかず、二日目は予定が入っていたため長時間考えていたわけではないですが、いろいろな場合を考えていると方針がしっちゃかめっちゃかになっていました。
順位表の方も観察していましたがなんとなく普段と違う感じで、過去に類題がない感じなのかと思いながら見ていました。
その中で逆に方針が決まり、
$${Q}$$が大きい場合については順位づけしてから「一番重い集合」「一番軽い集合」の差を小さくしていく
$${Q}$$が小さい場合については大きい方から可能な範囲で順位づけをし、順番が決めきれなかったアイテムについてはそれっぽく順番づけする。
具体的にはヒープソートを途中までやって、順番が決まらなかったものはヒープソートの2分木の根の方から順番に重いものとして扱う上にあげた方針は「一旦この方針で」くらいつもりで、根本から変わることがあることを前提にして、実際に動かして改善をしていく
としました。3については身も蓋もない方針ですが、きちんと覚悟をしておかないと、期限が決まっている中で最初に考えた方針を根本から変えるのは割と躊躇いやすいので方針として入れました。
結局どうなったかは次の通りです。
最終解法
処理の流れを記載しました。なかなかカオスです。
$${Q}$$が小さい場合($${Q \lt N\log{N}}$$)
各処理の説明について、
①記載の通りに初期化します
②差を小さくしたいので、重さ最大の集合のアイテムを1つずつ見ていき、「重さ最大の集合から現在見ているアイテムをのけた集合」の方が「重さ最小の集合」より小さければ、2つの集合間でそのアイテムを交換した際に両集合の差は小さくなります。そのような場合にアイテムを渡します。
③②と同じ話で、重さ最大の集合から出すアイテムの方が重さ最小の集合から出すアイテムの方より重い、という前提で、それぞれのアイテムをそれぞれの集合から取り除いた状態で重さ最大の方が最小の方より重ければ交換することで差が小さくなります。
④③と同じ話で、③でもクエリが余るケースがあったので追加しました。
⑤②で対象としていた集合をランダムにしただけです。seed25のように1つのアイテムで平均を超えたりするとうまくいかなくなることがあったので追加しています。
⑥③で対象としていた集合をランダムにしただけです。重さ最大最小と同じようにしたかっただけです。
そんな感じで最初に立てていた方針からガラッと変わってしまいました。こうなったのは
$${Q}$$が大きい場合でいい感じになってきたな、というタイミングで$${Q}$$が小さい場合のテストケースを落として得点具合を確認したところ、落ちたテストケースの割に得点がそこまで減らなかったので、他の人と比べてうまくいっていないことを確認、根本的に方針変更。
$${Q}$$が大きいケースも同じだが、ランダム等色々順番を試した結果、重さ最大と最小の集合の差を埋める方が絶対スコアが良くなりやすいことを確認、最大最小で極力アイテム交換するようにした。
それでもクエリ数が余ることがあったので、ランダムを入れた。
というふうにした結果、このような処理の遷移になりました。
$${Q}$$が大きい場合
①方針に書いた通りヒープソートをして、アイテムの大小関係を決めます。アイテムの確率分布がわかっているので、それを元にデータを$${N}$$個分生成するのを$${10,000}$$セット実施。$${10,000}$$セット分で平均をとったものを小さい順にアイテムに当てはめていきます。
②$${Q}$$が小さい時の②・③を合わせた形になります。①の処理があるおかげで$${Q}$$が小さい時と比べてこれ以降の比較回数が激減しています。
③重さ最大の集合から選択したアイテムに対して、重さ最小の集合の中でそのアイテムより小さいアイテムを①の処理を行なっているため列挙できます。その組み合わせを全て試しながら重さ最大最小の集合間の差を減らせそうなら減らします。
④②で対象としていた集合をランダムにしただけです。クエリ数が余るケースがあったのでこの処理を入れています。
④③で対象としていた集合をランダムにしただけです。クエリ数が余るケースがあったのでこの処理を入れています。
そんな感じで最初に立てていた方針から随分着膨れした感じになりました。こうなったのは
ランダム等色々順番を試した結果、重さ最大と最小の集合の差を埋める方が絶対スコアが良くなりやすいことを確認、最大最小で極力アイテム交換するようにした。
クエリ数が余るケースが目立っていたので、③のような処理を入れています
$${Q}$$が小さい時と比べてヒープソートでの比較を行なっているため、集合を改善する処理でクエリの発行数が減りました。そのため処理の遷移でも極力②の処理から始めるようにしています。
そんな感じです。
$${Q}$$が大きいとgif容量が大きくなったり、$${D}$$が小さいとあまり動きに面白みがなかったりしたので、動きが良さそうなseed372126の結果のgifを載せます。
他気をつけたこと
テストケースが$${5,000}$$ケースある、ツギハギ実装になっている、という状態だったのでテストは一応気をつけました。