AtCoder Heuristic Contest 025参加記録
こんにちは。競技プログラミングをしているssaattooと申します。AtCoder Heuristic Contest 025に参加して 25位でした。
反省、または誰かの為になることを期待して参加記録を残します。
問題概要
n個のアイテムを天秤をq回使用して、できるだけ均等にd個のグループに分割してください。
解法
大まかな解法は以下の通りです。
- 初期解を作成する（qによって2パターン）。
- 暫定解の最も重いグループから最も軽いグループに1アイテムを移動させる、またはアイテムをスワップすることを繰り返す山登り。
- その他の工夫（過去の比較から明らかな比較には天秤を使用しない。など）
これで暫定テストで94.5%程度の点を得られます。
初期解作成パート
まず、qが小さいときについて解説します。d個のグループにランダムにアイテムを割り当てた後、グループをその総和でソートします（d logd回天秤を使用）。
qが大きい場合は、アイテムをソートします（n logn回使用）。その後、最も小さいグループに最も大きいアイテムを追加し、グループをソートします。これをすべてのアイテムを追加し終えるまで繰り返します。これだけでかなり均等に分割することができます。
貪欲パート
1アイテム移動。グループa<グループbのとき、bからaにアイテムcを移動させようとするときにスコアが改善する条件は、a<b-cです（図2左）。この条件を満たすときは必ず移動させます（1回使用）。a>b-cだった場合は、スワップできるかを試みます。
２アイテムスワップ。グループa<グループbのとき、aのアイテムdとbのアイテムcをスワップするときにスコアが改善する条件は、a-d<b-cかつd<cです（図2右）。そのようなdを探してやるとよいです。qが大きくアイテムをソートしているときはc未満の最大のaの要素をdとしました（１回使用）。
解が改善された時はグループをソートしなおしました（d logd回使用）。
その他の工夫
qが大きい場合、アイテムがソート済みなのでその情報をうまく使いたいです。ソート済みの情報をそのまま用いた場合、小<大+小などの比較は明らかですが、小＋小<大という比較は自明ではありません。そこで、入力と同じ方法で重さの組を1200個作成して、1200個すべてで成り立つような比較は天秤を使用せず判断できるようにしました。
うまくいかなかったこと
いくつかの比較結果から焼きなましで重さを推定して、多数決で比較結果を予想するということを試しました。左右の差が10%以上あるようなときは99%程度の精度で予測できましたが、遅く、また重要である僅差を予測できなかったので諦めました。
日記
メモなので汚いです。
目標
考察を頑張る。上位が無理そうなら早めに撤退する。
コンテスト１日目
問題を読んだ。苦手そう。
クエリ数2Nがどのくらいきついのかが見当がつかない。天秤に載せた集合の重さの和がある程度特定できるのか、個々の重さが特定できるのか全く分からない。重さの推定は指数分布からあり得そうなように予想すべきか。
重みが正確にわかっているとき、厳密解は求められるのだろうか。dpとか？とりあえず山登りで高速にそれなりのグループ分けはできそう。
一つ一つの大小関係はn logn回の比較回数で求められる。あまったら適当に２個１個の比較をして、それを満たすように重さを生成。山登りでグループ分けを計算。時間が無くなるまで生成と山登りを繰り返して、平均スコアが最も低くなるようなグループ分けを出力。
ソートができないなら、２個を１個にまとめる。
上の方法を実装して初提出。65AC35WAで49%143位。WAはqがn lognより小さいときに無視してソートしているから。余った回数は無駄にしている。方針が違いそう。
明日すること。最初にいくつかの商品を塊にできるようにする。余った回数を有効活用し、その結果にあう重みを生成できるようになる。
コンテスト２日目
最初にd個に分割してソート。最大グループから最小グループに１個移すのを繰り返せばよくなる？ある商品cを移す場合、最小グループ<（最大グループ-c）なら改善する。
上のものを提出。4WAで88%40位。
バグを直して0WAで91%29位。
最大グループを最小化すればいい？
局所解っぽいのにはまると脱出できていない。適当なswapは意味があるのか。
グループa, bがa<bでそれらの要素caとcbがca<cbで(a-ca)<(b-cb)ならswapで改善する。１点移動では受理されない場合でも受理される場合がある。これは１点swapである必要はなく、何個かずつでも可能。
１点swapを実装して96%12位。
最大と最小で交換をできなくなってしばらくしたら最大グループを別のでも許可するようにして96.89%5位！
乱数で作っているので、既に比較したやつを比較しているかもしれない。hashで重複除去してとりあえず無駄をなくそうと思う。
qが小さいとき最初のグループのソートいる？２つの大小を判定すればそれでよくないか。
場合によっては、クエリをやりきってもその情報から改善できるかも。
既に探索済みのやつを比較しなくしたやつを提出。97.1%で7位。qに余裕があるやつはほぼどうしようもないくらい良い解が出てそう。
比較結果から合法な重みを生成して山登りは無理があるのかな。時間を有効活用したい。
明日すること。多対多のswapを実装。余った時間の有効な使い方を考える。qが小さいときの良い方法を考える。
コンテスト３日目
既存の比較結果から他の比較結果を計算してみる。実装したけど悪化。ミスってないことを確かめたけど、スコアにはほぼ影響なし。多対多のスワップも改善せず。
統計取る。スコアは重みを知っているときの焼きなましをbestとする相対評価の方が良さそう。けど焼きなましが貪欲に負けているっぽい。
全ケース11人に負けている場合、現在の534人の提出者数だと97.9%だから、苦手なケースがあるということ？
統計取った。横軸がlog((q-最初のソートにかかった回数)/n)、縦軸が対数スコア。やっぱりqが小さいケースを何とかした方がいい。log((q-dlogd)/n)が閾値以下のときはソートしない方がいいのかも。
ｑ小さいやつはソートしないようにしたら悪化した。
n個をソートするのではなく、上位n/2個下位n/2個を把握できたら便利かも（nth_element?）。まだ変更していないブロックから２個選び、小の小と大の大のswapが比較０回でできるから。大体２ｎくらい比較しているから無駄っぽい。
ordのソートはまとめてでもいいかも。比較無しでswapできるやつがあるなら優先した方がいいかも。
qが大きいときは、ｎ個をソートして、空のグループに小さいグループから詰め込んでいったものを初期解にしたら微増して97.0%で11位。
クエリ回数を使い切った後も、各グループ１回は小さいグループの比較済みの小さいものとswapすることができる。いやこれは嘘。悪化する場合もある。
ｑごとに提出して苦手を把握してもいい。
コンテスト４日目
１個と１個同士の推移律を実装した。そんなに効果なし。
高速だから、ハイパラを入れまくってoptunaを最後にするべき。
qn<1.7のみ提出で19ケースで18.176%。１ケースあたり95.6%で苦手ぎみではあるけれど思ったより高い。qn>4.0のみで19ケース18.37%。1ケースあたり96.6%。
qを10000回に増やしてみたらスコアは4倍くらいになった。効率のいい探索が必要。
一つ一つをソートしたものをw0,w1,..、としたときの差分di=wi+1-wiを求めるのはどうか。差分があれば焼きなまし的にできるかもと思ったけど。
かなり小さい＋かなり小さい＜かなり大きい、みたいな嘘情報も事前にあたえたら効率よくなるかも。
現在のスコアをmax block - min blockと近似すると、そのスコアはmax blockとmin blockに含まれない物で二分探索でlognで見積もれる。破壊する前にスコアを見積もって、破壊して貪欲後にスコアを見積もる。これで局所解から脱出できる？w0未満は計測できないことに注意。
コンテスト５日目
kickがうまく動作しない。
小さい2d個くらいは（それだけはソートして）探索中はブロックに含めなくて、最後に降順に追加するのは。
ソートして降順に小さいブロックに追加していく初期解が強すぎるから、qが小さいやつにもこれを適用したい。
焼きなましで重さを適当に作った。評価値は正解した数で９割くらい。これは未知の比較に関しては７割だった。これって焼きなまし解を100個作って多数決したらかなりの確率で正解するってこと？99%で成功するようになったけど、1%の嘘のせいでそれでも悪化する。
コンテスト６日目
意見が100%一致するのはクエリ中９割くらいで、そのほとんどのケースで100%の精度を達成していた。つまり、わからないクエリだけqを使用してほかは予測ですれば実質qを10倍にできるということか？
もしかしたらほぼイコールみたいなやつは把握できていないのかも。→その通りで、10％以内の差を区別することが難しかった。よってこの解法は忘れるべき。
提出。95.77%で16位。qが小さいときを何とかしたい。qを半分近く消費したときに焼きなませばどのくらいの精度が出せるんだろう。
コンテスト７日目
qn<1.7のみ提出で19ケースで17.822%。１ケースあたり93.8%。苦手らしい。
パラメータ調整してもあまり伸びそうにないからやる気が出ない。いい改善が思いつくのにかける。
コンテスト８日目
2点swapは大グループの要素未満の最大の要素でするのが貪欲としては最適だと気が付いた。いや最適ではないか。１％くらい改善。
提出。95.40%で21位。
q小さいときでも使える効率のいい方法が欲しい。
sympyというものを見つけたけど、これは役に立ったのだろうか。
コードを整理したらスコアが悪化した。なぜ。
コンテスト９日目
パラ調整して94.90%で20位。
終わりに
良かった点
- プロトタイピングがうまくできた。
- あたり方針を引くのが早かった。
悪かった点
- 2日目からほとんど改善できなかった。
- 小手先改善にばかり時間を費やしていた。
- パラメータ調整が雑。
順位表から粗点の差がわからなかったのでずっと手応えがないまま問題を解いていました。おそらく過去最高順位と初橙パフォーマンスですが、実力がついたとかではなくよくわからないまま終わりました。最初の方が順位が良かったからなんとか食らいつきたかったです。
わかったこととしては、私がプロトタイピングが上手になっていることで色々な方針を試せるようになってたことです。それは嬉しいです。
今回のような貪欲や推定問題ではなく、純粋に実力バトルになりやすい焼きなましで橙以上パフォをとれるように頑張ります。
