TCO22 Final に進出しました

TCO22 Final に進出

公式の順位表が更新されて Stage 4 のポイント集計に自分がカウントされていなかったので、去年に引き続き今年も TCO Final に出れるっぽいです（やったー）、去年は 4 -> 2 -> 4 の 200pt での突破でしたが、今年は 3 -> 7 -> 4 の 175pt での突破になりました。

TCO22 - Marathon

4位 とは 5pt 差でギリギリの戦いでした。

MM132

1, 2位とかなり離されたので結果としては残念だったがポイント的には 75pt 取れてラッキーだった回。3回のうち 1回でも高順位を取れると Final がぐっと近づくので本当によかった。

MM133

苦手な推定系の問題。当時流行っていた wordle を題材にした問題で、方針が全くわからず右往左往してたがなんとか 7位で耐えることが出来た。

MM134

比較的得意なマルチエージェント回。 Daiver19 さんより順位を上回らないといけない状況だったので個人的には絶望していたがなんとか勝てた（勝率 1割ぐらいだったので）

感想

方針を 2回外して突破できたので本当にラッキーという感じ。去年は 8位という下馬評通りな感じの順位で終わったので今度はそれより上の順位を目指したい。

AHC011 Sliding Tree Puzzle 参加記

問題

atcoder.jp

方針

主に 3つのパートで構成されています

• 与えられたパネルから木を構築する
• 構築した盤面の各パネルに対して数字を割り振る
• (N * N - 1) puzzle を解く

木の構築

木の構築は盤面を焼き鈍して作成を行いました。木の条件が厳しそうなイメージだったので「パネルの交換だけで出来るのか？」と疑問だったのですが実装してみたら意外と速く構築出来て驚きました。

近傍としては「2つのランダムなパネルを選択して入れ替える」の 1つでしたが選択時に色々と制限をかけています。

同じ種別のパネルを選択しない

同じ種類のパネルを入れ替えても状況は変わらないのでそれは行わないようにします

確実に悪い配置とわかる場合は除外する

「確実に悪い配置」というのは「そこにパネルを置くと絶対に木が完成しない」状態を指します。

図のように画面端に向かって枝が伸びているようなタイルが存在する場合は絶対に木が完成しないので、このような配置にならないように選択を行っています

どちらかは必ず接続状態を維持するようにする

タイルを交換する際にどちらのパネルも接続状態が途切れてしまう場合は交換を行いません。

例えば緑のマルで囲まれた部分を交換すると両方のパネルとも周辺のパネルと接続状態が途切れてしまいます。このような場合は交換を行わず再度タイルの選択をやり直します。

評価値

盤面状態の評価は「連結成分の個数 + 元の盤面からどれだけ近いか」で計算を行いました。

連結成分の計算は盤面全体を DFS で探索して計算を行っています。

元の盤面状態からどれだけ近いか

今の位置から元のパネルの種類の最短距離を計算してその合計値が少ない状態を良しとしています。

評価値については事前に計算しておきます。図は評価値の事前計算の一例です

種別 9 のタイルについて評価を行います

各マスについて種類 9 のパネルとどれだけ離れているのかを計算し dy * dy + dx * dx の最小値をテーブルに保存しておきます。

盤面評価の際はすべてのマスについてこの値を合計したものを利用しています。（この値が大きいほど元の盤面から乖離している ≒ 元に戻す手数が多いと考えられます）

（コンテストの途中、元の位置の距離 (dy * dy + dx * dx) をコストにしてみましたが、特にスコアに変化がなくただ試行回数が減っただけなのでこの評価値をそのまま採用しています）

焼きなましの打ち切り

盤面構築の際にどんなに試行回数を重ねても連結成分が減らない局所解に陥ることが多々あったので、 10万回スワップを行って 1回もスコアの更新が発生しなかった場合は処理を打ち切りました。

破壊的な近傍を用意して局所解からの脱出を行うよりも再実行のほうがコスパが良かったのでそうしています。

複数繰り返して色々な盤面を得る

1回の焼きなまし処理はだいたい 0.1 sec で終わって、盤面が得られる確率が大体 50% ぐらいだったのでこの処理を設定した時間 (今回は 1.7 sec) が来るまでに複数回実行して、様々な盤面を取得します。

構築した盤面の各パネルに対して数字を割り振る

完成した盤面に対して数字を割り振っていきます。割り振りには最小費用流を使用し、辺のコストには元の盤面からの距離 dy * dy + dx * dx と 1 ~ N のランダムな値で計算しています。ランダムな値を追加しているのは距離だけの評価だと毎回同じ数字の割り振りになってしまい、もし出来上がったものがパズルとして達成不可能な場合に数字を振り直したいのでランダムな値を追加して別の割り振りパターンになるようにしています。

パズルの達成が可能な盤面でコストが一番低くなるものを最終的に解く盤面として採用します。

完成可能かどうかの判定は以下のサイトを参考にしました。

manabitimes.jp

外周に近いマスのコストを高くする

n-puzzle は真ん中を先に揃えても後で壊される可能性が高く、基本的には端から揃えていきたいのでコストを計算するときに端のほうのコストが高くなるように設定しました。

配置コスト 5 + 9 = 14

配置コスト 4 + 10 = 14

画像では両方とも同じコストになるので距離のみの評価だとどちらを選んでも良いのですが、実際にはこの距離コストに係数を掛けたものを利用しています。

係数の値は端に近いほど高くなるように設定しています。（実装的には max(y, N - y + 1) みたいな感じです) この係数を使った場合は以下のような結果になります。

配置コスト(new) (4 * 5) + (6 * 9) = 74

配置コスト(new) (6 * 4) + (4 * 10) = 64

結果として、端のタイルはなるべく短い手数で済むような配置になります。（スコアとしては 2 ~ 3000 点ぐらいの向上）

(N * N - 1) puzzle を解く

盤面構築が終わったら後はパズルを解くフェーズになります。今回はビームサーチを利用しました。序盤は高速化が足りてなくて N が大きいケースでは外堀を埋めるルールベースを書いていましたが明らかに手数が多くて悪手だと感じていたので最低限のビーム幅が確保できる状態まで高速化しました。

評価関数

盤面の評価としては主に元の盤面からの距離から計算されるコストと Linear Conflict を少し改造したものを使用しました。（あと端が揃っているかどうか）

距離による評価

元の位置との縦軸の距離の差分 (dy) 横軸の距離の差分 (dx) を調べて、 dy * dy + dx * dx をコストとして計算します。 dy + dx のマンハッタンディスタンス (MD) の場合だと同じ評価値で揃える難易度が全く異なるものが発生しそうだったので2乗の方を採用しています。

特定のパネルを任意の位置に移動させたい場合に「同じ方向に連続で移動する」という動作がかなり手数を使ってしまうので、それを避けるようになるべく「縦の差分」と「横の差分」の差が少ないほうがコストが低くなるように設定しています。

端を揃えた状態の評価

n-puzzle では端が完成するとそれ以降は端を操作する必要がなくなるので、端が揃った場合はボーナス得点を与えています。

ただ、画像のように一部の端だけが完成し続けると最終的に端を崩さないと完成しない状況になりうるのでこのボーナスは「画面端から距離 Xの場合に有効とする」 といった感じで変数を使って制限を加えていました。（変数の値としては盤面のサイズの半分を超えないように設定しています）

隣接マスの関係性の評価

盤面全体をみて評価出来たほうがより精密に評価を出来るようになるとは思いますが、今回は高速化の都合上 1回の移動で変動したタイルの隣接マスだけを見て評価を行いました。

Linear Conflict

Linear Conflict についてはこちらのページを参考にしました。

michael.kim

隣接マスをみて完成図の同じ行 or 列に所属していて番号が逆転していた場合はペナルティを与えています。

特に、お互いが後 1手で完成する同士であった場合はより重いペナルティを与えています。（角でこれをやられるとかなりの手数を消費するので）

後はお気持ち程度の評価ですが、同じ列 or 行に所属していない場合でもゆるくペナルティを与えています。

本来であれば 9 は 7 の左側に来るべきなので減点する。

あと 1手同士が隣接している場合にボーナス

15 puzzle の攻略サイトを調べていると「後から車庫入れ」という形になっているとパズルがスムーズに解けるということだったので「残り 1手同士が隣接している」状態にボーナスを与えました。

studio-boiler.com

なので画像のような盤面状況が評価されることになります。

ボーナスとしては小さい値でしたが外すと 2 ~ 3000 下がったのでそれなりに有効だったみたいです。

zobrist hash による重複排除

同じ盤面を探索しないように zobrist hash による重複排除を行っています。重複排除の処理を外すと得点が 10000 下がったのでかなり効果があったみたいです。

Zobrist hashing - Wikipedia

感想

方針自体は maspy さんが初日に 38,307,047 を叩き出していたのでかなり早い段階で決まりました（n-puzzle を構築してそれを解く）あとは、手数を短くするために盤面構築の精度を上げるか n-puzzle solver の精度のどちらを上げるかでちょっと迷っていましたが最終的には solver の精度を上げたほうが良さそうだと思ったので評価関数を色々試してはみましたが 1位に追いつくことが出来ませんでした。

ビームサーチが題材の場合は評価関数を頑張らないとどうにもならないので（ビーム幅を 10倍にしても 1位のスコアに追いつけない）、15-puzzle の資料を色々読んでいましたが 4 * 4 というサイズの小ささに特化した手法が多くて Linear Conflict のような汎用的なものを見つけることが出来ませんでした。（本当はあったかもしれないけどそこは調査力が無かったということで）

ところで 6/23 2:00 から Marathon Match 137 が始まる予定なので興味がある方は是非参加してみてください。（世界大会に向けての予選なので恐らく強い人がたくさん参加する可能性が高いです）

リンクは参加方法についてのガイドラインになります。

www.topcoder.com

今回の問題では「焼きなまし」と「ビームサーチ」というマラソンマッチにおける基本的な探索手法を同時に扱えたのでとても面白かったです。個人的には AHC の時間制限を 10sec あたりまで伸ばしてくれたら時間管理をもっとゆるく行えて気持ちが楽になりそうだなと思っています。（自分の評価関数だとへたにビーム幅を下げると解が見つからない可能性があったのでこのあたりの調整がちょっと面倒でした）

MM136 HungryKnights 参加記

問題

www.topcoder.com

今回のスコア計算では同色の移動を連続で行うことで指数的にスコアが増える仕様となっていたので、出来るだけ長い同色消しの経路を作成する必要がありました。

方針

基本的な方針はビームサーチでの経路探索になります。

スタート地点の選択

長い経路を作りたいので、盤面にあるマスの色をカウントして一番多い色から消していきます。どのマスからスタートするかはランダムに決定しました。

移動先の決定

現在位置からの移動の候補は 8種類あり、移動先が同色かそうでないかで処理を分けます。

同色の場合

同色の場合は特に処理を行わずそのまま移動します。

違う色の場合

色が違う場合は別のマスから対象の色を持ってきて遷移するようにします。

移動先が別の色でこのままだと連鎖が途切れてしまう。

別のマスから同じ色の駒を持ってくる。

移動が可能になる。

この「別の駒を持ってくる処理」については連鎖中に行ってしまうと連鎖が途切れてしまうので、まとめて連鎖用の経路の前処理として実行します。

評価関数

処理後の盤面評価についてですが主に以下の点を重視しました。

• 残っているマスの個数
  • マスが残っているほど移動に自由が効いて連鎖を作りやすくなる
• 画面端に近いマスを消していると高得点
  • 画面端のマスは残りやすいため、なるべく残らないように評価を高くしておく
• 次に消す予定の色を残すようにする
  • 他の色でも大連鎖を組みたいのでなるべく残すようにする
  • その色だけではなくて周辺のマスも消さないようにする

その他

細かいスコアを取るためにやったこと、連鎖スコアに比べると些細なものなのであまり細かく詰めてはいない。

貪欲

連鎖も作れなくなったあとは残った駒を貪欲に消していきます。

挿入

最終的に使われない駒で、その周辺で処理を挿入できそうな箇所があれば変更を行います。

右上の青が最後まで使われなかった場合

「紫」→「黄色」と移動を行っているが、「青」→「黄色」 +「紫」→「青」 のほうがスコアが高くなる場合は「青」→「黄色」の処理を挿入する。

事前同色消し

残った駒の周辺に同じ色の駒がある場合は事前に同色消しを行っておきます。

先程と同様に青が残っている状態

事前に同じ色を使って消しておくことで 1点もらえる

感想

ビームサーチで評価関数勝負かと思ったら 1位は焼きなましだった。2色同時探索はちょっと実装しようかなと思ったけど、焼きなましはちょっと思いつかなかった。とりあえず実装してみてどのぐらいのスコアが出るかは確認したほうが良かったかもしれない。（初手のビームサーチで良いスコア取れたからそれに引きずられた感はある）

2割、3割スコアが離れてたら方針を疑ったかもしれないけど 1割以内で Psyho さんだったしなんかいい感じの評価関数があるのかなと思ってしまった。

Marathon Match 134 ShearTheSheep 参加記

問題

www.topcoder.com

戦略

• どの農家がどの羊を追いかけるかの割当を最小費用流問題として解く
• 対象への最良経路を探索
• 羊毛のバケツリレーを行う

農家と羊の割当

どの農家がどの羊を追いかけるのかを最小費用流問題として解きます。辺の張り方としては「農家」→「羊」となるようにし、フローの量は「農家の数」とします。

辺のコスト

S →「農家」は 0、「羊」→ T は 0、「農家」→「羊」についてはそれぞれコストを計算するための関数を使って定義を行います。また、各辺のキャパシティは 1 で定義します。

コスト計算では以下の要素を考慮します。

• 対象との距離
• 対象の羊毛の量
• 周辺の羊毛の量
• 納屋までの距離

対象との距離

対象までの距離をダイクストラ法で求めます。

距離が 4以下の「羊」については「壁」「木」と同様に通れないオブジェクトとして扱い、それ以上の距離にいる「羊」については距離に応じたペナルティを与えます。（ペナルティの係数は optuna で調整）、「農家」ついては交差したとしても羊毛を受け渡しが可能なので特にペナルティ無しで通過出来るようにしています。

羊毛の量

羊毛の量が MAX の時に成長のタイミングが来ると狩れるはずだったの毛の成長が行われないので実質スコアの減少となります。そのため、羊毛の量が MAX の状態の羊を優先的に狩るようにしました。

周辺の羊毛の量

保持できる羊毛の量 C が多い場合は連続で毛を狩るようにしておくと得点効率が良いので、対象の羊毛の量だけではなく周辺の羊毛の量も調べてそれも評価します。

納屋までの距離

ある程度羊毛を集めると納屋に戻って収める必要があるので、納屋までの距離も評価します。（この評価値はある程度羊毛を集めた農家だけに適用）

「農家」→「納屋」の辺を追加

ある一定量の羊毛を集めた農家に対しては「納屋」への辺の追加を行います。「納屋」→ T のコストは 0、 キャパシティは無限（農家の数より大きな値であれば何でも良いです）で定義し、「農家」→「納屋」のコストについてはダイクストラで計算した値に設定します。

対象への最良経路を探索

目的への経路をダイクストラ法で探索します。「羊」との距離を詰める場合は、羊側の行動によって距離が短くなる候補が多くなるように行動します。（基本的にはY軸とX軸の長い方を短くするような動きになります）

羊毛のバケツリレー

納屋の数が少ないケース等では羊毛を収めに来た農家が詰まってしまうので、詰まった状態でも羊毛を納屋に収めれるようにします。

農家の行動順を入れ替えて納屋までの羊毛の受け渡しを 1ターンで終了させるようにすることで詰まること無く羊毛を収めることが出来るようになります。意図的にリレーを行うというよりかは詰まった時にこの機能が無いと不便だよねという感じです。

感想

2次元グリッドベース + マルチエージェント系の問題。スコア計算が線形的なとの「これをやれば爆発的にスコアが伸びる」みたいなのも特に無かったので、基本的な実装は前半で終わってしまって、後半は地味なチューニング作業が多くなってしまった。焼鈍系の問題が減った代わりにオンライン系の問題が増えてきた印象がある。いい感じの評価値もといコスト計算を行う方法が全然わからないので、機械学習でその辺りを改善できるなら実装していきたい気持ちがある。

optuna 今までは Best parameters しか見てなかったけど、今回は Visualization 機能でパラメータとスコアの関係を俯瞰的に見れて便利だったので今後も機会があれば使っていきたい。（本音はチューニングじゃなくて方針で差がつく問題をやりたい）

Seed  1: 251
Seed  2: 6048
Seed  3: 4250
Seed  4: 403
Seed  5: 1179
Seed  6: 187
Seed  7: 1997
Seed  8: 639
Seed  9: 1406
Seed 10: 382

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

問題

atcoder.jp

方針

• 製造する製品の（形状、色、生産個数）をまとめて タスク という形にまとめる。
• タスク を行う順番を焼きなましで更新していく
• 順番が確定した後 生産個数 の部分を別の焼きなましで改善していく

タスクの作成

製品を 1個ずつ扱うと計算量が大きくなってしまうのと、基本的に切り替えのコストが大きいのである程度製品をまとめて生産するほうが良くなります。

今回は初期の生産個数を N[s][c] / K[s] と定義してタスクの生成を行いました。

焼きなましによる生産順番の改善

焼きなましによって生産の順番を改善していきます。遷移としては以下の 3つになります。

• 任意の 2つのタスクの順番の入れ替え (swap)
• 2-opt
• 任意の 1つのタスクの位置の入れ替え (insert)

スコア計算ですが1回のループで生産できる個数に制限が存在しているのと、前に設置したハンガーの再利用を考慮すると差分計算が出来ないため、基本的には再計算を行っています。 また、スコアを厳密に計算してしまうと必要な試行回数を稼げないためある程度簡易化したものを利用しました。（簡易版で試行回数 2M 程度)

簡易版では「再利用できるかどうか」の判定を簡略化しており、大まかに「前に設置した形状 s とどれだけ間隔が離れているか」を評価の基準としています。（間隔が H に近ければ近いほど評価しています。）

また、個数制限についても「直前に設置したタスクの生産個数との和が制限を超えているかどうか」だけで判定しており、この辺りの精度も落としています。

ただ、ベストスコアに関しては完全版のスコア関数を利用して比較を行います。

生産個数の焼きなまし

順番を確定させた後に、生産個数について別で焼きなましを行いました。一緒にまとめてやってしまうと非常に複雑化してしまって全然安定しなかったので「順番」→「個数」と別々で行っています。遷移としては「任意の製品を選び生産個数を変動させる」というものになります。

ここでのスコア関数は完全版を使用しています（制限時間は 0.2 sec 程度で試行回数が 20K 程度）。

感想

焼きなましの試行回数が全然稼げず終わってしまいました。簡易版を使用して誤魔化したのですがそれでもまだ足りなかったです。 「切り替えコストを少なくして、なるべくハンガーを再利用出来るようにする」と頭の中では理解していたのですが、結局それをどう評価していけばよいのかがわからず終わってしまいました。良い評価関数を作るにあたってデータ集めと解析を怠ってしまったのは個人的には反省です。

マラソンマッチにおいては「改善できなくなったら負け」なので、継続的にスコアを改善できるような仕組みを考えていきたいですね。

AHC008 Territory 参加記

AHC008 に参加していました。

atcoder.jp

方針

大きく分けて「柵を配置する」「動物を捕まえる」の 2つのフェーズでゲームを進めていきます。

• 複数人で 1つのチームを作ってチーム単位で行動を行う
• 部屋の中に予め設定しておいた柵を配置する
• チーム単位で動物の捕獲を行う

チームの作成

1人でペットを追いかけても捕獲するのが非常に困難なので、複数人で対象の動物を捕獲します。人間の数にもよりますが基本的には 2チームに分かれて捕獲を行います。

人間の数によってチームのメンバー数と編成数は変化します。

• 5人 (3, 2)
• 6人 (3, 3)
• 7人 (4, 3)
• 8人 (4, 4)
• 9人 (4, 3, 2)
• 10人 (4, 3, 3)

柵の配置

今回はグリッドサイズが 30 * 30 で固定だったので、前もって柵を配置する場所を決めておいてそれに元に柵の配置を行います。 今回自分は全部で 11個の配置パターンを用意しました。

基本的には図のような配置になります

ポイントとしては主に以下の 2点になります

• 人が横移動するだけで捕獲が可能
• 犬、猫を捕獲するための通路の作成

その他の配置パターン

M = 5

M = 6

M = 7

Mが小さいケースでは 4ラインだと人が足りなくなってしまうので 3ラインに減らしています。 また、M が 7以下の場合は 1回の横断で柵を設置しきれないため、柵の数を少なくしてなるべく早く設置出来るようにしています。

M >= 8 かつ動物の数 <= 12

人間の数が多くて動物の数が少ない場合は柵を多少減らしても達成率に影響が無いので、なるべく少ない柵の設置で目標が達成出来るようにパターンを修正しています。

横移動のみでの捕獲が可能

柵の設置が終わると水色のラインに人を割り当て、後は対象のペットに対して横軸を合わせるだけで捕獲が可能になります。

チームは横軸を合わせて行動することでペットが捕獲範囲に入ってきた際にすぐに捕獲出来るようになります。

その他の配置箇所

M = 5 (3人, 2人）

M = 6 (3人, 3人）

M = 7 (4人, 3人）

M = 8 (4人, 4人)

M = 9 (4人, 3人, 2人)

M = 10 (4人, 3人, 3人)

犬、猫の捕獲

今回の問題では完全にランダムではない行動を行う動物として「犬」と「猫」の 2つが用意されていました。 これらの動物は最初の行動が「目的地に近い方向に移動」というものなので、通路を用意してあげればそこに勝手に入って来てくれて捕獲することが出来ます。

乱数次第ではずーーーっと横移動だけを行い通路を使ってくれないパターンもあるとは思いますが、基本的にはそのようなことは発生しないので特に問題はありませんでした。

通路の長さは 4以上を確保する

「犬」「猫」「豚」に関しては移動距離が 2であり、 移動前と移動後の (x + y) の偶奇が変化しないので最小効率の 3の通路で捕獲しようとすると捕まらない可能性があるのでそれを避けるために 4以上の長さを確保する必要があります。

この場合、緑マスに止まる「犬」「猫」「豚」は絶対に捕獲することが出来ません。

長さを 4以上にすることでどちらの場合でも捕獲可能なマスが存在するようになります。

通路から出ようとしている「犬」「猫」は積極的に捕まえに行かない

例えば図のような状況下で最初の行動が下方向だった場合、絶対に通路内に入ってくることは無いので捕獲対象としての優先度を下げるようにします。

その場待機 or 通路からの脱出のいずれかの行動になるので追ってもあまり意味がないです。

通路に入ろうとする「犬」「猫」は捕まえに行く

図のように通路の中に入っていく動きをしている場合は高確率で通路内に侵入してくる可能性があるので捕まえに行きます。

最後の 1匹を無理やり捕まえに行く

今回のスコア計算ではペットが 1匹残っているだけでスコアが半分になってしまうので、最後の 1匹に関しては無理やり捕まえに行きます。

その時に使用する捕獲のパターンです。（画像は M >= 8 の時に使用するもの）

赤いマスの部分は最後に部屋を閉める場所になっています。

最後の捕獲に関してはゴリゴリに if 文を書いてるのでかなり無理矢理な実装になってます。

牛が全然捕まってくれず最後に捕まえにいっている様子がわかると思います。

「最後の 1匹ではなく 2匹だともっとスコアの取りこぼしが少ないのでは？」と思ったのですが、この方針だと捕獲までにかかる柵の数と閉じ込めた際の空間の消費量が「待ち」の戦略に比べて増えてしまうので、全体的なスコアとしては下がってしまったので採用しませんでした。

感想

今回は比較的得意な分野（二次元グリッド + マルチエージェント）だったので、特に大きく方針を外すことなく実装出来たかなとは思います（1位のスコアの 9割が毎回の目標値 - 今回だと20位辺り）。柵の配置を固定ではなくて不定形にすることで 7G あたりのスコアが出ることは確認していたので (seed 0 で確認 77111111）、もう少し期間があればそっちの方針も試していたのかなとは思います。（不定形だと犬 & 猫の捕獲は難しいので「犬」「猫」「その他」で戦略を切り替える。このあたりを実装してきて 7G ぐらいを出す人が出てもおかしくないなとは思ってました）

もし他のヒューリスティックコンテストに興味があるという方は 3/17 2:00 から Topcoder Marathon Match 134 が始まるので是非参加してみてください。（ただし、こちらに関してはコンテスト期間中の解法や考察に関する言及は禁止となっているので注意が必要です）

使用素材

サラリーマン（事務職） | ドット絵ダウンロードサイト DOTOWN

茶色のネコ | ドット絵ダウンロードサイト DOTOWN

Hitachi Hokudai Lab. & Hokkaido University Contest 2021 の感想

atcoder.jp

に参加してました。と言っても最低限のコードを書いて終わったのでガッツリ参加したというわけではありませんが、 全体を通しての感想を残しておきます。（どちらかというと要望）

運営も自虐するぐらいにはグダっていたと思います。

共通

アナウンス無しの延期は止めてほしい

• OO 日に更新予定です。 -> OO 日に特に何も無し
• XX 日に公開予定です。 -> XX 日に特に何も無し

このパターンが多かったです。当日でも良いので延期のアナウンスがあったほうが嬉しいです。（アナウンス無しは「もしかして放置されている？」と不安になります）

ジャッジプログラムや問題文の更新が多い

正直多すぎました。特にコンテストの序盤とかはちょっとジャッジプログラムを読み進めるだけでもすぐ問題文との矛盾点が見つかるぐらいには多かったです。4000行近くのジャッジプログラムだったので不具合が多いのは仕方ないと思いつつ、コンテスト終了直前まで定期的に修正が入るのはさすがにきつかったです。

ジャッジプログラムが読みにくい

不要な ; やif (false) のようなコードが多く、ジャッジプログラムを読むときには毎回消しながら読んでいました。

エラーメッセージが不親切

コンテストタント側のプログラムが何かしらの制約にひっかかって落ちた時にエラーメッセージ無しに exit(1); だけで終わらせていたので原因を突き止めるのに時間がかかりました。 （自分でエラーメッセージを追加してました）

ジャッジプログラムの計算資源を別で管理して欲しい

今回制限として「実行時間制限: 300 sec」「メモリ制限: 3072 MB」とあったのですが、正直何の指標にもなりませんでした。 というのも今回、コンテスタント側はジャッジ側にクエリを投げることで仮スコアを得ることが出来たのですが、 クエリの処理にかかる「時間」と「メモリ使用量」がこの制限に含まれていました。そのため、コンテスタント側で制限を守っていてもジャッジ側の処理でそれを超えてしまう可能性がありました。

様々なケースが考えられる中でテストケースのジェネレータも無いままジャッジ側のメモリの最大使用量を見積もるのは面倒でした。

「時間」に関しては A 問題だと、グリッド配置を決めたら後はジャッジプログラムが処理するだけなのですが、例えば 280sec 使って配置を決めても、ジャッジ側の処理で 21 sec 以上使ってしまうとアウトなので、コンテスタント側では「この配置だと XX sec 使用する」みたいな予測を行って、余裕をもたせてプログラムを終了させる必要がありました。

コンテスト序盤とかはほぼ何もしてないサンプルコードでも 90 sec 近くかかっていました。（改良版が出て 20 sec ぐらいには下がりました）

テストケースジェネレータの提供もしくは生成方法の擬似コード表記

今回 pretest が 3件だけだったので、システムテストが重要になってくるのですが、システムテストでどのようなパラメータになるのかがちょっとわからなかったです。 例として

(例: 系統から電力を購入することによるペナルティ(alpha_buy_ele やalpha_buy_env)が大きいケース、w_acc, w_trans, w_ele, w_envのいずれか1つが小さくなるケース)

とあり「alpha_buy_ele や alpha_buy_env は制約内でランダムに決められる値ではないのか」「いずれか1つが小さくなるケース ということは他のパラメータは同一の値なのか」とか色々質問したい事項がありました。

将来的な技術動向や政策動向を考慮し、特定のアセットや条件などが有利になるケースを含むように選択

と書かれてしまうと正直もう個人的にはお手上げでした。

相対スコアの導入

今回大まかに「輸送スコア」「電力スコア」「災害対応スコア」とカテゴリー別のスコアがあったのですが「輸送スコア」で得られるスコアが他のスコアに比べて大きかったので「輸送スコアを得意とする人」と「電力スコアを得意とする人」を比較した時に「輸送スコアを得意とする人」が有利となってしまうので、各スコアを平等に評価するのであれば相対スコアで比較したほうが良いと思いました。

A 問題

サンプルコードの充実化

A問題のサンプルコードが簡素なシェルスクリプトだったのは不親切かなと思いました。 問題自体が多くの入力を受け取る必要があったのでサンプルコードを書くコストもそれなりに高かったと想像できるのですが

なお、初心者向けのサンプルコードを用意しているので、必要に応じて参照して欲しい。

この文言からの

#!/bin/sh

echo end
echo 2
echo 1000 10000
echo 1 3
echo 1 
echo 1 3
echo 1
echo 1561 20000
echo 1 2
echo 1 
echo 1 3
echo 1 
echo 2
echo 1000 100000 1
echo 1561 100000 1
echo submit 9999 1

このコードは少し不親切かなと思いました。最低限入力を受け取るあたりのコードは欲しかった気がします。

車両アルゴリズムの説明

A 問題はグリッドと EV の配置を決めたら後はジャッジ側で事前に用意されたアルゴリズムによって処理が行われていくのですが、この車両アルゴリズムについての説明が一切無いのでジャッジプログラムを読んで理解する必要がありました。

A 問題の目的として「安定した電力供給に加えて円滑に輸送サービスを提供するために適切なナノグリッドの配置を考えて欲しい」とあるので、車両のアルゴリズムについてはある程度出題者側から説明が欲しかったです。

B 問題

ジャッジプログラムに計算資源を取られること以外は特に不満はありませんでした。