第8回 Asprova プログラミングコンテストに参加したぞー
結果はなんと1位！
解法を紹介します。
問題
解法
スコア計算に使用するパラメータa,bがテストケースごとに与えられます。
- a＝ハンガー付外しコスト
- b=空きフックコスト
- a+b=100
まずa,bが極端な例を考えてみると
a=99, b=1 のとき
1度置いたハンガーは外さない。使用するハンガー数をできるだけ少なくする。製品の完成はちょっと遅くても大丈夫。
a=1, b=99 のとき
ハンガー付外しは何度行ってもいい。とにかく隙間を開けずに製造し早く完成させる。
というように真逆の解法が必要そうだったので、aの値によって解法を切り替えました。
解法①：aが大きいとき(a>=19)
- ハンガー形状順と製造する色の順序を決める
- ハンガーの配置を決める
- シミュレーションしてスコアを算出
- ハンガー配置と色順をちょっとずつ変える焼きなまし
1. ハンガー形状順と製造する色の順序を決める
形状順は、形状切り替えにかかる時間の総和が最小になるような順番にする。bitDPで最適解を出せる。
色順も同様に、色切り替えにかかる時間の総和が最小になるような順番をbitDPで算出。
2. ハンガーの配置を決める
ハンガーの配置を「ハンガー数」「右スペース数」という2つの情報で表現する。
ハンガー数の決め方
- 全形状、ハンガー数1で初期化
- ハンガー数から各形状の製造完了までの周回数を算出。周回数が一番多い形状のハンガーを1個増やす
- これを一定のハンガー数になるまで繰り返す
こうすると全形状の周回数が大体同じになる。
右スペースの決め方
- 全形状、次の形状への切り替え時間分のフック数で右スペース数を初期化
- 一番右スペース数が少ない形状の右スペースを1増やす
- これをハンガー数と右スペース数合わせて250になるまで繰り返す
3. シミュレーションしてスコアを算出
決めたハンガーの配置と色順通りに作業をシミュレーションする。
作業の遅れている形状の作業が進むように、途中で製造を止めたりして調整する。
作業の進捗が次の形状と同率の時、作業を譲るかどうかは製品ごとに「譲るかフラグ」を持たせてそれで判断する。このフラグは焼きなまし中に変えていく。
4. ハンガー配置と色順をちょっとずつ変える焼きなまし
変え方（焼きなまし近傍）
- 形状の順番を2点入れ替え（選択率7%）
- 色の順番を2点入れ替え（選択率7%）
- 2つの形状のハンガー数と右スペース数を1～3個書き換え （選択率17%）
- 2つの形状のハンガー数を1個書き換え（選択率12%）
- 2つの形状の右スペース数を1～2個書き換え（選択率29%）
- 1製品の作業を譲るかフラグを切り替え（選択率29%）
選択率はOptunaを使用して調整。
出力例
解法②：aが小さい時(a<19)
製品セットという単位に分ける
1000テストケースでこの分け方を試したところ、製品セット数は22～195個だった。手頃な個数かも。
これで製品セットをどの順で製造するかという問題になった。
この問題を2段階の焼きなましで解く
- 製品セットの大まかな並び順を決める焼きなまし（540ms）
- 細かい調整をする焼きなまし（1350ms）
1段階目の焼きなまし
- 貪欲法により製品セットの製造順を決める
- 候補の製品セットの製造を全部試し評価値を算出。一番評価値の高い製品セットを次に製造するものとして確定。これを繰り返して全部の製品セットの順番を決める。
- 評価値
- (A)時間当たりの製造数
同じ時間で沢山製造できていた方が良い - (B)「形状毎の進捗率」の分散
全ての形状の作業進捗が同じぐらいが好ましい - (C)ハンガー付け外し回数
付け外し少ないほうが良い
- (A)時間当たりの製造数
- 順番が決まればその通りにシミュレーションしてスコアを計算できる
- 貪欲法の評価値(B)(C)に重みパラメータをつける。このパラメータをちょっとずつ変える焼きなましを行う。
一番スコアが高かった製品セットの順番が2段階目の焼きなましの初期値となる
2段階目の焼きなまし
変え方（焼きなまし近傍）
- ランダムな範囲の作る順番を逆転させる（選択率33%）
- 2つの製品セットの順番を入れ替え（選択率33%）
- 連続している3つの製品セットの順番入れ替え（選択率8%）
- 1つの製品セットの順番を変える（選択率6%）
- 同じ製品の製品セット同士で作る個数を変更（選択率11%）
- 同じ製品の製品セット同士で作る個数を変更、を2製品同時にやる（選択率9%）
製品セットの順番を変える近傍と製造数を変える近傍がある
順番を変える近傍
製造数を変える近傍
出力例
その他工夫
- 焼きなましの近傍選択率をOptunaで調整するというのをやってみた。スコア更新頻度の大きい近傍の選択率が高くなるのかと思っていたが、全然違う結果になったのが意外だった。
おしまい
