日立北大ラボ×北大コンテスト2021参戦記(総合5位解法)

# はじめに
本記事は、AtCoder上で2021/11〜2022/1に行われた[日立北大ラボ×北大コンテスト2021](https://atcoder.jp/contests/hokudai-hitachi2021)の参戦記です。
このコンテストで総合5位を獲得したアプローチについて書きます。(※システムテスト前の暫定総合順位は2位でしたが、PV購入条件をバグらせてしまったせいで最終順位が大分落ちました)

このコンテストは持続可能な地域社会実現に向けた自立型エネルギーシステム構築モデルの確立を目指し、良いアルゴリズムの発掘を目的としたもののようで、競技プログラミングに参加しながら社会貢献できそうなテーマとなっております。

初めにお詫びがあります。今回テストケースとなった地域社会に対して、以下のような仕打ちをしてしまいました。

- 太陽光発電の設置可能面積の処理にバグがあり、土地が足りないのに太陽光発電を設置し過ぎてしまいました
- 災害時はスコアに影響しないからと言って、燃料を省みず必要かどうかも判断せずに自家発電機をフル稼働してしまいました
- EVは輸送専用マシンとしてしまい、電力を運ぶ役割を果たせませんでした
- EVチャージャーは作業機械に自家発電機や系から充電するのみの目的で設置し、EVの充放電を全く行いませんでした
- したがって、EVは初期充電から全く追加充電しなかったので、電力が尽きたら行き倒れにしてしまいました
- スコアが得られない輸送需要は全て拒否してしまいました

ここに、テストケース地域社会の住民の方々、SDGs関係各位に深くお詫びをいたします。ただ、最初の頃は輸送のみに明け暮れて災害対策や電力対策には目も向けませんでしたが、最終的には多少は考慮することができました。

以後、問題内容については知っているものとして書き進めます。まだ問題を見ていない方は公式サイトの「[A問題 地域エリアデザイン](https://atcoder.jp/contests/hokudai-hitachi2021/tasks/hokudai_hitachi2021_a)」「[B問題 地域エリアデザイン＋日々の運用](https://atcoder.jp/contests/hokudai-hitachi2021/tasks/hokudai_hitachi2021_a)」をご参照ください。

# 基本方針
経緯として、コンテストの最終盤までB問題を中心に取り組み、最終日にB問題の初期配置部分を突貫でA問題に移植するというやり方で取り組んだので、結果的に両問題ともほぼ同じ考え方で実装されています。なので、本記事では両問題で事情が違う部分以外はあまりどちらの問題向けか区別せずに書きたいと思います。

B問題を中心に取り組んだので、最初の頃は得点効果の高い運搬をいかに効率良くやるかというところに終始しました。その転機となったのは以下の2つの気付きでした

<dl>
<dt>借金の発見</dt>
<dd>最初は資金1超過あたりのペナルティが1000〜2000点もあり、初期資金額は「超えてはいけないもの」という先入観がありました。しかし目的はスコアを最大化することなので、コスト超過ペナルティを課せられてもスコア的に得することであればやるべき、という発見がありました。</dd>
<dt>資金あたりのスコアの最大化</dt>
<dd>スコアを得るためには運搬をやったり災害対応をやったりといろいろ手段がありますが、スコアの源をたどると最終的には初期に購入した設備に行き着くので、いかに「得られる見込みスコア/そのために購入した設備の資金」を最大化するかが肝になってきます。</dd>
</dl>

つまり、やるべきこととしては以下のようになります。

- スコアが得られそうな戦略(アプローチ)を考える。例：EVを購入して運搬を行い、運搬スコアを得る
- 各戦略に対して、どれだけ資金を投入するとどれだけスコアが得られそうか見積もる(実質的に「日々の運用」)
- 見積もりに基づいて、各戦略に適切に資金を割り振ってスコアを最大化する(実質的に「エリアデザイン」)

問題文を見れば分かる通り、この問題は非常に多くの要素が登場し、見通しよく実装しないとソースコードが収拾がつかなくなってしまいます。上記のようにやるべきことがある程度抽象化した状態で見えてきたため、実装としては「戦略」に相当する共通のinterfaceを定義し(言語はJavaを使いました)、その実装クラスを運搬用クラス、作業用クラス、と言ったように書いていくことにしました。

このinterfaceには以下のようなメソッドを用意しました

1. 戦略の実現可能性や、資金当たりのスコア予想等の前計算
1. コストペナルティを課せられても得をする設備の購入予約
1. 残り資金で購入可能な設備のうち、最も効率良くスコアを得られる設備の提案
1. 3.で提案した設備の購入予約
1. 残り資金＋一部借金で購入して得をする設備のうち、最も効率良くスコアを得られる設備の提案
1. 5.で提案した設備の購入予約
1. 購入決定と初期配置の決定、日々の運用のための事前準備
1. 日々の運用時の1日の始まりで実行する前処理
1. 日々の運用の各ターンでの処理の実行

細かいことを言えば「3と5」「4と6」は同じメソッドだったり等あるのですが、概ねこのような感じです。そしてメイン処理側で各戦略の1と2を呼んだ後、残り資金でできることがある限り3,4を繰り返し、なくなったら最後に5,6を実行して、それが終わったら7以降に進むという形になります。

戦略としては以下のようなものを考えました。基本的にはそれぞれ独立した戦略となっていて、独立したクラスとして実装しやすい戦略を考えました(正確には災害対応戦略と電力需要地対応戦略はかなり関わりが深いので、実装としては統合しました)

| 戦略 | 購入設備 | 得点源 | 対価(副作用) |
|:--|:--|:--|:--|
| 運搬対応戦略       | EV  | 運搬スコア | 電力収支スコア(EVの電力消費) 　|
| 作業対応戦略       | EVC | 作業スコア | 電力・環境スコア(系電力の購入) |
| 作業電源改善戦略    | EV  | 電力・環境スコア(系電力低減) | 電力収支スコア(EVの電力消費) |
| 災害対応戦略       | FE or RB | 災害対応スコア | なし  |
| 電力需要地電源改善戦略  | FE or RB or PV | 電力・環境スコア(系電力低減) | 電力・環境スコア(RB収支・FE燃料) |
| メガソーラー戦略  | PV + (RB or EV+EVC) | 電力収支スコア  | なし  |

ただし、実際には作業電源改善戦略(これはEVを購入して毎日の作業地に移動し、作業に必要な電源を供給することで電力・環境スコアの改善を目指すという戦略です)は急造しすぎて動作が安定しなかったので、最終投稿からは取り除きました。また、メガソーラー戦略(これはPV設置効率の良さそうな土地にRBやEVなど充電できるものを置いて、電力収支だけで得を目指すものです)はあまり効率が良くなさそうなことと時間がなかったことから諦めました。
したがって、結果として4つの戦略を実装しました。

# 各戦略のポイント
## 運搬対応戦略
EVを購入して、orderを処理し作業スコアを得る戦略です。
### 日々の運用(orderの割り当て)
EVに「動作計画」を持たせて、新たなorderが出現する度にそれを追加・変更していく形で実装しました。「動作計画」はEVの移動目的地(これは隣の頂点とかの粒度ではなく、次のorderのpickup場所というレベルの目的地)とその目的地でどのorderをどうするか(積む・降ろす)をセットにしたものです。
こうしておくことで、あるEVの現在の動作計画が「order1を頂点X0で積む」→「order1を頂点X1で降ろす」だったとして、order2が出現したときに「order2を頂点Y0で積む」→「order1を頂点X0で積む」→「order2を頂点Y1で降ろす」→「order1を頂点X1で降ろす」というような割り込ませ方ができるようにしました。
この状況は、AHC006の[Food Delivery](https://atcoder.jp/contests/ahc006/tasks/ahc006_a)と似たような状況で、orderとEVの組に対してDPで最適な動作計画の追加位置を求めました。DPは、
- 状態0: 新規のorderを全く処理していない状態
- 状態1: 新規のorderの積み込みだけ行なった状態
- 状態2: 新規のorderを積み込み、目的地で降ろすところまで終わった状態
として、既存の動作計画の目的地間に0→1、0→2、1→2を挿入した時の得点の増加を記録していくようなやり方を行いました。このやり方で各EVにorderを処理させた場合のスコア増加を求めたら、あとはスコアが増加しているEVの内、貪欲に最も増分が大きいものに処理させるようにしました。
途中でEVの定員を超えないようにするとか(定員超過する場合は状態1を破棄)、運搬スコアだけでなく距離の増加による電力収支をスコアに参入しておくとか、結構ややこしい処理にはなりましたが、これによって複数orderの同時運搬ができるようになりました。

### 距離の計算
さて、上記の日々の運用のアルゴリズムを実行するに当たって問題になってくるのが距離の計算速度です。今回頂点数が20000までとなっています。今回の制限である実行時間300秒・メモリ3GBであれば全頂点間の距離をdijkstraで事前計算してメモリに保持しても何とか足りる可能性はあります。実際にそうした方が良かった可能性はありますが、私は違う方法で実装しました。

今回のマップは実際の地図をデータ化したもののようでした。

https://twitter.com/tanaka_a8/status/1468178981006499844

この知見を元に実際の地図などで使える距離計算アルゴリズムをググってみたところ、「[2-Hop ラベルの直接的な計算によるグラフ最短経路クエリ処理の効率化](https://db-event.jpn.org/deim2014/final/proceedings/A8-3.pdf)」という論文に行き着きました。この論文の4章に書かれていたアルゴリズムを実装して使用しました。
テストツールで提供されていたマップの範囲では、事前計算が数秒程度、1回の距離計算が数マイクロ秒程度(dijkstraを毎回やる場合の数百分の1程度)という感じで、メモリ使用も数MB〜数十MB程度といったところでした。

### スコアの見積もり
基本方針のところにも書きましたが、購入資金の割り当てを決めるために、EVを何台買ったら何点くらい取れる見込みというのを見積もる必要があります。そのため、orderを入出力1で得た条件の個数で生成しておき、「日々の運用」のアルゴリズムに基づいてシミュレーションしてスコアを算出することにしました。ただ、それなりに実行時間がかかるので試せるEVの台数パターンは限られます。

そこで台数を何パターンかシミュレーションし、あとは何らかの関数の形を仮定して平均二乗誤差を最小化する形で近似することにしました。

スコアは台数が増えれば増えるほど上がるはずですが、おそらく段々伸びは鈍って、最終的にはペナルティ0に収束していくことが想定されます。実際に実験してみたところ、上記の運搬方式だとある程度台数が増えてくるとスコアは$a-b/x^2$(xはEV台数)のような形に近いようでした。理屈的には-2乗ではなく-1乗になりそうな気もしたのですが、-2乗の方が近そうだったのでそちらを採用しました。台数が少ないうちはxに比例気味にスコアが伸びていき、徐々にスコアの伸びが鈍化して$a-b/x^2$に近づくという感じだったので、以下のモデルと仮定しました。

```math
\begin{eqnarray}
 f(x) = \begin{cases}
    a - b/x^2 & ( x \geqq x_0 ) \\
    cx^2 + dx & ( x \lt x_0 )
  \end{cases}\\
\end{eqnarray}
```

2個目の式は原点を通る2次関数ですが、c<0で上に凸なものを想定しています。上下の式は滑らかにつながってほしいので、$x=x_0$において両式の値と傾きが等しいという条件を入れると、実質パラメータ3つの式としました。下のグラフのようなイメージです(縦横は適当な係数で調整しています)。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/202945/bd467df9-29b2-2cfa-9746-4924fa6ccfd6.png)

これによって、例えばEVを10台から11台に増やした場合のスコアの増分予測ができるようになりました。

B問題はこれでまずまず問題ないと思われるのですが、A問題はジャッジ内のアルゴリズムで運搬が行われるため本来であればtestコマンドでサンプリングするのが良いと思われます。ただ、A問題は最終日にB問題からの移植で急造したためtestコマンドで拾ってくる手当てができず、サンプルケースだと自前アルゴリズムの5〜20%程度という感じだったので15%だということにして提出しました。

プログラムの実行時間には少し余裕があったので、もう少しシミュレーションのポイントを増やすとか、区間ごとに1次関数、2次関数、-1乗、-2乗で最も近似の良いものを使うとか、更なる工夫の仕方はあったように思います。

### EV車種の選定
使用するEVの車種は、台数をなるべく増やすために一番安いものにするか、購入額あたりの走行距離が一番長いものにするかどちらかかなと思ったので、条件を満たす車種が異なる場合は両方シミュレーションして、コストあたりのスコアが一番良いものを使うことにしました。

### EVの初期配置
一度EVが動き始めてしまうと関係なくなりますが、最初の1個の運搬のペナルティを少なくするためにはなるべく運搬が出現しそうな場所にEVを初期配置しておきたいところです。EVはナノグリッドに置く必要がありますが、幸い有料の設備を何も買わなくてもナノグリッドは作れるので、EVだけ購入すればコストを気にせずに好きなところに初期配置することができます。

なので問題としては、N台EVを置くとして、EVを置いた頂点に対して、自EVが一番近い頂点をそのEVの担当エリアだと思った時に、担当エリア内の人口と距離の2乗の積の総和が全体としてなるべく少なくなるようにN台を配置したい、というのを考えることにしました。

最初は乱拓山登りで実装していたのですが、orderシミュレーションをやろうとすると台数のパターンを増やさなければならず、実行時間上結構なネックになっていたので、最終的には以下のように逐次統合を行なっていくアルゴリズムである台数以下の任意の台数の配置パターンを求めていくことにしました。

1. 大きめの台数$N$を決める。今回は全頂点数の半分と3000の少ない方にしました
1. $N$台を人口比例でランダムに配置。この配置は、選んだ頂点数が多いので運搬ペナルティはあまり多くないと想定されます
1. $N$個の頂点の内、担当エリアの各頂点の人口を$p$、EV頂点との距離を$d$とした時に、$\sum p(d + 1)^2$の値が最も小さい頂点を選択
1. 3で選んだエリアに隣接するエリアの中で、$\sum p(d + 1)^2$の値が最も小さいエリアを選択
1. 3と4で選んだエリアを取り除き、元々EVを置いていた2頂点を最短距離で結ぶパスから両端を含む頂点をいくつか(今回は5つにしました)選定し、新EV頂点候補とする。この各候補に対して周囲のエリアも含めてエリア境界の再計算と$\sum p(d + 1)^2$の増減を計算し、最も小さくなる候補を選定
1. これによって$N-1$頂点の配置が得られたので、3〜5を頂点数が1になるまで繰り返す

$\ $ 要するに、存在意義の薄そうなEV頂点を逐次統合して配置を決めていくというやり方です。合併の際のエリア決めや$\sum p(d + 1)^2$の再計算に時間がかかりそうですが、統合するエリアと近隣のエリアにしか影響しないので、うまく実装すれば各回概ね$O(V/n)$程度の計算量で済みます(nはその時点のエリア数)。正確には影響範囲がどこまでかを持ちながらやったので、その部分は全体の頂点数Vに比例しているのですが、フラグなのでBitSetを使うことでVが数万程度であればあまり大きな問題にはなりませんでした。

また、3〜4で選ぶ頂点をもう少しうまく工夫することでもっと理想的なパターンにできそうな気もしますが、他にたくさんやることがあるので今回はこれくらいにしました。

### ビジュアライザ
問題AでEVがどう動いているか謎だったのと、問題BのEVの動きのデバッグのためにビジュアライザを開発しました。

- [A問題用ビジュアライザ](https://lavox.github.io/hokudai-hitachi2021-tool/a/vis_a.html)
- [B問題用ビジュアライザ](https://lavox.github.io/hokudai-hitachi2021-tool/a/vis_a.html)
- [ソースコード](https://github.com/lavox/hokudai-hitachi2021-tool)

ジャッジツールが複雑だったので、ジャッジツールの移植は諦め、ジャッジツールにビジュアライズ用のログ出力機能を追加し、そのログを読み込んで表示するような形式にしました。

ログを読み込んで表示するような形式にしました。

せっかくなので使ったライブラリを紹介しておきます。

- [Vue.js v3](https://v3.ja.vuejs.org)
- [vis.js](https://visjs.org)
- [chroma.js](https://gka.github.io/chroma.js/)

マップの表示は2個目の[vis.js](https://visjs.org)で行なっています。このライブラリは、グラフの辺の伸び縮みなどの物理演算を行う機能があるのですが、さすがに今回のような頂点・辺の規模になると重くなる（その上今回の目的にとって意味がない）のでオフにしました。

このビジュアライザはコンテスト期間内にGitHubで公開し、Twitterでも告知したので何人かの方に使っていただいたようで、励みになりました。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">EVやorderの状況に対応したビジュアライザーを公開しました。超簡単な使用方法を書きましたが、GitHubに置いたログ出力機能追加版judge_A.cppを使ってログを出力し、ビジュアライザーに読み込ませてください。<a href="https://t.co/kA0CjWq1Na">https://t.co/kA0CjWq1Na</a><br><br> <a href="https://twitter.com/hashtag/2HC2021?src=hash&amp;ref_src=twsrc%5Etfw">#2HC2021</a> <a href="https://t.co/0PEuDM0kh7">pic.twitter.com/0PEuDM0kh7</a></p>&mdash; Tanaka.A (@tanaka_a8) <a href="https://twitter.com/tanaka_a8/status/1472480189586509830?ref_src=twsrc%5Etfw">December 19, 2021</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

運搬系の部分しか作れませんでしたが、電力需給や災害対応などの部分も実装できたら良かったというのが反省点です。

ビジュアライザは作りましたが、正直なところA問題のEVの動作ポリシーはよくわからないままでした。ただ、全く稼働しないEVもあるようだということはわかりました。

## 作業対応戦略
EVCを買って作業機械に充電できるようにし、作業を実行することで作業スコアを得る戦略です。
### 実行可能性の計算
作業を完遂できるかどうかは、作業可能時間帯に極力たくさん作業をするようにして最終的に終わるかどうかで判断しました。ある連続した作業可能時間帯の中で、理想的には必要な電力量をまず充電し、充電できたらその時間帯終了まで作業し続けるというのが良いのですが、作業機械の蓄電量の制約から作業し続けるターン数には限界があります。そこでその時間帯に行う作業を何分割かして、次に行う作業分の充電→分割した1つ分の作業を繰り返していくことになります。

上記情報の計算には以下の要素が関連してきます。

- その連続した作業可能時間帯のターン数$r$
- その連続した作業可能時間帯の初期蓄電量$c$
- 1ターンでの最大充電量$W$
- 作業1回あたりの必要電力$\mathrm{\Delta}_{\mathrm{work}}$
- 作業機械の最大蓄電量$\mathrm{Cap}^{\mathrm{work}}_{\mathrm{ele}}$
- 最小連続作業ターン数$I^{\mathrm{work}}_{\mathrm{min}}$

EVCの機種を決めると、作業機械への1ターンでの最大充電量が決まります(EVCの最大出力と、作業機械の最大充電量の小さい方)。作業機械には充電効率ηがあるのでそれを掛けた値/100が、作業機械に1ターンで実際に充電される量になります(W)。

この連続期間の必要電力量の関係から、実際に作業可能なターン数をwとすると、以下の式が成り立ちます。

```math
w \mathrm{\Delta}_{\mathrm{work}} \leqq c + (r - w)W
```

この式はwについて解くことができ、この期間内で可能な最大作業ターン数が求まります。一方、作業機械の最大蓄電量までしか蓄電できないので、連続最大作業ターン数は最大蓄電量(充電効率のロスがあるので少し差し引いたもの)を作業1回あたりの消費電力で割った値となります。

なので、このターン数を超えず、かつ最小連続作業ターン数以上にはなるように期間を分割し、かつこの期間内の作業総量がwを超えないようにするような分割数を求めて、繰り返し実行するようにしました。

これをt=0から貪欲に繰り返し最終的に終われば作業完了可能、無理であれば不可と判断しました。当然作業禁止時間帯は残り作業に必要な範囲で充電するという前提でシミュレーションを行います。
(もしかしたらもう少し工夫したやり方により、押し込める作業が増える可能性もあるかもしれません)

ここまではEVCの機種によるので、安いEVCの機種から順に試し、作業可能で一番いEVCを使う前提でスコア効率を見るようにしました。もちろん、得られるのは作業スコアですが、系から購入した電力スコア・環境スコアを差し引いて評価する必要があります。

### 電源改善(未実装)
これは一度実装してみたものの、バグが取りきれず最終的には投稿しなかったのですが、作業に必要となる電力のコストを下げる試みです。

作業地は日毎に場所が変わっていくため、RBやPVのように固定の設備の購入はあまり効率が良くないように思われます。作業を実行する際は必ずEVCが必要となるので、EVを購入して日替わりで作業地を回って電源供給するようにすれば、その分系電力の購入が抑えられてスコア改善になることがあると見込まれます。

実際に仮実装したところでは、テストケースCで改善効果がありました。

## 災害対応・電力需要地電源改善戦略
### 災害対応時の対応可能性の計算
災害時の電源供給として、EVは残量が読みにくかったのでFE,RBで対応する方針としました。特にB問題ではFEの出力が自分で決められる上、災害対応期間は燃料消費のペナルティが全くないので、FEは災害対応中は常に全開で使用するという前提を置くことができます。A問題では、コンテスタントに開示されていないRBの最大出力値があり、それを超えた場合はFEの出力上限までの範囲でFEが使われるというロジックとなっているようです。

また、ジャッジツールのアルゴリズムを見ると、電力需要地では与えられた分散で需要量は正規分布していましたが、避難所においては同一Divでは一定値のようだったので、それも前提に置きました。

満たすべき条件は以下の2つになります。

- 災害対応期間中、1ターンでも供給不足にならないような最大出力があること
- 災害対応期間中、RBの蓄電量が尽きて、FEだけで賄えないようにならないこと

前者についてですが、電力需要地の需要量が正規分布に従うため、FEやRBの出力量がある程度大きかったとしても理屈上ではごく稀に瞬間電力需要が出力量を超えてしまう可能性はあります。なので、ある程度の確率で超えないという目安ラインとして、5.5σ以上の余裕があれば問題なし、5.0〜5.5σになる期間は10000ターン以内であれば問題なし、4.5〜5.0σになる期間は2000ターン以内であれば問題なし、それ以下しか余力がない期間は少しでもあるとNGということで、FEとRBの機種の組み合わせごとに対応可否を判断しました。(A問題はRBの最大出力量が分からないので、0であるという前提で判断しました。もしかしたらtestコマンドで電力スコアを観測することでRB各機種の最大出力量を求めることができたかもしれません)

後者については、nターンまでの需要電力の分散はnσであるとして、蓄電量のシミュレーションを行い、それまでの蓄電量の最大〜最小分を必要量とし、かつ1日通算で蓄電量がマイナスであれば、その量の日数分を加え、FEとRBの組み合わせごとにRBの災害対応開始初期の蓄電量の必要値を求めました。それに通常運用時1日分の必要電力量を加えて、RBの必要値としました。

1つ懸念事項として、電力需要地や避難所が作業地と重複していた場合は、通常運用時に作業側にRBが使われてしまい、災害対応開始時に必要蓄電量が残っていないかもしれないということが想定されます。レアケースとは思われますが、電力需要地や避難所が作業地と重複した場合はコスト効率が悪い方を諦めることにしました。

### 電力改善のための電源の選定
災害対応をするにしてもしないにしても、電力需要地の電源をどう改善するかという課題があります(なお、避難所は災害時にしか発生せず、災害対応時は電力・環境スコアがないため、改善してもスコアに影響しません)。

改善に使えそうな設備としてPV、RB、FEを設置した場合のスコアの変化を計算することにしました。実際に計算したのはFEの機種、RBの機種、RBの台数、PVの台数の組み合わせごとのスコアで、RBとPVの台数は1日に使い切れる量を日ごとに順番に並べて、その境界値だけを求めることで計算量を制限しました。FEやRBの機種が少なく、運用日数も16日が最大なので、これでも十分高速に動作しました。

ただこのロジックの中で、PVの台数の境界値を求める際に土地ごとのPV設置数上限の考慮が一部抜けてしまい、<font color="red">初期予算が潤沢な場合にPVを設置可能数を超えて購入してしまうという致命的なバグを埋め込んでしまいました</font>。単にスコアが下がるだけというバグならともかく、制約違反してしまうというバグは、発生してしまうとアウトなので、念には念を入れて確認する必要があるという教訓が得られました。

# その他の工夫
### ログ
今回の実行形式が、ジャッジツールから自プログラムが呼ばれて実行される形式で、デバッグが非常に行いにくかったため、手元で実行する際はメインクラスを継承してログの機能を追加した別クラスを用意して実行していました(本番用クラスではログ出力メソッドは空実装)。

それでも何か挙動がおかしい時の調査が困難を極めたので、ログなりビジュアライザなりもう一工夫が必要だった気がします。

コンテスト終盤でPV導入に関する追加実装時にバグを埋め込んでしまったのも、この辺りに遠因があるような気がします。

### ソースの分割
普段のヒューリスティックコンテストと比較して格段に登場する要素が多く、コーディング量も多かったため、ソースファイルを分割して作成し、投稿時に結合する仕組みを取り入れました。

途中までは1ファイルで編集していたのですが、それに比べると格段に生産性が向上しました。

# コンテストの経過と各戦略の効果
B問題で何を導入したらどの程度点が伸びたかを書き残しておきます(点は暫定テストのスコア)。

- 運搬のみに終始。1度に1orderの貪欲処理で9.90G点
- 複数orderを同時に処理できるように改善。10.09G点
- EVの初期配置を乱拓山登りで実装。10.18G点
- ソースの整理により原因不明の改善。10.28G点
- 初期資金超過を許容。10.41G点
- 作業対応。10.81G点
- 災害対応。10.857G点
- EV初期配置位置のアルゴリズムを逐次統合型に改善。10.861G点
- 通常運用時の電力需要地電源改善対応。10.863G点
- 電力需要地のPV設置対応。10.863G点

こうしてみると、最終的に行ったPV対応で全然スコアが上がらなかったにもかかわらず、使える手段は多い方が良いという判断からコードは残したのが、バグを埋め込む原因となってしまいました。

# 所感
- 長期間でかつ問題やジャッジの不備も多かったですが、コンテストというよりは研究への貢献だと思うことにしてモチベを維持しました
- 作ってみたビジュアライザを公開したところ、Twitterでも使っている方を何人か見かけ、これもモチベ維持につながりました
- 運搬・作業・災害対応などのミニゲーム＋資金配分ゲームという感じで、どこに主眼を置いた研究なのかが見えにくかったです。背景を読んだ感じだと全体最適的な方向性を目指しているのだと思いますが、それにしては運搬に比重が偏った配点になっているので、せめてシステムテスト仕様をもう少し早めに公開し、テストツールに含まれるケースもバリエーションを増やした方が良かったのではないかと思いました
- 最初は運搬一辺倒で全然エネルギーシステムっぽくない解答を作っていましたが、最後の方では作業や電力の改善にも取り組むことができ、ある程度は趣旨に沿った解答を作れたのではないかと思います(結果、盛大にバグらせてしまいましたが)
- コンテストとして見た時に、ジャッジの実行時間やメモリ使用が多い上にそれも含めた実行制約になっていたり、パラメータの生成方法が明かされていないためどう想定して良いか分からなかったりと困る部分が多かったです。極端な話、各Divで運搬数最大のテストケースがあればTLE続出したと思いますが、それがないという保証もなくモヤモヤしながら取り組みました。システムテストの仕様はもう少し詳細に公開していただければと思いました。
- 問題が巨大過ぎて、運営の方も問題文やジャッジの不備の潰し込みが手に負えなくなっているように見受けられました。少なくとも手に負えるレベルの問題ボリュームにして欲しいのと、ジャッジツールはGitHubなどで共有した方がコミュニケーションが早かったように思います(不備があること前提になっていますが)

いろいろ問題も多くTwitterなどでもやや炎上気味になっていますが、問題自体には楽しく取り組むことができました。運営の方も大変だったと思いますが、おつかれさまでした。

また、参加された皆様もおつかれさまでした。