問題
戦略
パラメータによって「ソートを行う」「ソートを行わない」の2パターンに分ける。ソートを行う場合はマージソートを使ってアイテムのソートを行う。箱ごとの比較を行い最も重い箱の重量と最も軽い箱の重量の差分が小さくなるように更新を行っていく。
初期解生成
アイテムのソートを実行したかどうかで初期解の生成も変える
ソートを行わない場合
ソートを行わない場合の初期解の生成ではまず最初に N個のアイテムを均等に箱に入れて、その後に箱のソートを行う。
ソートを行う場合
アイテムがソートされている場合はまず大きい順から D個取り出して箱に 1つずつ入れていき、その後は総重量が一番小さい箱を選択して新しくアイテムを追加、再度並べ直して総重量が小さい箱を選択 -> アイテム追加の処理をアイテムがなくなるまで続ける。追加するアイテムは後半に大きな変化が生じないように重量の大きい順に追加していく。
並べ直すときは 2分探索で挿入する位置を求める。
アイテムの入れ替え
初期解作成後は箱の中のアイテムの入れ替えをクエリーが実行できなくなる or 更新が行われなくなるまで実行する。操作としては以下の 3つ
- 最も重い箱の中のアイテムを取り出し一番軽い箱の中に追加
- 最も重い箱の中のアイテム 1つと一番軽い箱のアイテム 1つを入れ替え
- 任意の箱のアイテム 1つと任意の箱のアイテム 1つを入れ替え
最も重い箱の中のアイテムを取り出し一番軽い箱の中に追加
一番重い箱の中からアイテムを 1つ取り出してそれを一番軽い箱の中に追加します。追加後、元の箱の一番重いものと新しく追加した箱の重量を比較して小さい場合は変更を採用します。（画像でいうと追加後の箱の重量が max のラインを超えてなければ採用する）
更新を行わないパターン （max のラインを超える）
max のラインを超えない = アイテムを取り出した箱も min を下回らない が確定するので 1回の比較で更新できるかどうかを判断することができる。
最も重い箱の中のアイテム 1つと一番軽い箱のアイテム 1つを入れ替え
最も重い箱のアイテムと最も軽い箱のアイテムの入れ替えを行います。交換する前の条件として 最軽量の箱から取り出すアイテムの重量 < 最重量の箱から取り出すアイテムの重量 をチェックする必要があります。（この条件を満たしていない場合は重量差が開くので）ソート済みの場合はこのチェックにクエリーを消費する必要がありません。
条件を満たしていない場合は重量差が開く
条件を満たしている場合は差分が縮まる。（重いアイテム - 軽いアイテム = X のアイテムを先端に移動させるというイメージ）
入れ替え後は最軽量の箱に追加した重量が max のラインを超えていないかどうかをチェックして超えてなければ採用します。
任意の箱のアイテム 1つと任意の箱のアイテム 1つを入れ替え
この操作は他の 2つの操作で更新が出来なくなった時に行います。交換する箱の位置が変わる以外は前の操作と一緒になります。
入れ替え後の操作
入れ替えが成功した後は再度ソートを行います。2分探索で挿入する箱の位置を探索してそこに挿入を行います。
再実行
山登りが終わってまだクエリーが実行できる場合はランダムにアイテムを入れ替えて再度更新を行います。ランダムに入れ替える際には必ず最軽量の箱か最重量の箱を含むようにします。（意図的に解を悪くして再度山登り）
再実行によって得られた結果が前の結果より良くなっているかどうかは 現在の最軽量の箱の重量 < 新しい最軽量の箱の重量 および 現在の最重量の箱の重量 > 新しい最重量の箱の重量 の両方が満たされているかどうかを確認します。 ( min max の差分が小さくなっているかどうかを確認と言っても良いです）
その他の改善
今まで説明した部分がスコアに大きく関与していて、後は細かい改善を重ねた。
二分探索の初期探索位置を指定
二分探索では最初は配列の中央から探索を行うが、特定の条件下では初期の探索位置の指定を行った。
初期解生成時
ソート済みのアイテムを箱に入れていく時に大きな箱から順に詰めていくため、最初は変動が大きくなるが後半は小さくなっていく傾向があるので初期の探索位置を最後に追加した位置から開始するようにした (1 - 2% 程度改善)
再ソート時
アイテムの操作を行って再度ソートを行う際に箱を 2つ挿入していくが 1つ目の箱の挿入位置によって 2つ目の初期探索位置を変えた。1つ目の挿入位置を pos1 とすると 2つ目の初期探索位置を D - pos1 + 1 に設定した。これは両者とも同じ値の増減が発生しているので pos1 の位置の反対部分に挿入されるだろうと予測した結果である。（2-3 %改善)
無駄な探索の排除
- ソート済みの場合にあるアイテムの末尾から先頭への移動に失敗した場合に、それより重いアイテムの移動を行わないようにする。(100% 失敗するので）
- 重さのオーダーが 10 と 20 のアイテムの交換に失敗した場合に 5 と 25 といった失敗したものより大きな差分が発生する交換を行わないようにする。
重さ推定
ソートしない場合でも事前チェックの際に一部のアイテム同士の比較は行うのでその結果からある程度の重さの推定を行った。と言ってもシンプルに 重いと判断された回数 - 軽いと判断された回数 というものである。最初は焼きなましでクエリーの結果と一致するように重さを変更するという操作を行っていたが判断材料が少ないのか全然安定して推定できなかったため諦めた。
最初にソート行うかどうかの判断
マージソートの比較回数 + 初期解生成時の比較回数 が Q を下回っているかどうかで判断。マージソートの比較回数については手元でサイズごとに数千回実行して一番比較回数が多いものを計測して配列で情報を持つようにしている、厳密に計算出来るけどなんか面倒なので諦めた。（どうせ数回程度しか変わらないと思ったので）
初期解生成中にクエリーがなくなってはダメだし、初期解生成後にまともにクエリー回数が残っていないのもダメなのでちょうどいい感じに調整するのが面倒だった。
感想
今回は絶対スコアでも相対スコアでもない順位スコアが採用されたコンテストだったので少し新鮮な気持ちで取り組んいでいた。ヒューリスティックでは点差から自分の方針がどれぐらいダメなのかを判断することができるが、それが出来ないのでとにかく良い解を作るしかなかった。提出したときにどれぐらい上位の点数が削れたかどうかで判断できないこともないけど難しいことには変わりない。
Q / N が低いケースだと十分な回数のアイテム操作が行えないのでかなりスコアがブレてしまう。そのため、100件のテストケースだとかなりスコアが変動することが多々あった。今回のスコア計算だとちょっと差分が出ただけでかなり点差が開くので絶対スコアも相対スコアも確かに採用するのが難しそうだなと感じた。そういった場合でも順位スコアであれば解決出来るのか〜と驚いた。
もっとクエリーをうまく使えば効率的に情報が得られたのかもしれないけど最後まで分からなかった。毎回ソートを行っているがこのクエリーの消費量がハンパじゃないのでもっと効率的に管理できたら良かったけど特に思いつかなかった。
期間中に DALL·E 3 が使用できるようになったのでブログに追加する画像のバリエーションがかなり増やせそうで嬉しい。
0 - 9 までのスコア
Seed 0: 40351 Seed 1: 27805 Seed 2: 1659 Seed 3: 2066 Seed 4: 118717 Seed 5: 782178 Seed 6: 5601 Seed 7: 16586 Seed 8: 1129610 Seed 9: 116495
