MC Digital プログラミングコンテスト2023 参加記

問題

atcoder.jp

方針

• それぞれの空間からランダムに座標をいくつか選ぶ
• シルエットAの回転方向は 0で固定、シルエットBの回転方向をすべて試して一番評価が良くなるブロックを選ぶ
• ブロック設置後に 1マス延長を試してスコアが良くなるなら採用する処理をスコアが改善できなくなるまで繰り返す
• 「設置」→「山登り」をシルエットが完成するまで繰り返す
• 途中置くところが無くなったらランダムなブロックを選んで全削除
• 完成したらリセットして最初からやり直し、時間制限いっぱいまで実行して一番良かったものを採用

パネルの重み付け

一番良い状態のブロックをどう評価するかについてですが、各パネルに値を付与してその値の合計値が高いものを良いブロックと評価しました。 パネルの評価については「その部分をカバーするのがどれだけ難しいか」を基準に値をつけます。

• パネルの周囲4 マスにパネルが少ないほどより高いスコアをつける
• そのパネルを埋めることができる空間の個数が少ないほど高いスコアをつける

周辺パネルが少ないと高スコア

周辺のパネルの枚数が同じでも別方向から見たときにその位置にブロックを置ける空間の数が異なれば難易度も変わるのでそれも評価に含めます。

具体的な評価値についてはケースごとに分けて optuna で調整しました。

ランダムな座標選択

スタート地点として座標をランダムに選択しますが、まだ未完了のパネル、ブロックの設置難易度が高いところほどスタート地点として選ばれやすくしています。

• 優先度高 : 両サイドともまだ未完成のパネル部分
• 優先度中 : 片方のサイドがまだ未完成のパネル
• 優先度低 : その他の部分。周辺の空白マスの多いものを選ぶ（ブロックの動きの自由度が高くなりそうなもの）

一番良いブロックの置き方を求める

座標を決めたら次に回転方向を決めます。回転の種類は全部で 24種類あって組み合わせとしては 24 * 24 = 576 通りありますが、片方は固定しても特に問題ないので片方は 0で固定して、もう片方の残りの 24通りをすべて試します。ブロックは再帰的に探索して伸ばせる部分が無くなるまでブロックを伸ばし続けます。途中で他のブロックにぶつかった場合、そのブロックを削除してもそのブロックの連結性が保たれる場合はそのブロックが無いものとして探索を続けます。

この処理をいくつかランダムに座標を選び直しながらその中で一番良かったものを採用します。

なるべく周辺パネルが少ないマスをカバーするようにブロックが生成されていると思います。

連結性の確認

「このブロックを消したときに連結性が保たれているかどうか」の確認は簡易的なものを使用しました。正確に行おうとすると「1個消す → 周辺マスを DFS して 2回以上探索が行われるかどうか」みたいな判定処理になると思うのですが、この処理がとても重いので消したいブロックとその周辺のマスを確認して消せるかどうかの判定を行いました。

周辺に同じ ID のブロックが 1個以下しかない場合

特に細かい確認は必要なく問題なく消せます

周辺に同じ ID のブロックが 2個以上ある場合

隣接ブロックが他のブロックで接続されているかどうかを確認します。具体的には隣接ブロックがある方向を足し合わせたマスに同じ ID のブロックがあるかどうかを確認します。

図の例だと消したブロックの周辺には「前方向」と「左方向」の 2箇所同じブロックが存在していますが、この場合「前方向 + 左方向」に同じ色のブロックが存在するかを確認し、存在している場合は連結性が保たれているとして削除を行います。

n個隣接ブロックが存在する場合、この条件を満たすブロック配置が n - 1 個あれば連結性は保たれているのでそれで判断を行いました。

正確性は犠牲にしているので例えば以下のような状態だと無理だと判断されてしまいます。

計算量の問題から隣接ブロックの数が 4以下のところだけをチェックしています。消したいブロックを中心とした 3 x 3 の空間でチェックを行う実装もやってみましたが処理が重くて諦めました。評価の段階では壊しながら進みますが実際に置くときは他のブロックがあるところでストップするようにしています。（後に行う山登りで実際に壊してみてスコアが改善するかどうかを確かめます）

山登りによる改善

1つのブロックの設置が完了したら、その都度山登りによる改善を行います。遷移としては「1つマスを選んで 1マス伸ばす」を行い。スコアが改善したら採用するという処理を行います。これを改善できるマスが無くなるまで繰り返します。

before - after

処理が非常に重いため最初は一番最後のみの実行を行っていましたが、ブロック設置毎に実行したところスコアが大きく改善したためこちらを採用しました。

時間制限いっぱい繰り返す

「ブロック設置」→「山登りで改善」を繰り返してシルエットの未完成部分がなくなったらそこで終了。一番良かったのもを採用して終了します。繰り返し実行の中で現状の最小スコアより高くなったら早めに終了したりと足切り処理も入れています。

感想

最初思いついた方針でそのまま走った結果になった。この手の少しの変化で局所解の脱出が難しそうなやつは毎回多スタートの貪欲を選択している気がする。最初はブロック設置 + ランダム削除だったけど最初から作り直したほうがスコアが良くなったのでそっちになった。nika さんに抜かれたあたりから「あっこれ方針違うんだな」と思ってたけど残り 3日とかの段階だったので大きな変更もなくそのまま終了した。終盤に足が止まってしまうのは毎回の反省点。今回の問題みたいに 1位のスコアが圧倒的になるタイプの問題好き。（大体トップスコアの 9割が 20位のイメージだけど今回は 20位でも 6割程度しか取れていない）

競技プログラミング獲得賞金（2022年）

一覧

コンテスト名	順位	金額	備考
Hitachi Hokudai Lab. & Hokkaido University Contest 2021 B問題	2位	100,000円
MC Digital プログラミングコンテスト2022	4位	30,000円	賞金対象外者が 1名いたので繰り上げ
第8回 Asprova プログラミングコンテスト	9位	10,000円
第9回 Asprova プログラミングコンテスト	2位	80,000円
TCO22 Regional Events Marathon 東アジア地区	3位	50$	コンテストというよりイベント的なやつ

合計 220,000円 + 50$

MM143 TreeMaker 参加記

問題

www.topcoder.com

戦略

• 完成図の作成を行う
  • 色の配置を決める
  • タイルの配置を決める
    • 初期解の作成
    • 枝の追加・削除による木の変形
• 完成図に対してもとのタイルとのどのタイルが対応するのかを割り当てる
• 盤面を操作してタイルを揃える
  • y軸を揃える
  • x軸を揃える

完成図の作成

ただ闇雲に盤面をスライドさせても最小全域木の完成は難しいので、先に完成図を作成するところから始めました。

色の配置を決める

色の配置については各色について領域の4隅 [0, 0], [N - 1, 0], [N - 1, N - 1], [0, N - 1] を起点としてそこから dy, dx の最大値が小さい順にセルを彩色していきました。（なるべく正方形になるような配色になります）

もう 1つのパターンとしてシンプルに順番通りに彩色していくパターンも用意います。

タイルの配置を決める

初期解法の作成

まずは最初にベースとなる最小全域木の作成を行います。幸いテスターに木の作成方法は書かれていたので今回はそれを利用しました。

最初に対象の色の領域に空のタイルを設置します。

その後、ランダムにタイルとランダムな方向を選択して、その方向にまだタイルが設置されていない場合は枝を伸ばします。

この処理を未完了の領域が無くなるまで繰り返します。

木が完成したら他の色に対しても同様の処理を行っていきます。

枝の追加・削除による変形

木の性質として「辺を 1本追加すると必ず閉路が出来る」というものがあります。そしてまたその閉路の中の 1本を辺を消すことで再度木になるので、この特徴を利用して木の変形処理を行っていきます。

辺を追加して閉路の検出を行う（計算量は N * N)

見つけた閉路の中から辺を 1つ削除する。

この処理を行うことで木を維持しつつ使用するタイルの種類を変更することが可能となります。今回はこの処理を繰り返しつつ元の盤面のタイルの種類の数との差分が小さくなるように変更を行いました。

タイルの割当を行う

完成した盤面に対して元の盤面のタイルをどの位置に割り当てるのかを決定します。AHC011 の時は最小費用流を用いて割当を行いましたが、今回は速度重視で貪欲に割当を行いました。割当の評価としてはこの後に「y軸を揃える」-> 「x軸を揃える」という作業を行うので y軸が等しいものが多くなるように評価を行うようにしています。

盤面を操作してタイルを揃える

盤面を揃えるパートについては「y軸を揃える」 -> 「x軸を揃える」の順番で行っていきます。

y軸を揃える

現在持っている余剰パネルを正しい y軸の方向に入れます。余剰パネルが完成版で使用しないパネルの場合はまだ完成していない y軸で適当な箇所に入れます。

x軸を揃える

x軸を揃えて行きますがその際に「余剰タイルを含めた行の連結成分が 1になるように盤面の操作」を行っていきます。

例として下記の画像を使用します。

まず、本来そのタイルがいるべき x座標に対して有向辺を張ります。現状では連結成分数は 3となります。

この数が 1になるように行を横にスライドさせたりタイルの形が一緒の場合は値のスワップ等を行います。

あとは元の場所にタイルを押し出すことで x軸を揃えることが出来るようになります。

ソート後

このように x軸をそろえつつ行を1つ上に押し上げることが出来ます。この作業を N 回繰り返すことで盤面を完成させます。

まとめ

AHC011 と似たような問題ではあり実際に完成図を作るところは完全に AHC011 の方針と一緒だったが、盤面を完成させるパートが完全に別物でそこをどうやって手数を短くするのかを考えるのは楽しかった。横軸を揃える -> 縦軸を揃える方法だと多くの手数を使ってしまうのでそこをなんとか改善したかったが最後まで何も出来なかった。（上位勢と近い考察はしていたがうまく動か無さそうだなと案を捨ててしまったのが良くなかった）

MM142 HelpTheElves 参加記

問題

www.topcoder.com

戦略

主に以下の 2つになります。

• 各エルフについてルールベースによる行動の選択
  • 経路についてはダイクストラ法を使用しての探索
• どの AI が使用されているかの検出 & メタ戦略

今回の問題では各AIの弱点を上手く攻める必要があったので、序盤の箱の配置でどの AI が使用されているかを検知し各AIに対して特化した戦略を使用しました。個人的な攻略難易度としては「AI3 > AI2 > AI1 > AI4 > AI5」の順となっています。

AI のタイプ推定

自分は C++ を使っていたので Java で書かれた AI のコードを C++ で書き直して、各 AI がどの位置に箱を置くのかをシミュレーションしてその一致率が高いものを採用しました。正直 AI のタイプについては入力で渡しても良かったと思います。（特に AI2 と AI3 の判別が難しかったので）

AI5 対策

今回のAIの中で一番攻略が容易となっています。AI5 の特徴としては以下の 2つになります。

• ターン毎に指定された座標に箱を置く
• プレゼントを守る行動は一切行わない

そのため「プレゼントに向かって移動、プレゼントを回収したら戻る」というコードを書くだけでもプレゼントの回収率 100% を達成することがほぼ可能です。（無理なパターンとしては プレゼントの数 > エルフの数 の時ぐらいです）

あとは全ての AI 攻略に共通する対策ですが、プレゼントの回収は画面外から遠いもの（中央付近）を優先するようにしています。これは終盤に出現したエルフが何も回収出来ずにゲームが終了してしまう可能性をなるべく排除するのと、後半になればなるほど中央の守りが堅くなり到達が困難になるため序盤のうちに回収したいからです。

余計なお金を使わせる

AI5 はプレゼントが全て回収されたあとも箱を設置してくれるので、最後の 1個のプレゼントに関しては回収したあとに画面外から出ず待機させ、他のエルフに箱を回収させるようにしています。そうすることでマネーを消費させてスコアアップを狙うことが出来ます。

この「あえてゲームを終了させずに箱を設置させることでマネーを消費する」という戦略も全ての AI 共通の戦略となっています。

AI4 対策

特徴としては「プレゼントが危なくなったらブロックを行う」プレゼント防衛型の AI となっています。そのため、単純に接近するだけでは箱でブロックされてプレゼントの回収が行なえません。そのためいくつか工夫が必要になります。

AI4 の弱点として以下の 3つがあります。

• プレゼントの周辺マス以外については特に警戒されない
• 箱かプレゼントを保持しているエルフは警戒されない
• プレゼントを回収しているエルフに対するブロックは行われない

そのため自分の戦略としては「箱 or プレゼントを持っているエルフを利用して警戒されずにプレゼントに近づく」というものを採用しました。

具体的には下記の画像のような プレゼントの周辺 4マスのいずれかを箱 or プレゼント持ちのエルフに待機させる 状態を維持するようにします。

この状態を維持することで安定してプレゼントの回収を行うことが出来ます。

具体的には プレゼントに近づいても箱でブロックされる ということが無くなります。

近づくと箱でブロックされる。

箱でブロックするのをプレゼント持ちのエルフで回避して、位置を入れ替えることでプレゼントの回収を行う。

AI1 対策

特徴としては「プレゼントの集合を効率よく囲んでブロックする」エリア防衛型の AI となっています。各プレゼント毎にブロックを行うのではなくエリアに対してブロックを行うので箱を効率よく利用できマネーの消費を抑えることが出来ます。

MM131 においては一番優秀だった AI1 ですが 1つ弱点が存在しております。

• プレゼントを囲む経路上に箱が置けない場合は箱を置かない。

また、この経路を作成する際には木以外のマスについては同じコストで計算されているので画像のような箱で囲まれている状態と

経路の一部にエルフが入り込んでいる状態は経路のコストとしては同じになります。（エルフがいる位置に箱を置きたいが、エルフがいるので箱を置くことが出来ない。また、コストが一緒なので箱持ちエルフを回避した経路を作ることもない）

攻略としては以下の段階を踏みます

• 囲まれている部分の箱を回収する
• 箱を回収したエルフは「ゲート役」として他のエルフが囲いの中に入る手助けを行う

ゲート役について

ゲート役のエルフは他のエルフがエリア内に入る手助けを行います。具体的には近くにエルフが来たらマスを開けて通り過ぎたら元の位置に戻るという行動を行います。

この行動は相手の AI が箱を置きたい場所を常にエルフがいる状態にして箱を置くのを防ぎつつエリア内の出入りを自由に出来るというメリットがあります。

AI2, 3 対策

この 2つの AI が今回の攻略で一番難しかったタイプになります。

AI2, 3 は基本的な方針は一緒で「箱が置ける場所に置いてみて、一番プレゼントが回収しにくくなる場所に箱を置く」というものです、評価値の算出方法の点が異なります。

少ししか改善されない場合でもマネーがある限りどんどん箱を設置していくので、MM131 的にはあまり良くない解法でも今回の問題に関してはかなり攻略が難しい AI となりました。（箱の物量作戦で押し切られるのが一番つらい）

基本的な攻略は AI1 の時と一緒でゲート役のエルフを上手く使いながらエリア内に侵入しプレゼントを回収していきます。

閉じ込められるのを回避する

箱を回収する際に場所によっては閉じ込められて再度箱の回収が必要になってしまうので、それをなるべく避けるために相手の箱の設置場所を先読みしてなるべく閉じ込められないように行動するようにしています。

次のターンで再度閉じ込められてしまう。

相手の行動を先読みで閉じ込められないように行動。

これで大体 1% の改善です（AI は 5つあるので 0.2% の改善）

正直この 2つのタイプについては特に特化した戦略を思いつかなかったのであまりスコアは良くありませんでした。（複数のエルフを使って攻略する案はあるのですが、実装が複雑になりそうなので止めました）

まとめ

いつもの問題だとジャッジ内部の AI のコードを読んでそれに対応するコードを実装するみたいな感じだと思うので、AI のタイプが複数あってそれぞれに対応する必要があったのは斬新だなと思いました。 ただ高いスコアを得るためにはジャッジコード + AIのコードを読む必要があり、AI のコードが Java で書かれていたため C++ で再実装する必要があったのでいつもよりコード量が多くなってしまったのは少し面倒だなと感じました。（AI のタイプを推定するためにも移植は必要）

ルールベースのコードを書くと毎回最後の方で条件が複雑になってしまって、最後の方はデバッグに時間が取られてしまったのは戦い方としてはあまり良くなかったなと思った。まだ実装したい案はいくつかあったけどバグの埋め込みの可能性のほうが高いので結局手が出せなかったのは残念。

TCO22 Final 参加記

問題

今年のお題はパズルゲームでした。（インタラクティブ問題）

入力として N * N のサイズのグリッドと 3 * 3 の固定サイズの手持ちパネルの情報が与えられ、1ターン毎以下の操作を行うことが出来ます。

• 手持ちのパネルを 1枚選択しフィールド上のフルーツと重ならないように配置する（パネルの回転は出来ない）
• 手持ちのパネルを 1枚選択し破棄する

また、行動後はパネルが新たに 1枚手持ちに追加されます。（追加されるパネルの内容はランダム）

配置後にフィールドをチェックして横か縦にフルーツが 1列並ぶと消えます。ラインを消した場合はスコアが与えられ、その得点は各ライン毎に 消したラインの数 * 消したラインに含まれるフルーツの最頻出値 ** 2 で計算されます。

例えば以下の画像ではスコアはこのように計算されます。

消したラインの数 : 1

ラインのフルーツの最頻出値 : 4

1 * 4 * 4 = 16点

また、次の画像では以下のようになります。

消したラインの数 : 2

縦のラインのフルーツの最頻出値 : 6

2 * 6 * 6 = 72点

横のラインのフルーツの最頻出値 : 6

2 * 6 * 6 = 72点

合計 144 点。

以下は実際に動作している様子です。

この操作を 1000ターン繰り返しなるべく多くのスコアを獲得することが目的となります。

可変なパラメータとしては以下の通りになります。

• フルーツの種類 : C (1 - 5)
• 手持ちのパネルの枚数 : T (1 - 5)
• グリッドサイズ : N (6 - 20)

方針

ビームサーチによる探索を行いました。ただ、探索の深さは手持ちのパネル枚数の T の値を上限にしていたので T が 1のケースでは実質貪欲法になっています。

操作としては以下の 2つです。

• 任意のパネルを 1枚選択し、任意の場所に配置する
• 任意のパネルを 1枚選択し、破棄する

多くのスコアを獲得するには「多くのラインを同時に消す + なるべく同種類のフルーツでラインを作る」ことが必要でしたので、評価関数として以下の要素を主に評価しました。

• ライン毎の フルーツの最頻出値
• ライン毎の フルーツの最頻出値 / ラインに配置されているフルーツの数 (ラインの何割を同じフルーツで占めているのかをチェック)
• 連続した空白地帯の数 (独立した空白地帯が多いとパネルが置きにくくなるため）
• 単発消しに対するペナルティ

ライン毎のフルーツの最頻出値

最頻出値は 2乗でスコアに影響しているのでなるべくこの値を大きくなるように評価を行いました。

ラインごとのフルーツの割合

同じ最頻出値でも N の値が 15 だとして 5 / 10 と 5 / 6 では後者のほうが同じフルーツが配置されている割合が高く、より得点が伸びる可能性があるので、割合を計算して評価に加えました。

連続した空白地帯の数

今回の問題では、なるべくパネルを破棄するような自体を起こしたくないため パネルを配置しやすい状態 というのを維持したいです。そのため連続した空白地帯の数を調べてその数が少ない状態の盤面を評価するようにしました。

空白地帯が連続しており、色々なパネルが置きやすい状態。

空白地帯がまばらでパネルが起きにくい状態になっているため良くない。

盤面全体を評価するこの処理はちょっと重かったので T = 1 のケースでしか利用していません。

代わりに、他のケースではライン毎の連続した空白地帯の数を評価しました。

下の画像のほうが他のパネルが置きやすいため良い状態と評価しています。

単発消しに対するペナルティ

なるべく同時消しを行ったほうがスコアが高くなるため単発消しに対してペナルティを与えました。ただ、盤面が埋まってくると単発消しを行って盤面整理を行う必要があるので空白率を調べてその割合が 10% を切ったらペナルティを与えないようにしています。

まとめ

シンプルに 24h でどこまで評価関数の精度を上げることが出来るのかの勝負でしたが上位勢のスコアに追いつくことが出来なかった。provisional のスコアの解析を見た感じ C = 1 のケースでは勝っていて、C の値が大きくなるにつれてスコア差をつけられていたので同一のフルーツを集めて消す処理があまり上手くいってなかったのかなと思われる。去年よりは戦えたがまだまだ実力が足りないと感じた。今年は寝ようと思っていたが、なんだかんだ順位が気になって結局ずっと起きていた。（それでも途中イスの上で 1-2h 寝た）

総括

今年の TCO はオンサイト（ボストン）で開催予定だったが、オンサイト参加者が少ないのでオンライン開催となりました。パスポートの取得とESTAの申請は終わっていたけど無駄になってしまった。それはそれとして、去年の初参加から絶対に改善しようと思っていたのが以下の 2つ

• 作業マシンの変更
• 与えられた EC2 環境を利用する

作業マシンの変更

去年は外付けの web カメラが無かったので、メインとは別のノートPC のほうで作業を行っていたのだが「全画面共有」にかなりマシンパワーを取られてローカルでテストを回すのが遅くなってしまったので、今年は外付けの web カメラを購入してメインのほうのマシンで作業できるようにした。

EC2 環境を利用する

去年は競技が終わったあとに EC2 環境に関するメールが届いていたことに気づき「これを利用できなかったのはかなりもったいない」と思ったので今年は利用することにした。今年は c5.9xlarge を与えられていたので手元のマシンよりかなりスペックが高くて便利だった。

スペックが高いとローカルでテストを回すスピードが格段に速くなる。元々テスト自体はマルチプロセスで並列処理出来るようにしているので並列数を 3 -> 30 にパラメータ変更するだけでテストのスピードが 10倍になった。

あとは事前に安いインスタンを使って EC2 上での環境構築の手順を確認して本番のときに手間取らないようにした。

試合の流れ

「問題を読む」-> 「ビームサーチ系の問題だな」→「それっぽい評価関数を書く」 (ここまでで大体 6h ぐらい）

「暫定 2位！ ただ、全員提出していないので（仮）だな」

評価関数をどんどん変更する（ビジュアライザを見て色々調査しながら 6h ぐらい）

「暫定 1位！ｷﾀｰ」

この後 6h ぐらい何も思いつかず順位が 8位ぐらいまで落ちる。

「タイルを破棄する評価が割と高かったので、ギリギリまでタイルを破棄しないように評価値を調整したらスコアがかなり上がった」

けどまだ上位には全然届かない。そのまま試合終了。

システムテストで最終的に 2人に抜かれて 5位で今年の TCO は終了しました。 provisional テストの解析結果から 4位には確実に落ちることはわかっていたけど、5位まで落ちてしまった。

感想

去年 8位で今年 5位だったので当初の目標「去年より高い順位を取る」は達成出来てよかった。来年もし参加出来たら 4位以上を狙いたい。2度海外オンサイトの機会があってコロナで全部フイになってしまっているのは少しもったいない感じがする (HTTF もそうだけど）。（飛行機代とか調べたら 30万とかしたので海外行けるだけでもお得感ある）

MM141 TrafficController 参加記

問題

www.topcoder.com

方針

• 毎ターンごとに5ターン先までの信号機の方向を焼きなましで求める

焼きなましで信号機の方向を決める

• 遷移としては任意のターン、任意の信号機をランダムに 1箇所選択して変える
• 実際にシミュレーションを行い評価を行う
  • 前進 +1pt
  • 停止 -1pt
  • スポーン地点での停止 -2pt
  • グリッドロックが発生しうる箇所での停止 -5pt

グリッドロックの回避

グリッドロックは下の画像のように渋滞が連続すると全く前進できなくなる状態のことを指す。

これを回避するために閉路を検出して、閉路の角に対して停止した場合のペナルティを大きくした。（赤色の部分で停止するとペナルティが大）

ただこれだけだと不十分なので他にもっと良い回避方法があったかもしれない。（1方向を完全に止めるとかもやってみたけど回避率が上がっても全体のスコアが下がってしまったのでバランスが難しい）

感想

最後までグリッドロックを効率的に回避する方法がわからなかった。車両にそれぞれポイントが付与されていたが結局どれだけ車両を捌けるかが大事なのであまりスコアに影響なかったように思える（終盤で緊急車両を優先するみたいなことはあるとは思うけど）

最近はわからない問題が多くて何もわからない。

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

問題

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++ 使っていたから気づけたけどそうでない人はハマってそう。

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

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