第9回 Asprova プログラミングコンテスト に参加しましたー
1位でしたー！わーわー
コンテストページ
※問題文はコンテストに参加登録した人しか見れません
解法
稼働パターンの扱い
各週の稼働パターンは1～9の9パターンで平日/祝日それぞれ指定しますが、平日/休日を組み合わせて9×9=81パターンとして扱うことにしました。
この81パターンを稼働時間でソートすると、稼働時間をn段階減らす、増やすといった操作ができるようになります。
パターン同士のコストを比較すると「稼働時間は少ないのにコストが高い」といったパターンが見つかります。これらは無駄*1なパターンとして除外します。
すると30～36パターン程度まで減らせます。
さらに等間隔に間引いて26パターンぐらいにしました。（最終日にやってみたらスコア上がったから採用。コスパが悪いほうから順に間引いたほうがよかったかも。）
ファイナライズ
計画プログラムからのフィードバックで重要なものとして作業負荷率があります。これは稼働時間に対して実際に作業が行われた割合を示しています。
これがもし0%であれば全く作業が行われていないということなので、稼働を行わない稼働パターン1変えてしまって問題なさそうです。*2
そこで「すべての設備について、後ろの週から作業負荷率が0%が連続している範囲を稼働パターン1で埋める」という操作を考えます。フィードバック後に常にこの操作を行うことで確実に稼働パターンを減らせてスコアを上げることができます。
この操作をファイナライズと呼ぶことにします。
さらにファイナライズした状態のスコアをファイナライズスコアと呼ぶことにします。
※稼働パターン変更回数の上限に引っかかって稼働パターン1で埋めることができない場合もあって、実装は結構大変でした。
手順１：大まかに稼働パターンを決める
全設備/全週の稼働パターンをまとめて変更して出力、というのを二分探索的に繰り返し、納期に間に合い稼働時間のできるだけ少ない稼働パターンを見つけます。
ぎりぎりの境界を見つけるよりは、大雑把（途中で探索を打ち切る）なほうがスコア上がりました。
手順2：ちょっとずつ稼働パターンを減らしていくループ
(1)操作候補リスト作成
次の操作を候補とします。
- 1つの設備の全部の週の稼働パターンを1/2/4/8/16段階減らす
- 1つの設備のある週以降の稼働パターンを1/2/4/8段階減らす
- 1つの設備の1つの週の稼働パターンを1/2/4段階減らす
(2)操作候補の評価値算出
操作候補リストの操作すべてに対して評価値を算出します。
評価値はまず、操作後の設備稼働率を見積もり（前回のフィードバックの設備稼働率か大体計算できる）し、これを使って操作後のファイナライズスコアを算出します。
そして以下の情報を混ぜ合わせて評価値を算出します。
- ファイナライズスコア
- 操作によって後ろの週にずれる作業時間
- 設備番号
- 変更する段階数
- 変更する週の種類（全週 or 複数週 or 単週）
- 変更する週の数
- 計画プログラムとのやりとりの回数
- 手順2の試行回数
このような評価値になった経緯
ファイナライズスコアが高いほど良いけど、納期遅れになる確率が高いなら良くない。
納期遅れになる確率って推定できる？フィードバックされる情報からだと難しい気がする。大量のテストケースで事前学習しておくのがいいんじゃない？
ちゃんとした機械学習はできる気がしないし、とにかく影響ありそうなパラメータを評価値に足しこんでOptunaで調整させよう。
(3)評価値最大の操作の出力
評価値が一番高かった操作を出力し、フィードバックを得ます。フィードバックされた情報を使いファイナライズスコアを算出します。
ファイナライズスコアが今までで最大ならその状態を記録します。
(4)操作候補の枝刈り
フィードバックで納期遅れが発生してたら候補操作から無駄そうなものを削除します。今の稼働時間で納期遅れるのだったら、稼働時間をもっと減らすような操作は無駄だろうという観点です。
(5)終了判定
計画プログラムとのやりとりの回数が残り3回以上なら(2)に戻り繰り返します。もし操作候補リストが空なら手順2をはじめから行います。
計画プログラムとのやりとりの回数が残り2回なら手順3に進みます。
手順3：ファイナライズして出力
まず、今までのファイナライズスコア最大の状態を（ファイナライズ後の状態で）出力します。これで納期遅れなしのフィードバックが帰ってきたら、もう一度同じものを出力して終了です。
まれに納期遅れありがフィードバックされます。なぜ納期遅れが発生するかというと、作業負荷率が小数点3位までで切り捨てられているため、作業負荷率0%でも実際には作業を行っているためです。
この納期遅れを解消するために次の対策を入れました。
- 納期遅れのあった設備とそれより番号の大きい設備すべてについて、その設備の最終作業週の次の週の平日に稼働パターン2（午前中だけ働く）を設定して出力。*3
これで納期遅れが起こらない気がしていますが確証はないです（ジャッジプログラムを理解できてないの）
この納期遅れ対策のために、前の手順で計画プログラムとのやりとりの回数を2回残しておく必要がありました。
作ったビジュアライザ
ファイナライズ後の状態を表示したり、設備単位の合計コスト/稼働時間を表示できたのが便利でした。
感想
実行時間が短いのと乱数もないので、optunaで最適なパラメータがきれいに見つかるのが気持ちよかったです。
横軸：パラメータ、縦軸：スコアのグラフ↑
作業負荷率0%で実際には作業しているケースの対策に苦労しました。発生率自体は低いものの発生したときは無視できないぐらいのスコア減点があるので対応せざるを得ませんでした。正しく対応するにはジャッジコードをちゃんと理解する必要がありそうだったのですが、それよりは別なとこに力入れたほうがいいでしょ、という絶妙なスコア設定でした。
問題文が長く複雑で、問題文だけ見て参加やめてる人がいそうで、ちょっともったいない気がしました（大部分は理解しなくてもよくて、理解してもあまり活用できない……）
参加記のネタにしようとコンテスト中に日記を書きましたが、細かく記載しすぎてまとめるのが大変でした。時系列に改善していった様子を記事にしたかったのですが、難しすぎて断念しました。記録の仕方も工夫しないといけないかなあ。
時系列やったこと
1日目
- サンプルコード実行
- 公式ビジュアライザを動かす
- ビジュアライザ自作
- 設備稼働率100%超えてるので質問出す
- 遅れ作業の個数が公式ビジュアライザと合わない
2日目
- ジャッジの変更を反映
- 全設備全週同じ稼働パターンで埋めるのを全パターン試す実装
- 稼働パターンを1段階ずつ下げる貪欲を実装
- ファイナライズ実装
3日目
- 稼働パターンを平日/祝日を組み合わせ81パターンで扱う実装をした
→1段階ずつ減らす操作だと局所解にはまる - 1設備1週だけ変更する操作の実装
- 提出：154098562126点（7位）
- 1設備1週の休日だけ変更する操作の実装
4日目
- パラメータ大量に用意してoptunaで殴ると良さそう
- 稼働パターン81パターンから時間ソートして無駄なの省くとすごいパターン減る
- C=8のケースが見当たらない→テストケース生成プログラム見たら作られないみたい
- エクセルでパラメータとスコア表作った
- スコア予測処理実装
- 作業時間をもとにした納期遅れ判定実装
5日目
- 変更するときの段階数を4/2/1みたいにするといい感じ。二分探索みたいになるんだ。
- ファイナライズしても納期遅れ発生する。誤差で0%になってるということか。
納期遅れだった設備の最後に祝日の稼働パターン2を入れるようにして対策→それでも再発→平日の稼働パターン2を入れるようにした。 - 設備単位、ある週より前の週全部を変更する操作を追加→驚くほどスコア変わらない
6日目
- すぐ局所解に陥って山登れてなさそう
- 設備単位、ある週以降の稼働時間を減らす操作を追加→かなり良い
- 二分探索みたいな操作を実装
- 問い合わせ回数を余らせないように繰り返し処理実装
- 提出：159,754,557,566（3位）
- 稼働パターンの変更手順フェーズ「全周変更」「指定週以降変更」「1週変更」の3つを、全設備で変更がなかったら次のフェーズに移行していたのを、設備単位で以降するようにしたらスコア上がった。
7日目
- 「全周変更」「指定週以降変更」「1週変更」の3フェーズ順不同の同時進行にしたらスコア上がった
- またファイナライズで納期発生する。ムキー！納期遅れのあった設備より後の設備全部に稼働稼働パターン2を入れて対応。
- スコアだけでなく評価値を使って操作を決めるようにした
- optuna回すために新しく買ったPCを開封した。めちゃ早い。
- ジャッジコードを高速化した
8日目
- optunaの結果を反映
- 提出：161,234,108,954（1位）
- 評価値追加
- optunaでパラメータ調整
- コードを少し変えて上がるなら採用を繰り返す
- 稼働パターン候補を間引きするとなぜかスコア上がるので採用
- 最終提出：161,413,266,352 点
