概要
AtCoder Heuristic Contest 025に参加した記録です。
珍しいインタラクション問題。
方針1：ナイーブ実装
とりあえずシンプルな解法を考えて実装するところから着手した。以下のような解法になる。
- 最初、各グループは1つずつアイテムを持つ。残ったアイテムはすべてグループ0が持つ。
- s=0とする。
- グループsが他のグループに順番に1個ずつアイテムをランダムに渡していく。
- グループsがグループiにアイテムを渡したとき、グループiがグループsより重さが大きくなったら、s = iになって、再度3を繰り返す。
実装上の注意点として、
- アイテムが0個のグループを作ってはいけない
- 他のどのアイテムを足し合わせても敵わないような激重アイテムが1個ある場合、そのアイテム1個を唯一持つグループが出来上がる。このグループからその激重アイテムを取るとアイテムが0個になってしまうので取ってはいけない。
シード1の結果
提出コード：https://atcoder.jp/contests/ahc025/submissions/46658987
得点：1,163,992,256
方針1の問題点は、「アイテムを1個ランダムに選んで渡す」とき、重いアイテムを渡す可能性があることにある。できれば軽いアイテムをやりとりして各グループの重さがならされるようにしたい。
ここで、クエリに2つのアイテムの大小関係を尋ねまくると、（アイテムの重さは不明のままだが）いずれアイテムをソートできることに気づく。アイテムがソートできた状態になると、各グループの一番軽いアイテムがわかるので、軽いアイテムを選択してやりとりすることで微調整できるようになる。
ソートアルゴリズムはクイックソートを実装した。
実装上の注意点として、
- クイックソートは最悪クエリ回数が(N-1)N/2 回かかる
- クイックソートでクエリ回数を使い果たさないようにしなければならない。今回は実装が簡単のため
N*10 <= Q のときクイックソートするのに十分なクエリ回数があると判断するプログラムとした。十分なクエリ回数がない場合、ナイーブ実装に切り替えた。
シード1の結果
提出コード：https://atcoder.jp/contests/ahc025/submissions/46693668
得点：811,781,427
今回の問題は得点が小さいほど良いスコアとなるので、改善されたと言える。
方針2の改良。クイックソートに使えるクエリ回数上限を設定できるようにして、上限に達したら途中でソートを打ち切る。打ち切ると順番が中途半端にわからないアイテムがあるが気にしない。
アイテムの交換に使える最低クエリ回数を D*3 くらい（各グループ3回くらいアイテムのやりとりをするくらい）は確実に残すようにして、あとはクイックソートに使えるように設定した。もちろんクイックソートが早く終わればアイテムの交換に使えるクエリ回数は増える。
これにより方針1のナイーブ実装の実行を完全に排除できた。（運次第だと思うが、ナイーブ実装のほうが良いスコアのサンプルがちらほらあったが……）
提出コード：https://atcoder.jp/contests/ahc025/submissions/46697190
得点：586,051,759
このあと、アイテムの交換に使える最低クエリ回数の値をいろいろ試したところ、D*5 が最もスコアが良かったので最終的にそうした。
Seed 29を考察した。
方針3のシード29の結果
シード29は完全にソートされているにも関わらず、あまり良くないスコアになっている。
たとえば、左から5番目のグループは軽いアイテムをたくさん持っているにも関わらず、それらを貯め込んで一番重いグループになっている。こいつのグループが他のグループに軽いアイテムを配ってくれればもっと良いスコアになるはず。
分析の結果、全1423ターンのうち、509ターン目でソートが完了し、残り約900 ターンでアイテム交換をしていた。アイテム交換に十分のターン数があるにも関わらず、スコアは良くない結果になっている。
もっと深く考察するために、途中結果を出力して確認してみる。
ソート完了直後の状態
ソート完了直後は上の状態となった。
1回目のアイテム交換
一番左と、左から3番目のアイテムの交換が行われた。
2回目のアイテム交換
一番左と、左から4番目のアイテムの交換が行われた。
これを見ると、重いグループ同士で無駄な交換が起きているように見える。なので、クエリ回数が十分に残っている場合（最悪交換回数の(D-1)*D/2以上の場合）、各グループの重さでソートし、「重いグループと軽いグループで交換を行う」ということをすれば良さそうである。
すなわち今回の方針では、グループの重さのクイックソートを実装した。
提出コード：https://atcoder.jp/contests/ahc025/submissions/46748553
得点：602,827,302
スコアが悪くなってしまった。
方針5：方針4の改良（残りクエリ回数を十分取るときだけグループのソートをする）
方針4では、残りクエリ回数が十分にあるときだけグループのクイックソートをして、そうでないときは方針3に切り替えるように調整した。それでもスコアが悪かったので、何がいけないのか出力ファイルを比較して原因を探った。
悪くなったサンプルを比較してみる。
以下の分数は、(アイテムのソートで使ったクエリ回数)/(全クエリ回数)。
シード7の比較。
278/294
左が方針3、右が方針4
シード8の比較。
175/197
左が方針3、右が方針4
シード16の比較。
206/221
左が方針3、右が方針4
良くなったサンプルを比較してみる。
シード1の比較。
306/1120
左が方針3、右が方針4
シード18の比較。
368/1028
左が方針3、右が方針4
他にも比較したが割愛。
比較してわかったのが、 (アイテムのソートで使ったクエリ回数)/(全クエリ回数)の値が大きい （＝アイテムのソート後に残ったクエリ回数が少ない）と、グループのソートに使えるクエリ回数が少なすぎて方針3より悪いスコアになってしまうらしいということ。
つまり残りクエリ回数が十分にあるときだけグループのクイックソートをしていたつもりが、まだまだ全然足りなかったということらしい。
残りクエリ回数がQ/2以上のときだけグループのクイックソートをするように変更した。
提出コード：https://atcoder.jp/contests/ahc025/submissions/46748977
得点：543,035,466
方針3よりスコアが良くなった。
上記の方針5では、方針3よりサンプル100個中、
- 5個スコアが悪くなった
- 31個スコアが改善された
- 64個はスコアが変わらなかった
方針6：残りクエリ回数に応じて確率的にグループの重さが切り替わるようなアイテム交換を許す
方針5では、64個はスコアが変わらないのであった。これは、アイテムのソート後に残りクエリ回数が少ないので方針3に切り替わった個数が64個ということであった。
方針3の問題点はなんだろうかと、いくつか悪いスコアのものをピックアップしてみた。
seed62: 157/185
シード62の結果
seed66: 438/482
シード66の結果
ビジュアライザを動かしてみると、残りクエリ回数が少ないときにもグループ間の重さが入れ替わるような重いアイテムの交換を許してしまっていた。
残りクエリ回数がまだ残ってるときはグループの重さが入れ替わってもいいが、残りクエリ回数が少ないときはグループの重さが入れ替わるようなことはせず、軽いアイテムのやりとりだけで済ましてほしい。イメージ的には『安定』したやりとりをしてほしいという欲求がある。
なので、残りクエリ回数に応じて確率的にグループの重さが切り替わるようなアイテム交換を許す実装をした。気持ち的には焼き鈍し法である。
方針7のシード62の結果
方針7のシード66の結果
かなり良くなった感じがしたので、提出した。
提出コード：https://atcoder.jp/contests/ahc025/submissions/46841307
得点：492,973,943
方針6を最終結果として提出した。
A：58,654,377,877
A-Final：300,672,027,666
順位：458
ここまでの感想
- 方針5を実装した時点での相対スコアが62Gで、順位は380位くらいだった。この得点帯は激戦区で、寝て起きたら順位が結構下がっている。
- 方針5を実装した時点で頭打ちしてると思ったのだが、上位陣が90Gで途方もなかった
- 「山登り、焼きなまし、ビームサーチは絶対にできないよな」「いやしかし…」とぐるぐる考えてた
- 方針6は発想としてはかなり焼き鈍し法なのだが、これに至るまでかなり時間を要した。
公式解説
公式解説動画のリンク
X（Twitter）で調べると強い人はソートして一番重いものと一番軽いものを交換している人が多いイメージ。似たようなことは自分もしているのだが、自分の解法では一番重いやつと軽いやつを交換、2番目に重いやつと軽いやつを交換、…としていたのが良くなかったのか？
公式解説の動画を見てみる。
- 解法1：クエリを使ってがんばって重さを推測する。その後クエリを使わずに最適化問題を解く
- 解法2：焼きなまし法（近傍解を求めて、その近傍解が良くなったら採用。悪くなったら悪くなった度合いに応じて確率的に採用）は、今回の天秤を使ったクエリでは「どれだけ悪くなった」かがわからないので難しい（「悪くなった」はわかるが「どれだけ悪くなったか」はわからない）。が、「良くなった」のは判定できるので、山登り法が可能
- 解法3：初期解を貪欲法で作る
公式解説では解法2の山登りを解説してくれた。
山登り法
2つのグループ間でアイテム交換をするの図（公式解説動画から引用）
2つのグループの大小関係がわかっている状態で、アイテム交換をする。アイテム交換後、2つのグループの大小関係が変わっていなかったら、「スコアが良くなった」といえる（2つのグループ間の分散が小さくなっているので）。
基本的にはこれをひたすら山登っていけばいい。
この解法のシンプルな手法ではソートすら必要なくて、アイテムをランダムに1個選び、それをどこのグループに入れるかもランダムに選ぶ。アイテム交換してスコアが良くなるなら交換し、スコアが良くならないなら交換しない。
初期解は各グループ同じアイテムの個数になるように適当に割り振る。
これをすると321位がとれるらしい。
うーーーーーーーーーん。シンプルな解法に見えるが、これでも十分自分より良い点数が取れるところを見ると、考察力が足りないと感じる。やってることは「言われてみれば当然といえば当然」のことなのだが、思いついてないんだよなぁ。
アイテム交換方法2
もうひとつのアイテム交換方法として、グループAとグループBからそれぞれアイテムを1個ずつ取り出して、取り出したアイテムをアイテムa、アイテムbとする。
このとき、「グループA < グループB」「アイテムa < アイテムb」ならば、アイテムaはグループBに入れ、アイテムbはグループAに入れるとスコアが良くなる。
アイテムaはグループBに、アイテムbはグループAに入れるのが良い
このようなアイテム交換はクエリ2回の発行で行える。
「この交換法も50%の確率でする」みたいに組み合わせると218位に入れるらしい。
キャッシュする + 推移律のグラフを作る
一度した交換方法はキャッシュして覚えて、2回もしないようにすると地味に良くなる。
アイテム交換方法2をすると、アイテムの大小関係のデータが蓄積していく。
a < b のような大小関係のグラフを作っておくと、a < b と b < c => a < c のように、クエリを発行しなくても推移律で新たに大小関係が判明する。
推移律からa < cを導く
もっとやろうと思えば以下のように導くこともできる。
a<b と b+c<d から、a+c < d も判明する
こういう不等式系がたくさんあったときにすべて満たす解を求める方法にLP（線形計画法）があるらしい。
それをしなくても「アイテムa+cとアイテムdの交換」といった複数個の交換が可能になる。
これを実装すると200位になる。
グループのソートを実装する
これまでの方法の問題点は、交換するグループをランダムに選んでいたのが問題であった。
そこでグループのソートを実装すると、どのグループがアイテムを交換すべきなのかがわかる。
一番重いグループと一番軽いグループがアイテム交換するのが良い
アイテム交換後のグループのソートは単純にやればO(DlogD)。けどこれは以下のようにして改善できる。
一番重いグループをグループA、一番軽いグループをグループBとする。アイテム交換後、グループAとグループB以外の他のグループはソート済みなので、「グループA（B）は、ソート済みのグループのどこに入るか」を2分探索すればO(logD)で済む。確かに……。
これをすると49位になる。
公式解説の感想
- 公式解説を見ると、「なぜこれが思いつかなかったのか……」といった感想になった。ソートなどそれっぽいことは思いついて実装できているのだが、初期の解法の土台が良くないのでスコアが伸びなかった印象。論理的な道筋が見えていないのというか。練度が足りない。
