AHC025 ソートしない参加記
はじめまして。AHC025 Balancing by Balance に参加し、246位でした。
246位がどれくらい凄いのか分かりませんが、上位解法に興味がある方はさようなら。
ビジュアライザの使用を怠ったため本記事は白黒です。色にこだわる方はさようなら。
1. 問題概要
- AtCoderはロゴ入りの商品を販売している。
-
N D - 各商品の重さは未知だが、商品群を2つ作り、
Q
2. アプローチと試行錯誤
初期解を適当に決め、天秤を使って少しずつ良い解に遷移させるアプローチを取りました。
各アイテムの重さを推定する手法も頭をよぎりますが、天秤の試行回数が限られているため、そのままよぎり過ぎてもらいました。
まず初期解として、全ての福袋を同じ個数になるように上から分配しました。
-
絶対スコア：
\textrm{2,427M}
2-1. 改善したアプローチ
(1) 重い福袋から軽い福袋へ商品を移す。
- 福袋をランダムに2つ選ぶ。
- 天秤を使い、重い福袋を
A B - 福袋
A a - 商品
a B - 1~4をクエリ上限まで繰り返す。
-
1回の試行で必要なクエリ回数：
1 -
絶対スコア：
\textrm{1,632M}
このアプローチは必ず良い解への遷移が保証されていません。
(2) 重い商品と軽い商品を入れ替える。
- 福袋をランダムに2つ選ぶ。
- 天秤を使い、重い福袋を
A B - 福袋
A a B b - 天秤を使い、商品
a b - 1~4をクエリ上限まで繰り返す。
-
1回の試行で必要なクエリ回数：
2 -
絶対スコア：
\textrm{1,420M}
これも必ず良い解への遷移が保証されませんが、商品数が変わらないため(1)よりはマシなスコアになりました。
(3) 重い商品と軽い商品を入れ替え、改善されていれば遷移させる。
- 福袋をランダムに2つ選ぶ。
- 天秤を使い、重い福袋を
A B - 福袋
A a B b - 天秤を使い、商品
a b -
天秤を使い、入れ替え後の福袋
B' A'
- 1~5をクエリ上限まで繰り返す。
-
1回の試行で必要なクエリ回数：最大
3 -
絶対スコア：
\textrm{409M}
手順5を追加することで、遷移後が確実により良い解になるため、一気にスコアが上がりました。ただ、入れ替えしかせず福袋の商品数は変わらないため、まだまだ改善の余地はあります。
(4) 入れ替え成功後、片方の商品だけに移す遷移も試行する。
- 福袋をランダムに2つ選ぶ。
- 天秤を使い、重い福袋を
A B - 福袋
A a B b - 天秤を使い、商品
a b - 天秤を使い、入れ替え後の福袋
B' A' - 福袋
A' b B' - 天秤を使い、福袋
B' A' - 1~7をクエリ上限まで繰り返す。
-
1回の試行で必要なクエリ回数：最大
4 -
絶対スコア：
\textrm{321M}
入れ替えだけでなく、商品を片方の袋に移動する試行が増えることで、商品数の増減が考慮されスコアが上がりました。
(5) 初期解作成時、商品を軽い袋に優先して入れる。
- 途中までは、順番に福袋に商品を1つずつ入れていく。
- 残りの商品数が福袋の数と同じ
D
-
必要なクエリ回数：福袋の数
D -
絶対スコア：
\textrm{278M}
少しスコアが良くなりました。初期解作成にクエリを消費するため、アプローチやN,D,Qの数によっては必ずしも良いアプローチとは思えません。
(6) そういえばメモ化してなかった。
クエリと結果をメモ化することで無駄な天秤試行回数を削りました。
福袋に対応した商品を入れたリストを文字列化してソートすることで、左右入れ替えただけの天秤の試行も省くように気をつけました。
-
絶対スコア：
\textrm{190M}
(7) 入れ替えの時の遷移の判定が甘いことに気づいた。
入れ替え遷移後の福袋を
遷移確定の条件式を変えるだけでスコアが上がりました。
-
絶対スコア：
\textrm{169M}
その他、コスパの悪い悪あがき（チューニング）を行って、最終スコアは
2-2. 悪化したアプローチ
福袋をランダムに2つ選ぶ。を繰り返さない。
例えば(3)のアプローチであれば、以下の太字手順を追加します。
- 福袋をランダムに2つ選ぶ。
- 天秤を使い、重い福袋をA、軽い福袋をBとする。
- 福袋Aからランダムに商品aを選ぶ。同様に福袋Bから商品bを選ぶ。
- 天秤を使い、商品aが商品bより重ければ入れ替える。
- 天秤を使い、入れ替え後の福袋Bより福袋Aの方が重ければ入れ替える。
- 2~5を一定回繰り返す。
- 1からやり直す。
2~5の手順では遷移しないことが起きるため場合によっては効くかと思いましたが、あまり効果はありませんでした。
こんなことするより、ソートして確実に遷移できる商品を探していれば。。。
同時に移動する商品数を2個に増やす。
商品の数が多く、クエリ回数が少ないときに、扱う商品を2個セットにしてみました。しかしどのランダムセットでも改善できませんでした。商品は最小単位で細かく動かすのが、私のアプローチでは良かったようです。
最終2日、貴重な時間のほとんどをこの実装とデバッグに費やしてしまいました。。。
3. 直面したエラー
スコアの理解（頭のエラー）
順位表の相対スコアは数字が大きい方が高得点ですが、提出実行時にフィードバックされる点数は分散をもとにした絶対スコアのため、小さい方が高得点です。
途中までこれを勘違いして、アルゴリズムを改善しても得点が下がっていると思い込んでいました。
このエラーが発生した場合、急速にやる気を失うか、躍起になって改善を続けるかの２パターンが観測されていますが、今回は後者で助かりました。
Q回天秤で計っていない
初期解作成時に地味にはまりました。その後もWAが出たときは真っ先に疑っていました。
天秤に乗せられない商品群を天秤に乗せる
問題文にもはっきり記載されていますが、同じ商品を複数天秤に乗せたり、片方の秤に商品を乗せないということはできないです。頭ではわかっているつもりでも、発生してしまうことがありました。つまり何もわかっていない。
4. 結果と反省
結果は246位でした。私より点数の高い人が245人もいるなんて興奮します。
解法の反省
ソートを使うことに思い至れなかったのが一番の失敗でした。何故かクエリ上限にソートする余裕がないと思い込んでいました。アルゴリズムの勉強も並行して精進が必要です。
実装の反省
コードテスト・ビジュアライザーなど全く使わず、30分ごとに提出して得点だけで試行錯誤したので、効率がとても悪かったです。短期コンテストでは話にならないです。
終わりに
今回のスコアで茶色から緑色になりました。カビみたいですね。
Discussion