# Hitachi Hokudai Labo & Hokkaido University Contest 2020 A サンプルプログラム

* これは、Hitachi Hokudai Labo & Hokkaido University Contest 2020 A で使われるサンプルプログラムの説明になります。本プログラムを使用することで、ローカル環境で解答プログラムの得点計算が行えます。
* 本プログラムの使用は自己責任でお願いいたします。これらのプログラムを使用することで発生したあらゆる損害に関して、北海道大学と日立製作所は補償いたしません。
* 得点計算を行うプログラムは、実際のコンテストで解答プログラムの得点計算を行うプログラムと同一ですが、実際のコンテストで使用するテストケースやシードは非公開となります。このため、これらのプログラムによって計算された得点は、当コンテストの得点を保証するものではありません。

## サンプルプログラムの概要

`src` フォルダ内には以下のコードが格納されています。

* `judge_A.cpp`
* judge の役割を担うプログラムです。
* `judge_A.lib/`
* `judge_A.cpp` で必要とされるヘッダファイルが格納されています。
* `generator_A.cpp`
* テストケースを生成するプログラムです。オプション引数で乱数のseed値を設定出来るほか、DayType等を固定することができます。
* `generator_A.lib/`
* `generator_A.cpp` で必要とされるヘッダファイルが格納されています。
* `sample_A.cpp`
* 解答サンプルコードです。

## コンパイルについて

以下のようにコンパイルし、`judge_A` と `generator_A` という名前の実行ファイルを作成します。

g++ -Isrc -std=c++17 -O2 src/generator_A.cpp -o generator_A
g++ -Isrc -std=c++17 -O2 src/judge_A.cpp -o judge_A

`make` を利用することもできます。

make

`make` を利用した場合、後述のサンプルコードも同時にコンパイルされます。

別途、解答コードを作っていただき、実行ファイルを作成します。コンパイルが必要な言語である場合はコンパイルしてください。本ツールキットには judge からの入力を読み込みつつ、常にstayを出力する `sample_A` がサンプルコードに含まれています。このサンプルコードは次のようにコンパイル出来ます。

g++ -Isrc -std=c++17 -O2 src/sample_A.cpp -o sample_A

以下では、この `sample_A` を例として説明します。

## テストケースの生成・インタラクティブ処理

次のようにしてテストケースを生成します。

./generator_A [options] > test_case.in

利用できるオプション引数は次の通りです。

* `-s --seed_number, ex) --seed=seed_number`
* 疑似乱数のシード値を指定します。`-r`と同時に指定された場合は`-r`が優先されます。デフォルト：`23587163955511535`
* `-r --random`
* 疑似乱数のシード値をシステム依存の乱数発生器から取得します。`-s`と同時に指定された場合は`-r`が優先されます。
* `-d day_type, ex) --day-type=DayType (= 0, 1, 2, 3)`
* DayType を指定します。このオプション引数が指定されない場合は、DayType はランダムに決定されます。
* `-D, --deterministic`
* 電力需給が常に予想通りの値を返すようになります。ゲリラ豪雨や予想外の晴れも生じなくなります。
* `-? --help`
* ヘルプメッセージを表示します。

生成したテストケース `test_case.in` に対して、得点計算は次のように行います。

./judge_A ./sample_A < test_case.in > test_case.result

`test_case.result` にスコアが出力されています。

### テストケースの仕様

ここでは`generator_A`が出力するテストケースの内容について説明します。

`generator_A`はまず入出力形式１の内容を出力します。ここで出力される内容はコンテスタントがジャッジから受け取る内容と同一です。

次に、`generator_A`は次のような出力を生成します。実装上の都合で注文の情報が出力され、ジャッジはこれを読み込みますが、コンテスタントには一切出力されません。

1. 注文の情報

    $N_{\rm order}^1$
    ${\rm id}^1_1 {\rm from}^1_1 {\rm to}^1_1 t$
    :
    ${\rm id}^1_{N_{\rm order}^1} {\rm from}^1_{N_{\rm order}^1} {\rm to}^1_{N_{\rm order}^1} t$
    :
    :
    $N_{\rm order}^{T_{\rm last}}$
    ${\rm id}^{T_{\rm last}}_1 {\rm from}^{T_{\rm last}}_1 {\rm to}^{T_{\rm last}}_1 t$
    :
    ${\rm id}^{T_{\rm last}}_{N_{\rm order}^1} {\rm from}^{T_{\rm last}}_{N_{\rm order}^1} {\rm to}^{T_{\rm last}}_{N_{\rm order}^1} t$

* $N_{\rm order}^t$は時刻$t$で生じる注文の数です。$0$である場合、続く注文の詳細は出力されません。
* 続く$N_{\rm order}^t$行は時刻$t$に生じた注文の詳細を表します。時刻$t$に$n$番目に生じた注文に対して、
* ${\rm id}_n^t$ は割り当てられたidです。
* ${\rm from}_n^t$ は出発地点です。
* ${\rm to}_n^t$ は到着地点です。
* $t$ は発生した時刻です。

2. ナノグリッドの電力需給

    $x_1$ ${\rm pw}^{{\rm actual}, 1}_1$ ... $x_{N_{\rm grid}}$ ${\rm pw}^{{\rm actual}, 1}_{N_{\rm grid}}$
    :
    $x_1$ ${\rm pw}^{{\rm actual}, T_{\rm last}}_1$ ... $x_{N_{\rm grid}}$ ${\rm pw}^{{\rm actual}, T_{\rm last}}_{N_{\rm grid}}$

* $t$ 行目は、時刻$t$でのナノグリッドの電力需給です。予測値に揺らぎやゲリラ豪雨、想定外の晴れといった確率的変動を加えた真の電力需給が与えられます。
* $1$行に$N_{\rm grid}$個のナノグリッドの情報が与えられます。各行は$x_i^t$ ${\rm pw_i^{{\rm actual}, t}}$の形式が$N_{\rm grid}$回繰り返されます。
* $x_i$は$i$番目のナノグリッドの位置、${\rm pw_i^{{\rm actual}, t}}$は時刻$t$での$x_i$に存在するナノグリッドの真の電力需給を表します。

## サンプルコードについて

同梱したサンプルコードはコンテストに対する解答を試験的に実装したものです。戦略の実装、変更等が容易になるよう実装されています。

サンプルコードは C++17 を使用して書かれています。

### 設計

入出力形式1でジャッジから入力される情報は`A`クラスのコンストラクタで読み取ります。`A`クラスは内部でグラフに関する情報を保持する`graph_data`クラス、ナノグリッドに関する情報を保持する`grid_data`クラス、EVに関する情報を保持する`EV_data`クラスの各インスタンスを持っており、適切なタイミングで各クラスのインスタンスに情報の読み取りを移譲します。

入出力形式2でジャッジから入力される情報は、ナノグリッドに関するターン毎の情報を扱う`grid_info`クラス、EVに関するターン毎の情報を扱う`EV_info`クラス、注文に関するターンごとの情報を扱う`order_info`クラスがそれぞれ読み取ります。

入出力形式2でジャッジに出力する各EVへの`<command>`は、`strategy`クラス内部で保持している`command_queue`の先頭から取り出して渡します。

`command_queue` への `<command>` の挿入は `command` メンバ関数を利用して行います。ユーザーは`strategy`クラスを継承し、`command`メンバ関数をオーバライドすることで、独自の戦略を実装することが出来ます。実装したクラスは`str`シェアードポインタ変数にインスタンスを代入することで、実際に動作させることが出来ます。

以下に独自の戦略を実装する際に重要と思われる関数・クラスの説明を列挙します。全ては書ききれませんので、説明に無い関数・クラスの詳細についてはソースコードから読み取ってください。

#### メンバ関数 `strategy::command`

void strategy::command(const grid_info&, const EV_info& , const order_info&);

* 戦略を実装する上で中核となる関数です。各ターン毎に呼ばれ、ターン毎の情報が渡されるので、それを下に新しく`command_queue` に積む `<command>`を決定してください。実装上の都合で`order_info`を要求しますが、この内容を読みこんではいけません。

#### メンバ関数 `strategy::enqueue`

void strategy::enqueue(size_t EV_index, const string& cmd);

* `<command>` のキューイングに使用します。`EV_index`で指定したEVの`command_queue`に`cmd`を挿入します。
* `cmd`の末尾に改行は不要です。
* `EV_index` は 0-index であることに注意してください。

void enqueue(size_t EV_index, const string& cmd, size_t repeat)

* `<command>` のキューイングに使用します。`repeat` で指定した回数だけ、`EV_index`で指定したEVの`command_queue`に`cmd`を挿入します。
* `move XXX`、`charge_from_grid XXX`、`charge_to_grid XXX`など、連続して行う`<command>`が多いため用意しました。

void enqueue(size_t EV_index, list<string>&& cmd_list)

* `<command>` のキューイングに使用します。`EV_index`で指定したEVの`command_queue`に`cmd_list`の内容をまとめて挿入します。
* より複雑な処理をまとめてキューイングするために用意した関数です。後述の`move_to`と組み合わせると便利かと思います。

#### メンバ関数 `bool strategy::is_free`

bool strategy::is_free(size_t EV_index);

* 各EVのキューの状態を調べます。`EV_index`で指定したEVの`command_queue`が空であれば`true`を、そうでなければ`false`を返します。
* 現在遂行中の仕事の無いEVを調べることが出来ます。

#### クラス`graph_summary`

struct graph_summary {
    vector<vector<size_t>> len;
    vector<vector<size_t>> next;
    vector<size_t> nanogrid_pos;
    size_t diameter = 0;
    size_t cover_radius = 0;

    graph_summary(const graph_data& graph, const grid_data& grid);
};

* グラフに関する要約情報を保持します。
* コンストラクタでWarshall–Floyd法が走り、以下の情報を取得します：
* `len`: 点Aから点Bへの最短経路長を`len[A][B]`で取得出来ます。
* `next`: 点Aから点Bへ最短経路で向かう場合、次に進むべき点を`next[A][B]`で取得出来ます。実際にどう使うかは`move_EV`の実装が参考になるかと思います。
* `nanogrid_pos`: 各ナノグリッドが存在する頂点番号です。
* `diameter`: グラフの直径(=グラフ上の2点間の最短経路長の内、最大のもの)です。言い換えると、任意の現在地Aから任意の目的地Bまでの最短経路長は、どんなに長くても`diameter`を越えることはありません。
* `cover_radius`: 最寄りのナノグリッドへの最短経路長のうち、最長のものをです。言い換えると、グラフ上の任意の位置から最寄りのナノグリッドへ移動しようとしたとき、その最短経路長は`diameter`を越えません。

#### クラス `struct action`

struct action : std::list<std::string> {};

* 複雑な動作に対する`<command>`生成を隠蔽するためのプレースホルダです。

#### クラス `struct move_EV`

struct move_EV : action {
    move_EV(size_t current, size_t goal, const graph_summary& gs);
    move_EV(size_t current, const std::vector<size_t>& path, const graph_summary& gs);
};

* 複雑な移動の`<command>`生成を隠蔽するためクラスです。

move_EV::move_EV(size_t current, size_t goal, const graph_summary& gs);

* `current`から`goal`までの移動を最短経路で行うための`<command>`列を生成します。

move_EV::move_EV(size_t current, const std::vector<size_t>& path, const graph_summary& gs);

* `current`から出発して`path`で指定された頂点を順に最短経路で巡るための`<command>`列を生成します。

### サンプルコードで実装済みの戦略

1. `all_stay`
* 常に`stay`を出力します。
* 問題A、問題B共用です。
2. `random_walk`
* 各EVはノードに到達するごとに最寄りのナノグリッドから50ターン分の電力を充電します。
* 充電が完了したEVはランダムに行き先を決定し、行動キューに設定します。
* 上記の行動を繰り返します。
* 問題A、問題B共用です。
3. `transport_only_0`
* 各EVは以下の戦略を取ります。
1. 現在地がナノグリッドではない場合、EVは最寄りのナノグリッドへ移動します。
2. EVの電力残量が危険域である場合、EVは危険域を脱するように充電します。
3. EVが割り当てられていない運搬物がある場合、EVはID順に最大4つの運搬物を運搬します。運搬ルートに対して充電量が十分でない場合、十分量の充電を行ってから出発します。
* 実際の運搬ルートは貪欲法で決定されます。
* 問題B専用です。

## 謝辞

* 本ツールキットに含まれる `testlib.hpp` は `https://github.com/MikeMirzayanov/testlib` にてMITライセンスで公開されているコードを本ツールキットに合わせて修正したものです。
* 本ツールキットに含まれる `cmdline.h` は `https://github.com/tanakh/cmdline` にて修正BSDライセンスで公開されているコードを本ツールキットに合わせて修正したものです。
* サンプルコードはMITライセンスをもとに公開されています。