参加記～第9回 Asprova プログラミングコンテスト～

1．はじめに

本記事では第9回 Asprova プログラミングコンテストのmy解法をまとめています。

考察ノートを兼ねているので、あまり解説っぽい記事にはならない気がします。

2．問題概要（超ざっくり）

•  M個の設備があるよ
• X週稼働させるからそのスケジューリングをしてね
• 長く稼働させるほどコストがかかるよ
• 各設備ごとの稼働パターンはなるべく毎平日（毎休日）一緒であってほしいよ（でもC回までだったら変えてもOK）
• 設備の計画が出力されたらこっちでN個のタスクを与えてその計画を評価するよ
• ちなみにタスクの情報は個数含めて一切与えてあげないよ
• 「一つでもタスクを完了できない」or「稼働パターンの切り替えがC回を超えた」場合は0点ね
• そうじゃない場合、スコアは設備の稼働コストのみに依存するよ（どれだけ早くタスクを終わらせたかは関係ない）
• 出力→評価をE回繰り返して一番良かったスコアが君の得点だよ

3．1日目・2日目

まず、問題文を理解することに難儀。この記事を書いている時点でも（2日目終わり）、気持ちを100％理解できているとは言えないです…。

次に、ビジュアライザを動かすことに難儀。検索しながらよくわからないままぽちぽちしてたら、これまで競プロをしていた環境がぶっ壊れました…。clarを投げると丁寧な回答をいただけて、無事動かすことに成功しました。感謝の気持ちでいっぱいです。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

1日目・2日目の解法のベースは、スコアのフィードバックを利用した山登り法です。

初期解は「全部9」、遷移は「ランダムに設備を1つ選び稼働時間をランダムに短くする」としました。

130Bを超えたあたりで壁を感じ始め、いろいろ工夫はしましたが140Bに乗らず...。

焼き鈍しにすることも考えましたが、300回しか回せないのは致命的なので断念。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

この時点で1位が155B。今の山登りだとどう改善しても150Bを超える未来が見えないので、解法を一新することを決断します。

同時に、いろいろと問題を整理し直す意味も込めて、この記事を書き始めることも決めました。

4．3日目・4日目・5日目

思ったことが実装できていなくて、それを直すと140Bに乗りました。

とは言え壁は感じているので、1から解法を考え直します。

この問題の難しいポイント

作成した計画の評価をこちら側で出来ないのが辛いです。

評価を得られるのは最大でも300回なので、焼き鈍しをしようにもそのままだと試行回数が少なすぎてスコアが伸びません。

打開策は？

作成した計画の完璧な評価はできませんが、スコアは稼働コストのみに依存するので、全く予測不能というわけではありません。

より具体的に言えば、「その計画ですべてのタスクを完了できるかがわからない」のであって、「完了できると仮定した場合のスコアがいくつか」という計算は可能です。

つまり？

得られたフィードバックをもとに、「計画は少なくともこの制約を満たしていないといけない」というリストを作れないだろうか？

それができれば、その制約の範疇で焼けそうじゃない？

制約をどのように設けるのか

事実として、以下の二つのことが言えます。

少なくともこの二つは、制約として加えてもスコアが悪くなることはないはずです。

とりあえずこれだけを使って実装をしてみます。

実装

まずは山登りを書いてみます。乱択にしました。

下の画像を参考にしてください。（山登りの部分は乱択に置き換えてください）

最初にいくつかの解を提出するのは、何も制約がない状態で山登り乱択をするのはうまみが少なそうと考えたからです。

OKな計画のリストでは両方のリストで（実装の簡単のため）、計画そのものの他に「スコア」と「稼働パターンの切り替え回数」も記録しておきます。

結果

130Bくらいでした。最初に提出する解の個数は10個にしています。

考察

山登りから乱択に変更したのは、少ない探索回数の中で多様性を確保したいと思ったからです。

制約はかなり緩めのつもりでしたが、意外とスコア伸びたなという感想。

下は0000.txtの出力の様子（の一部）ですが、かなり0が多いことがわかります。

これは、今使っている制約が弱いので妥当な感じですね。

5．6日目

130Bが出たときは、OKの計画を変化させる際に、それぞれの設備について50％の確率で稼働パターンを変更するようにしていました。

これを0.5％まで下げるとスコアが145Bに乗りました。

うーーなぜ？

0000.txtの出力の様子を見てみるといい感じにスコアが更新されていることがわかります。

OKの計画から選んで変化させているのは、近傍をとってよりいい解を見つけられたらいいな、という気持ちだったのですが、設備の計画を複数個変化させてしまうと状態が離れすぎてしまうのかな？（0.5％の確率での変化であれば、複数個変化することはほぼなさそう）

試しに、1つの設備の計画だけを変化させるように書き直してみます。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

上の考察は正しそうです。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

0002.txtの出力を見ていたら、前半にベストスコアが出て、後半はそれが全く更新されていないことに気が付きました。

毎回出力するたびに記録する計画の個数が増えるので、制約のチェックに計算がかかり、乱択の試行回数が減っていそうです。

あんまり良くない解が増えることで、よい解を得にくくなっているという線もあるかな？

best_scoreを更新する可能性がない解は、可能な限り出力しないようにすると、質の悪い解が減って嬉しい？それとも多様性が減って悲しい？

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

乱択の試行回数は増えたけど、スコアはそんなに伸びなかったね。

0002.txtのスコアは3.7Bくらいでもともとかなり高かったし、ここに執着する意味はあんまりないのかな。
1位が160B（平均3.2B）とかなので、3.0Bに届いていないケースを重点的に見ていくべきかも。

E=100,300のケースを見ても、かなり早い段階でスコアが収束してるっぽいので、スコアはEの値よりもタスクの値とcostの値に大きく依存してそう。だとすると取れるところで取るのが正解なのかな～わかんない…

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

今まで稼働パターンの切り替えを許容していなかったので、それを許容するような遷移を足します。

足したら150Bに乗りました！！！！！

ただ、この遷移を足したせいで、後半の乱択の試行回数が一桁になっていて辛そう。

OKの計画のリストの個数を制限した方が良いのかも？多様性が犠牲になるのでスコアにつながるかは怪しい？

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

20個までしかOKの計画のリストに入れないようにしましたが、あんまり変わらないですね。NGの計画のリストのサイズがボトルネックになるだけでした。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

考えてみたいこと

• NGの計画のリストをどうにかして軽くすることができないか
• 乱択をいい感じに山登りに変えたらスコア上がったりする？
• フィードバック、スコアの値以外全然活用してないけど？

6．最終日

後半に行くにつれて最高スコアの更新頻度が著しく下がることが気になっています。

これまで均等に乱択の時間を割り振っていたけど、出力を何回か無駄打ちして、一回の乱択にかける時間を伸ばしたほうが良い？

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

あんまり変わんない…

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

ちょっと早いですが、調整して撤退です…辛かった…

7．コンテスト後の反省

（他の方の解法を見て追記する予定）