問題

atcoder.jp

方針

各設備の稼働パターンを以下の流れで調整しました。

二分探索で基本となる稼働パターンを決める
調整案をいくつか作成しその中からランダムで選択した案を採用する
終盤に稼働が必要なさそうな設備の稼働を止める

二分探索による稼働パターンの探索

稼働パターンを下限値 4 上限値 9で二分探索を行います。この探索で必要な試行回数は最低 2回、最高でも 3回となります。

変更する時はすべての週に対して操作を行います。

下限値を 4 にしているのは、今回は山登り的にスケジュールを改善しているので序盤からキツめに調整してしまうと後の調整の自由度がなくなってしまうのである程度余裕をもたせるようにしているためです。

調整案の作成

基本となる稼働パターンを決めた後は調整案を作成していきます。調整案はいくつかのパターンがありそれに基づいて作成されます。

調整案1

今回の問題では各注文に「納期」が存在するため、合計の稼働時間が同じでも「日程の前半に多く稼働させる」 or 「日程の後半に多く稼働させる」では前者の変更のほうが依頼の達成率が高くなります。

稼働時間が単調減少するパターン

稼働時間が単調増加するパターン

そのため、調整案 1 では稼働スケジュールの 1週目のパターンを「基本パターン」として「2 ~ X - 1」の中からランダムな値を選択し「選択した値 ~ X週」までの稼働パターンを基本パターンからいくつか下げた値に変更します。（この下げ幅もランダムに選択されます）

この変更は「平日のみ適用」「休日のみ適用」「両方に適用」の 3つからランダムに選択され実行されます。

調整案2

調整案 1 が採用され続けると 2週目以降の稼働パターンが完全に下がりきった状態になるので、それを解消するために 1週目の稼働パターンを下げます。

スケジュール変更の流れ

各設備では「二分探索による基本稼働パターンの探索」→「細かい調整」を行っていきます。まず変更を行う設備をランダムに選択し、基本稼働パターンの探索が完了していない場合はその続きを、完了している場合は調整案を作成します。この処理を何回か行いその中で一番コストが削減されるものを採用し、その後は変更後のスケジュールを計画プログラムに渡して評価を受け取ります。

変更が成功したか失敗したかによってその後の処理が変わります。

成功時

成功したスケジュールを採用し、変更を行った設備の「最低設備コスト」の値を 0 にリセットします。ここでの「最低設備コスト」とは「その設備における最低限必要なコスト」を指し、この値を下回る変更を行わないようにします。（このコストを下回ると必ず依頼に失敗するというしきい値）

失敗時

変更を行った設備のスケジュールを元に戻し、「最低設備コスト」の値を更新します。

最低設備のコストの計算は (a * updated_cost + b * cur_cost) / (a + b) で行っており、a: 4, b: 1 を基本として失敗した注文の数が多い場合は a: 2, b: 1 に設定して計算を行いました。（例 - 現在のコストが 100、更新後のコストが 0の場合 (4 * 0 + 1 * 100) / 5 = 20 となる

序盤はまとめてスケジュールを変更する

序盤はほとんどのクエリが成功するので複数まとめてスケジュールの変更を行いました。まとめる件数は最初 M件からはじめて成功失敗に関わらず半分にしていきます。（例: M が 8 の場合は 1ターン目: 8件まとめて変更、 2ターン目: 4件まとめて変更, 3ターン目: 2件まとめて変更といった感じです）

終盤のスケジュール作成

終盤では今まで送ったスケジュールの中で一番スコアが良かったものをベースに稼働が必要なさそうな部分を「稼働させない」パターンに変更する作業を行いました。稼働が必要かどうかについてはクエリを送ったときの返り値の 負荷率 を調べてその値が 0 の部分を「稼働させない」に変更します。

↓

休日のみ稼働を停止させる

負荷率が 0 でない場合でも「休日」は停止できる可能性が残っています。というのも 1週間の構成は「day1 ~ day5 が平日で day6, day7 が休日」となっているので、画像のように day1 ~ day5 の間だけ稼働していて day6, day7 は何もしていないという可能性があるからです。

「負荷率 Y を下回った場合は休日の稼働を停止させる」という処理を行いますが、この Y の値については二分探索で求めました。今回は ok: 0, ng: 80 を初期値として設定しています。（例: 1回目は 40% が基準となる。2回目の値は失敗した場合は 20%、成功した場合は 60%）もし、最後のターンまで 1回も成功しなかった場合は Y = 0 にして処理を行います。

この処理は E = 50 のケースでは終盤の 2ターン、それ以外では終盤の 4ターンで行っています。

感想

問題文が複雑そうだから理解するのに時間かかるかなと思ったけど、やってみたら思ったよりやることが少なかった印象。テストケース生成のコードと調整プログラムのコードを調べようかと思ったけど 1週間コンテストだし気合が足りなかったので結局ふわふわした感じの理解で問題を解いていた。時間があれば TPE とか調べて参考にしていたかもしれない。

雑感

ジャッジプログラムの日本語が文字化けしていたので英語のコメントを読んでいた。

クエリの結果から得られる情報がほぼないのでクエリを工夫して注文の内訳を調べるとかそういう感じの問題ではなかった。（ブラックボックスなものをいい感じにパラメータ調整する問題なのでそれはそう）

工程自体は複数に分けられていたけど注文が特定の設備に依存している感じだったので工程がM個あるのとあまり変わらない感じがした。（工程 a を行う設備 b が今使えないから代わりに工程 a を行う設備 c を使おうみたいな処理があると思っていた - ちゃんと把握しているわけではないので違う可能性もある）

最終日付近でジャッジプログラムに最適化オプションつけるのを忘れていたことに気づいて直したら 4倍ぐらい速くなって感動した。C++ 使っていたから気づけたけどそうでない人はハマってそう。

インタラクティブ問題ではクエリの結果に「今このぐらい時間を使用していますよ」というのを含めたほうが良いと思っている。

後いろいろ細かい調整は入っているけどスコアにクリティカルに影響あったのは書いたつもり。