AtCoder Heuristic Contest 025参加記
AtCoder Heuristic Contest 025
AtCoder Heuristic Contest 025に参加しました。 問題文はこちら↓ atcoder.jp
今回でヒューリスティックのレートが青色になりました！
問題文概略
- N個のアイテムをD個の袋に、重さができるだけ均等になるように分ける。
- アイテムの重さを直接知ることはできず、天秤を使って判断する。
- 天秤の左右の皿にアイテムを好きなだけのせると、{左に傾く, 右に傾く, 釣り合う} のいずれかの結果が得られる。
- このクエリをQ回行うことができる。
得点は、袋の重さの分散が小さいほど良い。
制約
- 30≤N≤100
- 2≤D≤N/4
- 2N≤Q≤32N
問題文を読んで思ったこと
- 最初に連想したのは、天秤を2回使って8枚のコインから軽い偽物を見つけ出す問題です。しかし今回の問題にはあまり関係なさそうです。
- 比較ができるということは、比較ソートができそうです。
- 暫定的な解を作ったとして、それの良さを判定するのが難しそう。
- 解の評価にもクエリ回数を消費してしまうので、焼きなまし法は向いてなさそう？
正の得点を得る
まずは正の得点を得られるコードを書きます。 なかなか解法が思い浮かびませんでしたが、人間がやるならどうするかを想像して、以下のように作りました。
- アイテムを各袋にできるだけ同じ数ずつ入れる。
- 以下をクエリ回数の限界まで繰り返す。
- 袋の重さを比較して、最も重いものと最も軽いものを探す。（クエリ D-1回)
- 重い袋からランダムにアイテムを一つ取り出し、軽い袋に入れる。
テスタの製作
クエリに応答したり、スコアを計算するためのテスタプログラムを製作します。 公式からも配布されていますが、多数のテストケースを試したり、結果を集計したりしたいので、自作しました。
製作したテスタで前項のコードを100ケース試してみると、平均スコア（低いほど良い）は6,413,402 (6.41M)となりました。 ここから改善していきます。
アイテム重量をざっくり推定する
袋に振り分けた後、重い袋から軽い袋へ移動するアイテムは、軽いものにしたいです。 そこで、初めにアイテムの重量を推定することにしました。
すべてのアイテムを重量順でソートするために必要な比較の回数はNlogN回くらいで、本問題の制約ではケースによってはクエリ回数が足りなくなります。
そこで、勝ち残り式トーナメントのように、アイテムを比較して重いほうを脱落させ、軽いほうを次のステージへ進出させます。何回戦まで勝ち進んだかを基準に、重量を推定します。1回の比較ごとに1つのアイテムが脱落するので、"優勝"を決めるまでに必要な比較回数はN-1回です。
平均スコアは5.67Mとなりました。
100回のテストのうち、最もスコアが悪かったケースのスコアとシード値を出力するようにしました。 最悪ケースの結果をビジュアライザで確認して、改良していきます。
重量を均等に割り当て
せっかく重量を推定しているので、初めに袋に入れるアイテムを選ぶときにも、推定重量を考慮して均等になるように配るようにしました。
平均スコアは5.62M、ほんの少し改善しました。
重いほうもトーナメントをする
これまでのトーナメント方式だと、半数のアイテムが1回戦敗退で、同じ重さとして推定されてしまいます。 そこで、軽いアイテムが勝ち残るトーナメントで1回戦敗退になったアイテムで、逆に重いほうが勝ち残るトーナメントを行って重量推定をするようにしました。
平均スコアは4.55Mでした。
良い解が得られた時点で終了する
ビジュアライザで観察していると、途中で良い解になったにもかかわらず、その後悪化するということがありました。
非常に軽いアイテムを最も重い袋から最も軽い袋に移動したときに袋の重さの最大最小が入れ替わった場合、アイテムの振り分けがかなり均等にできていると言えそうです。
一定以下の重さのアイテムを移動したことで袋の最大最小が入れ替わったら、その時点の振り分けの状態を回答とすることにしました。
平均スコアは3.98Mでした。順調に下がっているようです。
袋の重量順を保持しておく
これまでは、重量最大最小の袋を探すために全探索していましたが、これではクエリ数の無駄使いなので、袋を重量順に並べておき、アイテムの移動によって重量が変化したときには二分探索で挿入することで、袋のソート状態を維持するようにしました。
平均スコアは3.14Mでした。
トーナメント方式の"シード"の問題
100ケースのうち、スコアが最悪だったものを見てみると、非常に重いアイテムを非常に軽く推定していて、それを動かしたことでスコアが大きく悪化していました。
トーナメント方式なので、たまたまより重い相手とばかり当たっていると、重いアイテムが上位に勝ち進んでしまうことはあり得ます。しかし、それにしても異常な推定値でした。
当該ケースはアイテム数が65で、問題のアイテムは最後のNo.65でした。65は、2 ^ 6 + 1です。それを踏まえてコードを見ていると、重大な問題に気付きました。
トーナメント方式で次のステージに勝ち残るアイテムを決めるとき、残っているアイテム数が奇数の時は、最後のアイテムをトーナメントでいう"シード"のように、無条件で次のステージに進ませていました。
65個のアイテムでトーナメントを行うと、アイテム数は65 -> 33 -> 17 -> 9 -> 5 -> 3 -> 2 -> 1 となります。決勝戦以外ずっとアイテム数が奇数であり、最後のアイテムは不戦勝を続けることになってしまいます。
シードに選ばれるアイテムを、ステージごとに右端、左端交互になるようにしました。
（今振り返ると、ランダムにしてしまったほうがよかったと思います。両端は2回に1回シードになってしまうので。）
平均スコアは2.52Mでした。
Nに対してQが十分大きい時にはきちんとソートする
ケースのQがNlogNよりも大きければ、トーナメント方式ではなく、確実なソートができます。ソートした後にもクエリを残しておく必要があるので、余裕をもってQがNの10倍以上ある場合にはアイテムのソートを行うことにしました。
ソートアルゴリズムは実装が簡単そうなクイックソートにしました。
平均スコアは2.45Mでした。このあたりからテストケースを1000個試すようにしました。
行き詰まる
その後細かい改良を行い、平均スコアが1.64Mまで下がりましたが、そこで行き詰まってしまいました。最悪ケースを観察し、思いついたことを試してみても、何をやってもスコアが悪化してしまいます。
Q/Nが小さい時の重量推定方法として、アイテムをいくつか纏めて束にして、その束をソートするという方法を考えました。これを実装するにはコードの大幅な変更が必要なので、思い切って全面的に書き直しました。しかし、スコアはむしろ悪化してしまいました。
最後の3日間ほどは、取り組んでいたにもかかわらずスコアはよくなりませんでした。
結果
最終結果は265位、パフォーマンス1595でした。
AHC019以来青パフォとれていないので、取りたかったです。
感想と反省
- 前半は、100ケース試す⇒最悪ケースを観察する⇒改善する⇒効果確認 というサイクルを回してスコアを改善していけたのが良かった。
- 後半はスコアが伸び悩んだ。
- 最悪ケースにばかり注目したのが良くなかったかもしれない。
- 最悪ケースは不運が重なった極端に悪いケースなので、これに対応しようとして全体的に悪化してしまったのかもしれない。
- 平均スコアを指標にしたのが良くなかったかもしれない。
- 最悪ケースにばかり注目したのが良くなかったかもしれない。
