AT_hokudai_hitachi2020_a hokudai_hitachi2020_a
Description
[problemUrl]: https://atcoder.jp/contests/hokudai-hitachi2020/tasks/hokudai_hitachi2020_a
Input Format
N/A
Output Format
N/A
Explanation/Hint
### 目次
[ 問題概要 ](#gaiyou)
[ タイムスケジュールと空間構造 ](#time-space)
[ ナノグリッド ](#nanogrid)
[ 電力需給 ](#yojou)
[ EV ](#ev)
[ ナノグリッドの蓄電池の充放電処理 ](#charge)
[ 採点方法 ](#scoring)
[ 問題文 A ](#problem)
[ 入出力形式1 ](#io-format1)
[ 入出力形式2 ](#io-format2)
[ 入出力形式3 ](#io-format3)
[ 入出力制約 ](#constraints)
[ 入出力例 ](#example)
[ サンプルコード A ](#sample)
問題概要
------
この問題では、点在するナノグリッド(発電、蓄電、消費が行われる)における電力が不足しないよう、複数台のEV(=電気自動車)を用いて蓄電量のバランスを保つことを考える。EVは走行距離に応じて電気を消費するため、ナノグリッドから充電する必要がある。ナノグリッドでは太陽光や燃料エンジンによる発電、電力の消費およびEVへの充電が行われており、それらにより時間変動する電力需給を蓄電池の充放電および必要があれば外部からの電力供給によりバランスしている。
本ページ下部からダウンロード可能なtoolkitには、ジャッジからのデータ読込などI/O周りを既に実装したサンプルコードを用意しています。また、EVの動作も"all stay", "random walk"をサンプルとして実装済です。新しいアルゴリズムを実装する際も、strategy classを継承する形でEVの動作の記述に注力できるつくりになっています(詳しくはREADME.mdもご参照ください)。投稿の際、こちらをご活用いただいて構いません。
タイムスケジュールと空間構造
----------------
- **タイムスケジュール**: 1つのテストケースは $ 1 $ 営業日分に相当する。時刻 $ t $ は $ 0 $ から $ T_{\max} $ までの整数の値をとる。各テストケースで天候が $ 4 $ パターンのいずれかから $ 1 $ つランダムに割り当てられ、電力需給に影響を及ぼす。コンテスタントはテストケース開始時に全時刻分の予測電力需給の情報を受け取る。また各時刻 $ t $ において、各ナノグリッドの蓄電量と、前時刻 $ t-1 $ における実際の電力需給、余剰で捨てた電力、外部からの供給電力を受け取る。これらの情報を基に、コンテスタントは時刻 $ t $ から $ t+1 $ の間に実行するEVの動作(移動、充放電など) を決定する。
- **空間構造**: 単純かつ無向であるグラフ $ G\ =\ (V,\ E) $ を考える。ここで $ V $ は頂点集合、$ E $ は辺集合である。EVの移動や充放電は全てこのグラフ内で行われる。頂点のうち一定数はナノグリッドに対応する。また、辺は道路に対応し、各辺には正の整数で重み(距離)が定められている。地図を表すグラフは、後述のアルゴリズムによってランダムに生成される。
グラフ $ G $ の生成について 全てのテストケースにおいてグラフ $ G\ =\ (V,\ E) $ は以下のアルゴリズムによって生成される。 - **入力:**$ |V| $, $ |E| $, $ \mathrm{MaxDegree}=5 $(最大次数)
- **頂点の生成方法:**
- はじめに、$ |V|\ =\ R^{2}\ +\ r $ を満たす最大の非負整数$ R $ を見つける（ただし、$ r $ も非負整数とする）。
- 次に、$ 0\ \leq\ x,\ y\ を満たすxy $座標平面上の全ての格子点に対して、点 $ (x,\ y) $ をプロットする。
- 各点の座標を $ (x,\ y)\ \leftarrow\ (x\ +\ dx,\ y\ +\ dy) $ とずらす。ここで $ dx,\ dy $ は $ dx,\ dy\ \in\ [0,\ 1] $ を満たす一様ランダムな実数である。つまり、移動後の座標は$ (x\ +\ dx,\ y\ +\ dy)\in\ [0,R]\ \times\ [0,R] $を満たす。
- 残りの $ r $ 個の点それぞれについて、座標 $ (x',\ y') $ ($ 0\ \leq\ x',\ y'\ \leq\ R $ の一様ランダムな実数) を定めてプロットする。
- 各点に対して、$ 1 $から$ |V| $までの番号(ID)をランダムに割り振る。
- **連結性の保証:**
- 生成した頂点集合 $ u\ \in\ V $ に対して、完全グラフ $ G_{\text{comp}} $ を生成する。各頂点ペア $ u,\ v\ \in\ V\ \times\ V $ に対する頂点間のユークリッド距離を、完全グラフにおける辺の重み $ W_{u,\ v} $ と定める。
- 次に、完全グラフ $ G_{\text{comp}} $ に対して、[最小全域木](https://ja.wikipedia.org/wiki/%E5%85%A8%E5%9F%9F%E6%9C%A8#%E6%9C%80%E5%B0%8F%E5%85%A8%E5%9F%9F%E6%9C%A8) を生成し、生成された $ |V|-1 $ 本の辺を道路とする。これらの辺の重み $ d_{u,v} $ を $ d_{u,v}\ \leftarrow\ \lceil\ 2\ \times\ W_{u,\ v}\ \rceil $と定める。
- **残りの道路の作成方法:**
- 残りの $ |E|-(|V|-1) $ 本の道路は、次の手順で$ 1 $本ずつ生成される。
- $ \mathrm{cost}(u,v) $を更新する。
- グラフGの辺でつながっていない$ u $, $ v $のペアの内、$ \mathrm{cost(u,v)} $の最小を与えるペアをつなぐ辺$ \left\{\ u,\ v\ \right\} $をグラフGに加える。
- 選ばれた辺の重み $ d_{u,v} $ を $ d_{u,v}\ \leftarrow\ \lceil\ 2\ \times\ W_{u,\ v}\ \rceil $ と定める。
- ここで $ \mathrm{cost}(u,v) $ のベースは頂点間のユークリッド距離だが、低い次数の頂点が選ばれやすくなるように、また、できる限り道の交差を避けるため、斜め方向よりも縦横方向の道が選ばれやすくなるように $ \mathrm{cost}(u,v) $ を定める。以下に $ \mathrm{cost}(u,v) $ の計算方法の詳細を示す。
- 各頂点 $ u\in\ V $ の次数 $ \mathrm{degree}(u) $ を計算する。次数 $ \mathrm{degree}(u) $ は $ u\in\ V $ をいずれかの端点に含むグラフ $ G $ の辺の本数である。
- 各頂点 $ u\in\ V $ の色を、頂点の初めの(ずらす前の)座標 $ (x,y) $ をもとに、下記のように定める。まずは $ |V| $ 個の頂点のうち、$ R^{2} $ 個の頂点に対し、
- $ x+y $ が偶数の場合 : $ \mathrm{color}(u)\ =\ 0 $
- $ x+y $ が奇数の場合 : $ \mathrm{color}(u)\ =\ 1 $
- と定める。残りの $ r $ 個の頂点には、ランダムに$ 0 $もしくは$ 1 $の色を割り当てる。
- ファクター $ f(u,v) $ を以下のように定める:
- $ \mathrm{color}(u) $ と $ \mathrm{color}(v) $ が同じ場合： $ \mathrm{f}(u,v)\ =\ 5 $
- $ \mathrm{color}(u) $ と $ \mathrm{color}(v) $ が異なる場合： $ \mathrm{f}(u,v)\ =\ 1 $
- ファクター $ g(u) $ を以下のように定める:
- $ \mathrm{degree}(u)\ \lt\ \mathrm{MaxDegree} $ の場合: $ g(u)=1 $
- $ \mathrm{degree}(u)\ \geq\ \mathrm{MaxDegree} $ の場合: $ g(u)=\infty $
- $ \mathrm{cost}(u,v) $ を以下のように計算する。：
- $ \mathrm{cost}(u,v)\ =\ W_{u,v}\times\ \mathrm{degree}(u)\ \times\ \mathrm{degree}(v)\ \times\ f(u,v)\ \times\ g(u)\ \times\ g(v) $.
- **ナノグリッド頂点の選択方法:**
- 頂点集合 $ u\ \in\ V $ の中から一様ランダムに $ N_{\mathrm{grid}} $ 個の頂点を選択し、それらをナノグリッド頂点と定める。またナノグリッド頂点集合を $ V_{\mathrm{grid}} $ と表す。
ナノグリッド
--------
ナノグリッドは発電設備、電力消費者、EVの充放電設備および蓄電池から構成され、以下の内部状態を持つ。
- **頂点ID**: 頂点 $ u $ のID. ただし、$ u\ \in\ V_{\mathrm{grid}} $ ($ V_{\mathrm{grid}} $: ナノグリッド頂点集合, ("グラフ$ G $ の生成について"を参照))
- **蓄電量**: ナノグリッド内の蓄電池に蓄えられた電気の量。初期値 $ C_{\mathrm{init}}^{\mathrm{grid}} $。上限値 $ C_{\mathrm{max}}^{\mathrm{grid}} $ (初期値と上限値は全ナノグリッド共通)。各時刻 $ t $ で電力需給(=発電-消費)の値だけ増減する。また、EVと蓄電池の間の充放電によっても増減する(詳細は**[ ナノグリッドの蓄電池の充放電処理 ](#charge)**参照)。増加分が上限値 $ C_{\mathrm{max}}^{\mathrm{grid}} $ を超える場合、次の時刻 $ t+1 $ の蓄電量は上限値となり、超えた分の電気は捨てられる。逆に蓄電量が足りなくなった場合、不足分はナノグリッドの外部(系統電力)から供給され、不足分に比例してスコアは減点される(詳細は**[採点方法](#scoring)**参照)。
- **電力需給**: 各時刻におけるナノグリッド内の発電量とEVへの充電及び蓄電池への蓄電量を除いた消費量の差であり、その各時刻における予測値が時系列データで各テストケース開始時にコンテスタントに与えられる。実際の電力状態はその予測値と確率的部分（ゆらぎ、ゲリラ豪雨or想定外の晴れ）の和になる(詳細は**[電力需給](#yojou)**参照)。
- **上限充放電速度**: $ V_{\max}^{\mathrm{grid}} $. ナノグリッド内の蓄電池への充放電速度の上限値(全ナノグリッド共通)
電力需給
------
各時刻におけるナノグリッド内の発電量とEVへの充電及び蓄電池への蓄電量を除いた消費量の差である。
- **電力需給のパターン**: 1つのテストケースは $ 1 $ 営業日分($ 0\ \leq\ t\ $ x_1 $ $ y_1 $ $ \mathrm{pw}_{1}^{\mathrm{actual},t-1} $ $ \mathrm{pw}_{1}^{\mathrm{excess},t-1} $ $ \mathrm{pw}_{1}^{\mathrm{buy},t-1} $ : $ x_{N_\mathrm{grid}} $ $ y_{N_\mathrm{grid}} $ $ \mathrm{pw}_{N_\mathrm{grid}}^{\mathrm{actual},t-1} $ $ \mathrm{pw}_{N_\mathrm{grid}}^{\mathrm{excess},t-1} $ $ \mathrm{pw}_{N_\mathrm{grid}}^{\mathrm{buy},t-1} $ $ \mathrm{carinfo}_1 $ : $ \mathrm{carinfo}_{N_\mathrm{EV}} $
- 始めの $ N_\mathrm{grid} $ 行のうち $ i $ 行目は、$ x_i $ 上に存在するナノグリッドの蓄電量が $ y_i $ であり、前時刻 $ t-1 $ における実際の電力需給、余って捨てられた電気の量、電力不足で系統から購入した電気の量がそれぞれ $ \mathrm{pw}_{i}^{\mathrm{actual},t-1} $、$ \mathrm{pw}_{i}^{\mathrm{excess},t-1} $、$ \mathrm{pw}_{i}^{\mathrm{buy},t-1} $ であることを表す。ただし $ t=0 $ においては、 $ \mathrm{pw}_{i}^{\mathrm{actual},t-1} $、$ \mathrm{pw}_{i}^{\mathrm{excess},t-1} $、$ \mathrm{pw}_{i}^{\mathrm{buy},t-1} $ はいずれも $ 0 $ が表示されるものとする。
補足: $ \mathrm{pw}_{i}^{\mathrm{actual},t-1} $、$ \mathrm{pw}_{i}^{\mathrm{excess},t-1} $、$ \mathrm{pw}_{i}^{\mathrm{buy},t-1} $は、それぞれ [ ナノグリッドの蓄電池の充放電処理 ](#charge)"処理1"の $ \Delta^{\mathrm{grid}}_{\mathrm{gen},t-1} $、"処理2"の"速度や上限蓄電量を超えた分の電気"$ \Delta^{\mathrm{grid}}_{\mathrm{total},t-1}\ -\ \min\ \left\{\ V_{\max}^{\mathrm{grid}},\ C^{\mathrm{grid}}_{\max}-C^{\mathrm{grid}}_{t-1}\ \right\} $、"処理3"の"電力不足分" $ -\ \Delta^{\mathrm{grid}}_{\mathrm{total},t-1}\ -\ \min\ \left\{\ V_{\max}^{\mathrm{grid}},\ C^{\mathrm{grid}}_{t-1}\ \right\} $ に対応する。ただし、前時刻 $ t-1 $ でそれぞれ"処理2"、"処理3"が実行されなかった場合、$ \mathrm{pw}_{i}^{\mathrm{excess},t-1} $ と $ \mathrm{pw}_{i}^{\mathrm{buy},t-1} $ はそれぞれ $ 0 $ となる。
- 続く $ N_\mathrm{EV} $ 項目はそれぞれ $ 3 $ 行からなり、そのうち $ i $ 項目目の $ \mathrm{carinfo}_i $ は $ i $ 番目のEVの状態を表す。$ \mathrm{carinfo}_i $ はそれぞれ後述の形式で与えられる。
$ i $ 番目のEVの状態を表す $ \mathrm{carinfo}_i $ は、以下の形式で与えられる。
> $ \mathrm{charge}_i $ $ u_i $ $ v_i $ $ \mathrm{dist\_from}\_u_i $ $ \mathrm{dist\_to}\_v_i $ $ N_{\mathrm{adj},i} $ $ a_{i,1} $ $ a_{i,2} $ $ \ldots $ $ a_{i,N_\mathrm{adj}} $
- 始めの $ 1 $ 行目は、 $ i $ 番目のEVの蓄電量が $ \mathrm{charge}_i $ であることを表す。
- 続く $ 2 $ 行目は、 $ i $ 番目のEVの位置を表す。$ u_i\ \ne\ v_i $ ならば、$ i $ 番目のEVは頂点 $ u_i $ と 頂点$ v_i $ を結ぶ辺上に存在して頂点 $ u_i $ から $ \mathrm{dist\_from}\_u_i $、頂点 $ v_i $ から $ \mathrm{dist\_to}\_v_i $ の距離にあることを表す。$ u_i\ =\ v_i $ ならば、$ i $ 番目のEVはちょうど頂点 $ u_i $ 上にあることを表し、$ \mathrm{dist\_from}\_u_i $ と $ \mathrm{dist\_to}\_v_i $ は共に $ 0 $ が出力される。
- 続く $ 3 $ 行目は、動作`move`で $ i $ 番目のEVがその方向に移動可能な頂点が $ N_{\mathrm{adj},i} $ 個存在し、それらが頂点 $ a_{i,1} $、頂点 $ a_{i,2} $、$ \ldots $、頂点 $ a_{i,N_\mathrm{adj}} $ であることを表す。
次に、コンテスタントは、時刻 $ t $ ($ 0\ \leq\ t\ \lt\ T_{\max} $) における各EVの動作 $ \mathrm{command}_i $ $ (1\ \leq\ i\ \leq\ N_\mathrm{EV}) $ を標準出力に出力しなければならない。各動作は改行で区切られなくてはならず、また末尾に改行を出力する必要がある。
> $ \mathrm{command}_{1} $ $ \mathrm{command}_{2} $ : $ \mathrm{command}_{N_\mathrm{EV}} $
ここで、$ \mathrm{command} $ は以下の形式でなければならない。
- `stay` を行う場合、`stay` と $ 1 $ 行で出力
- `move w` を行う場合、`move w` と $ 1 $ 行で出力
- `charge_from_grid` $ \Delta^{\mathrm{grid}\ \rightarrow\ \mathrm{EV}}_{\mathrm{charge}} $ を行う場合、`charge_from_grid` $ \Delta^{\mathrm{grid}\ \rightarrow\ \mathrm{EV}}_{\mathrm{charge}} $ と $ 1 $ 行で出力
- `charge_to_grid` $ \Delta^{\mathrm{EV}\ \rightarrow\ \mathrm{grid}}_{\mathrm{charge}} $ を行う場合、`charge_to_grid` $ \Delta^{\mathrm{EV}\ \rightarrow\ \mathrm{grid}}_{\mathrm{charge}} $ と $ 1 $ 行で出力
それぞれの動作には満たすべき条件が存在する(詳細は[EV](#ev)の"動作"の節を参照のこと)。それらの条件を満たさない場合の動作は未定義である。
入出力形式3
--------
コンテスタントが時刻 $ t=T_\mathrm{max}-1 $ における各EVの動作を標準出力に出力したのち、ジャッジから時刻 $ t=T_\mathrm{max} $ におけるEVとナノグリッドの状態 $ \mathrm{info}_t $ が標準入力に与えられる（$ \mathrm{info}_t $ の形式は"入出力形式2"を参照）。引き続いて次の行にジャッジから以下の形式でスコア $ \mathrm{Score} $ が標準入力に与えられる。
> $ \mathrm{Score} $
入出力制約
-------
- 入力で与えられる数値のうち**"\[小数\]"**と記載されているものは小数で与えられ、その他のものは整数で与えられる。
#### 初期化(入出力形式1)
- $ |V|\ =\ 225 $
- $ 1.5\ |V|\ \leq\ |E|\ \leq\ 2\ |V| $
- $ 1\ \leq\ u_{i},\ v_{i}\ \leq\ |V|,\ u_i\ \ne\ v_i $ $ (1\ \leq\ i\ \leq\ |E|) $
- $ 1\ \leq\ d_i\ \leq\ \lceil\ 2\sqrt{2|V|}\ \rceil $ $ (1\ \leq\ i\ \leq\ |E|) $
- 与えられるグラフは自己ループ・多重辺が存在せず、連結であることが保証される。
- $ \mathrm{DayType}\ \in\ \left\{\ 0,\ 1,\ 2,\ 3\ \right\} $
- $ N_\mathrm{div}\ =\ 20 $
- $ N_\mathrm{pattern}\ =\ 3 $
- $ \sigma^{2}_{\mathrm{ele}}\ =\ 100 $
- $ p_{\mathrm{event}}\ \in\ \left\{\ 0.0,\ 0.1\ \right\} $ **"\[小数\]"**
- $ \Delta_{\mathrm{event}}\ =\ 1000 $
- $ -1000\ \lt\ \mathrm{pw}_{i,j}^{\mathrm{predict}}\ \lt\ 1000\ (1\ \leq\ i\ \leq\ N_\mathrm{pattern},\ 1\ \leq\ j\ \leq\ N_\mathrm{div}) $
- $ N_\mathrm{grid}\ =\ 20 $
- $ C_{\mathrm{init}}^{\mathrm{grid}}\ =\ 25000 $
- $ C_{\mathrm{max}}^{\mathrm{grid}}\ =\ 50000 $
- $ V_{\max}^{\mathrm{grid}}\ =\ 800 $
- $ 1\ \leq\ x_i\ \leq\ |V| $ $ (i\ \neq\ j $ なら $ x_i\ \neq\ x_j,\ 1\ \leq\ i\ \leq\ N_\mathrm{grid}) $
- $ 1\ \leq\ \mathrm{pattern}_i\ \leq\ N_\mathrm{pattern} $ $ (1\ \leq\ i\ \leq\ N_\mathrm{grid}) $
- $ N_{\min}^{\mathrm{EV}}\ =\ 15 $
- $ N_{\max}^{\mathrm{EV}}\ =\ 25 $
- $ N_{\min}^{\mathrm{EV}}\ \leq\ N_\mathrm{EV}\ \leq\ N_{\max}^{\mathrm{EV}} $
- $ C_{\mathrm{init}}^{\mathrm{EV}}\ =\ 12500 $
- $ C_{\mathrm{max}}^{\mathrm{EV}}\ =\ 25000 $
- $ V_{\max}^{\mathrm{EV}}\ =\ 400 $
- $ \Delta_{\mathrm{move}}^{\mathrm{EV}}\ =\ 50 $
- $ 1\ \leq\ \mathrm{pos}_i\ \leq\ |V|\ (1\ \leq\ i\ \leq\ N_\mathrm{EV}) $
- $ \gamma\ =\ 2.0 $ **"\[小数\]"**
- $ T_\mathrm{max}\ =\ 1000 $
#### 繰り返し処理(入出力形式2)
- $ 1\ \leq\ x_i\ \leq\ |V| $ $ (i\ \neq\ j $ なら $ x_i\ \neq\ x_j,\ 1\ \leq\ i\ \leq\ N_\mathrm{grid}) $
- $ 0\ \leq\ y_i\ \leq\ C_{\mathrm{max}}^{\mathrm{grid}} $ $ (1\ \leq\ i\ \leq\ N_\mathrm{grid}) $
- $ -10000\ \lt\ \mathrm{pw}_{i}^{\mathrm{actual},j}\ \lt\ 10000\ (1\ \leq\ i\ \leq\ N_\mathrm{grid},\ -1\ \leq\ j\ \leq\ T_\mathrm{max}-2) $
- $ 0\ \leq\ \mathrm{pw}_{i}^{\mathrm{excess},j}\ \lt\ 10000,\ (1\ \leq\ i\ \leq\ N_\mathrm{grid},\ -1\ \leq\ j\ \leq\ T_\mathrm{max}-2) $
- $ 0\ \leq\ \mathrm{pw}_{i}^{\mathrm{buy},j}\ \lt\ 10000,\ (1\ \leq\ i\ \leq\ N_\mathrm{grid},\ -1\ \leq\ j\ \leq\ T_\mathrm{max}-2) $
- $ 0\ \leq\ \mathrm{charge}_i\ \leq\ C_{\mathrm{max}}^{\mathrm{EV}} $ $ (1\ \leq\ i\ \leq\ N_\mathrm{EV}) $
- $ 1\ \leq\ u_i,\ v_i\ \leq\ |V| $ $ (1\ \leq\ i\ \leq\ N_\mathrm{EV}) $
- $ 0\ \leq\ \mathrm{dist\_from}\_u_i\ \leq\ \lceil\ 2\sqrt{2|V|}\ \rceil $ $ (1\ \leq\ i\ \leq\ N_\mathrm{EV}) $
- $ 0\ \leq\ \mathrm{dist\_to}\_v_i\ \leq\ \lceil\ 2\sqrt{2|V|}\ \rceil $ $ (1\ \leq\ i\ \leq\ N_\mathrm{EV}) $
- $ 1\ \leq\ N_{\mathrm{adj},i}\ \leq\ 5(\mathrm{MaxDegree}) $ $ (1\ \leq\ i\ \leq\ N_\mathrm{EV}) $
- $ 1\ \leq\ a_{i,j}\ \leq\ |V| $ $ (1\ \leq\ i\ \leq\ N_\mathrm{EV},\ 1\ \leq\ j\ \leq\ N_{\mathrm{adj},i}) $
#### スコア(入出力形式3)
- $ \mathrm{Score} $ **"\[小数\]"**
入出力例
------
注意: **この例はわかりやすさのために小さなセットで入出力を説明したものである。そのためパラメータの値は"入出力制約"に書かれた値とは異なるが、入出力のフォーマット(入出力形式1,2及び3)とEVの動作、及び"ナノグリッドの蓄電池の充放電処理"に書かれた計算方法は実際と同じである。**
時刻 ジャッジ コンテスタント 説明 ```
4 4
1 2 1
2 3 2
3 4 3
4 1 1
0
2 2 1 0 10
5 -2
-4 4
2 10 20 4
1 1
4 2
2 5 10 2 1
2
4
0.5
4
```
はじめに、ジャッジ側からデータが与えられる。
$ 1 $ 行目: 無向グラフ $ G $ は $ |V|\ =\ 4 $ 個の頂点と $ |E|\ =\ 4 $ 本の辺から構成される。
次の $ 4 $ 行 ($ 2 $ - $ 5 $ 行目) は、グラフの辺に関する情報を表す。
$ 2 $ 行目: 辺 $ 1 $ は頂点 $ 1 $ と頂点 $ 2 $ を結んでおり、長さは $ 1 $ である。
$ 3 $ 行目: 辺 $ 2 $ は頂点 $ 2 $ と頂点 $ 3 $ を結んでおり、長さは $ 2 $ である。
$ 4 $ 行目: 辺 $ 3 $ は頂点 $ 3 $ と頂点 $ 4 $ を結んでおり、長さは $ 3 $ である。
$ 5 $ 行目: 辺 $ 4 $ は頂点 $ 4 $ と頂点 $ 1 $ を結んでおり、長さは $ 1 $ である。
$ 6 $ 行目: 天候タイプは $ 0 $ "晴(ゲリラ豪雨無し)" である。
$ 7 $ 行目: 予想電力需給が一定の時間区間の数は $ 2 $ 個、ナノグリッドの需要パターンは $ 2 $ 個、電力需給のゆらぎの分散は $ 1 $ 、ゲリラ豪雨の発生確率は $ 0 $、ゲリラ豪雨発生時の電力需給の低下量は $ 10 $ である。
次の $ 2 $ 行 ($ 8 $ - $ 9 $ 行目) は、予想電力需給に関する情報を表す。
$ 8 $ 行目: 需要パターン $ 1 $ のナノグリッドの予想電力需給は $ 5 $ (時間区間 $ 1 $)、$ -2 $ (時間区間 $ 2 $)である。
$ 9 $ 行目: 需要パターン $ 2 $ のナノグリッドの予想電力需給は $ -4 $ (時間区間 $ 1 $)、$ 4 $ (時間区間 $ 2 $)である。
$ 10 $ 行目: グラフ $ G $ の頂点のうちナノグリッドがあるものは $ N_\mathrm{grid}\ =\ 2 $ 個、時刻 $ t=0 $ におけるナノグリッドの蓄電量は $ C_{\mathrm{init}}^{\mathrm{grid}}\ =\ 10 $、最大蓄電量は $ C_{\mathrm{max}}^{\mathrm{grid}}\ =\ 20 $、上限充放電速度は $ V_{\max}^{\mathrm{grid}}\ =\ 4 $ である。
$ 11 $ 行目: ナノグリッド $ 1 $ は頂点 $ 1 $ 上にあり、需要パターンは $ 1 $ である。
$ 12 $ 行目: ナノグリッド $ 2 $ は頂点 $ 4 $ 上にあり、需要パターンは $ 2 $ である。
$ 13 $ 行目: あなたが動作させることができるEVの台数は $ N_\mathrm{EV}\ =\ 2 $ 台、時刻 $ t=0 $ におけるEVの蓄電量は $ C_{\mathrm{init}}^{\mathrm{EV}}\ =\ 5 $、最大蓄電量は $ C_{\mathrm{max}}^{\mathrm{EV}}\ =\ 10 $、上限充放電速度は $ V_{\max}^{\mathrm{EV}}\ =\ 2 $ 、単位時間のEVの移動で減少する蓄電量は $ \Delta_{\mathrm{move}}^{\mathrm{EV}}\ =\ 1 $ である。
次の $ 2 $ 行 ($ 14 $ - $ 15 $ 行目) は時刻 $ t=0 $ における各EVの位置を表す。
$ 14 $ 行目: EV $ 1 $ は時刻 $ t=0 $ で頂点 $ 2 $ 上にある。
$ 15 $ 行目: EV $ 2 $ は時刻 $ t=0 $ で頂点 $ 4 $ 上にある。
$ 16 $ 行目: ナノグリッドが外部から補充した単位電気量あたりの減点は $ \gamma\ =\ 0.5 $ 点である。
$ 17 $ 行目: あなたが行動するターン数は $ T_{\max}\ =\ 4 $ である。 0 ```
1 10 0 0 0
4 10 0 0 0
5
2 2 0 0
2 1 3
5
4 4 0 0
2 1 3
```
```
move 1
charge_from_grid 2
```
次いで、ジャッジ側から時刻 $ 0 $ でのデータが与えられる。
1 行目: 頂点 1 にあるナノグリッドの時刻 $ 0 $ での蓄電量は $ 10 $ である(時刻 $ 0 $ の場合、残りの $ 3 $ つの値は必ず $ 0 $ である)。
2 行目: 頂点 4 にあるナノグリッドの時刻 $ 0 $ での蓄電量は $ 10 $ である(時刻 $ 0 $ の場合、残りの $ 3 $ つの値は必ず $ 0 $ である)。
次の $ 3 $ 行 ($ 3 $ - $ 5 $ 行目) は、EV $ 1 $ の状態を表す。
3 行目: EV $ 1 $ の時刻 $ 0 $ での蓄電量は $ 5 $ である。
4 行目: EV $ 1 $ は時刻 $ 0 $ において頂点 $ 2 $ 上に位置する。
5 行目: EV $ 1 $ が `move` コマンドでその方向に向かって移動可能な頂点は $ N_{\mathrm{adj},1}\ =\ 2 $ 個あり、頂点 $ 1 $ および頂点 $ 3 $ である。
次の $ 3 $ 行 ($ 6 $ - $ 8 $ 行目) は、EV $ 2 $ の状態を表す。
6 行目: EV $ 2 $ の時刻 $ 0 $ での蓄電量は $ 5 $ である。
7 行目: EV $ 2 $ は時刻 $ 0 $ において頂点 $ 4 $ 上に位置する。
8 行目: EV $ 2 $ が `move` コマンドでその方向に向かって移動可能な頂点は $ N_{\mathrm{adj},2}\ =\ 2 $ 個あり、頂点 $ 1 $ および頂点 $ 3 $ である。
これに対するコンテスタントの出力は以下のとおりである。
1 行目: EV $ 1 $ を頂点 $ 1 $ の方向へ移動させようとする。EV $ 1 $ の充電が $ 1 $ 消費されるが、蓄電量が $ 1 $ 以上であったため移動は成功する。頂点 $ 1 $ から頂点 $ 2 $ への辺の長さは $ 1 $ であるので、時刻 $ 1 $ に頂点 $ 2 $ へ移動することが可能である。
2 行目: EV $ 2 $ はナノグリッドから $ 2 $ だけ充電する。EV $ 2 $ はナノグリッド上にあり、充電量はEV $ 2 $ の上限充放電速度 $ 2 $ を超えない。またEV $ 2 $ の充電後の蓄電量は最大蓄電量 $ 10 $ を超えない。したがって動作条件を満たすので、時刻 $ 1 $ に充電量を $ 7 $ に増やすことが可能である。 1 ```
1 14 5 1 0
4 6 -4 0 2
4
1 1 0 0
2 2 4
7
4 4 0 0
2 1 3
```
```
stay
charge_from_grid 2
```
次いで、ジャッジ側から時刻 $ 1 $ でのデータが与えられる。
1 行目: 頂点 1 にあるナノグリッドの時刻 $ 1 $ での蓄電量は $ 14 $ であり、前時刻 $ t=0 $ における実際の電力需給、余って捨てられた電気の量、電力不足で系統から購入した電気の量がそれぞれ $ 5,\ 1,\ 0 $ である(ナノグリッドの上限充放電速度を超える分は捨てられる)。
2 行目: 頂点 4 にあるナノグリッドの時刻 $ 1 $ での蓄電量は $ 6 $ であり、前時刻 $ t=0 $ における実際の電力需給、余って捨てられた電気の量、電力不足で系統から購入した電気の量がそれぞれ $ -4,\ 0,\ 2 $ である。
次の $ 3 $ 行 ($ 3 $ - $ 5 $ 行目) は、EV $ 1 $ の状態を表す。
3 行目: EV $ 1 $ の時刻 $ 1 $ での蓄電量は $ 4 $ である。
4 行目: EV $ 1 $ は時刻 $ 1 $ において頂点 $ 1 $ 上に位置する。
5 行目: EV $ 1 $ が `move` コマンドでその方向に向かって移動可能な頂点は $ N_{\mathrm{adj},1}\ =\ 2 $ 個あり、頂点 $ 2 $ および頂点 $ 4 $ である。
次の $ 3 $ 行 ($ 6 $ - $ 8 $ 行目) は、EV $ 2 $ の状態を表す。
6 行目: EV $ 2 $ の時刻 $ 1 $ での蓄電量は $ 7 $ である。
7 行目: EV $ 2 $ は時刻 $ 1 $ において頂点 $ 4 $ 上に位置する。
8 行目: EV $ 2 $ が `move` コマンドでその方向に向かって移動可能な頂点は $ N_{\mathrm{adj},2}\ =\ 2 $ 個あり、頂点 $ 1 $ および頂点 $ 3 $ である。
これに対するコンテスタントの出力は以下のとおりである。
1 行目: EV $ 1 $ はその場にとどまる
2 行目: EV $ 2 $ はナノグリッドから $ 2 $ だけ充電する。EV $ 2 $ はナノグリッド上にあり、充電量はEV $ 2 $ の上限充放電速度 $ 2 $ を超えない。またEV $ 2 $ の充電後の蓄電量は最大蓄電量 $ 10 $ を超えない。したがって動作条件を満たすので、時刻 $ 2 $ に充電量を $ 9 $ に増やすことが可能である。 2 ```
1 18 5 1 0
4 2 -4 0 2
4
1 1 0 0
2 2 4
9
4 4 0 0
2 1 3
```
```
move 4
charge_to_grid 2
```
次いで、ジャッジ側から時刻 $ 2 $ でのデータが与えられる。
1 行目: 頂点 1 にあるナノグリッドの時刻 $ 2 $ での蓄電量は $ 18 $ であり、前時刻 $ t=1 $ における実際の電力需給、余って捨てられた電気の量、電力不足で系統から購入した電気の量がそれぞれ $ 5,\ 1,\ 0 $ である。
2 行目: 頂点 4 にあるナノグリッドの時刻 $ 2 $ での蓄電量は $ 2 $ であり、前時刻 $ t=1 $ における実際の電力需給、余って捨てられた電気の量、電力不足で系統から購入した電気の量がそれぞれ $ -4,\ 0,\ 2 $ である。
次の $ 3 $ 行 ($ 3 $ - $ 5 $ 行目) は、EV $ 1 $ の状態を表す。
3 行目: EV $ 1 $ の時刻 $ 2 $ での蓄電量は $ 4 $ である。
4 行目: EV $ 1 $ は時刻 $ 2 $ において頂点 $ 1 $ 上に位置する。
5 行目: EV $ 1 $ が `move` コマンドでその方向に向かって移動可能な頂点は $ N_{\mathrm{adj},1}\ =\ 2 $ 個あり、頂点 $ 2 $ および頂点 $ 4 $ である。
次の $ 3 $ 行 ($ 6 $ - $ 8 $ 行目) は、EV $ 2 $ の状態を表す。
6 行目: EV $ 2 $ の時刻 $ 2 $ での蓄電量は $ 9 $ である。
7 行目: EV $ 2 $ は時刻 $ 2 $ において頂点 $ 4 $ 上に位置する。
8 行目: EV $ 2 $ が `move` コマンドでその方向に向かって移動可能な頂点は $ N_{\mathrm{adj},2}\ =\ 2 $ 個あり、頂点 $ 1 $ および頂点 $ 3 $ である。
これに対するコンテスタントの出力は以下のとおりである。
1 行目: EV $ 1 $ を頂点 $ 4 $ の方向へ移動させようとする。EV $ 1 $ の充電が $ 1 $ 消費されるが、蓄電量が $ 1 $ 以上であったため移動は成功する。頂点 $ 1 $ から頂点 $ 4 $ への辺の長さは $ 1 $ であるので、時刻 $ 3 $ に頂点 $ 4 $ へ移動することが可能である。
2 行目: EV $ 2 $ はナノグリッドへ $ 2 $ だけ放電する。EV $ 2 $ はナノグリッド上にあり、放電量はEV $ 2 $ の上限充放電速度 $ 2 $ を超えない。またEV $ 2 $ の放電後の蓄電量は $ 0 $ 下回らない。したがって動作条件を満たすので、時刻 $ 3 $ に充電量は $ 7 $ に減ることになる。 3 ```
1 17 -1 0 0
4 6 3 1 0
3
4 4 0 0
2 1 3
7
4 4 0 0
2 1 3
```
```
stay
move 1
```
次いで、ジャッジ側から時刻 $ 3 $ でのデータが与えられる。
1 行目: 頂点 1 にあるナノグリッドの時刻 $ 3 $ での蓄電量は $ 17 $ であり、前時刻 $ t=2 $ における実際の電力需給、余って捨てられた電気の量、電力不足で系統から購入した電気の量がそれぞれ $ -1,\ 0,\ 0 $ である(電力需給の予測値は $ -2 $ だがゆらぎにより実際の値は $ -1 $ となった)。
2 行目: 頂点 4 にあるナノグリッドの時刻 $ 3 $ での蓄電量は $ 6 $ であり、前時刻 $ t=2 $ における実際の電力需給、余って捨てられた電気の量、電力不足で系統から購入した電気の量がそれぞれ $ 3,\ 1,\ 0 $ である。(電力需給の予測値は $ 4 $ だがゆらぎにより実際の値は $ 3 $ となった)。
次の $ 3 $ 行 ($ 3 $ - $ 5 $ 行目) は、EV $ 1 $ の状態を表す。
3 行目: EV $ 1 $ の時刻 $ 3 $ での蓄電量は $ 3 $ である。
4 行目: EV $ 1 $ は時刻 $ 3 $ において頂点 $ 4 $ 上に位置する。
5 行目: EV $ 1 $ が `move` コマンドでその方向に向かって移動可能な頂点は $ N_{\mathrm{adj},1}\ =\ 2 $ 個あり、頂点 $ 1 $ および頂点 $ 3 $ である。
次の $ 3 $ 行 ($ 6 $ - $ 8 $ 行目) は、EV $ 2 $ の状態を表す。
6 行目: EV $ 2 $ の時刻 $ 3 $ での蓄電量は $ 7 $ である。
7 行目: EV $ 2 $ は時刻 $ 3 $ において頂点 $ 4 $ 上に位置する。
8 行目: EV $ 2 $ が `move` コマンドでその方向に向かって移動可能な頂点は $ N_{\mathrm{adj},2}\ =\ 2 $ 個あり、頂点 $ 1 $ および頂点 $ 3 $ である。
これに対するコンテスタントの出力は以下のとおりである。
1 行目: EV $ 1 $ はその場にとどまる
2 行目: EV $ 2 $ を頂点 $ 1 $ の方向へ移動させようとする。EV $ 1 $ の充電が $ 1 $ 消費されるが、蓄電量が $ 1 $ 以上であったため移動は成功する。頂点 $ 4 $ から頂点 $ 1 $ への辺の長さは $ 1 $ であるので、時刻 $ 4 $ に頂点 $ 1 $ へ移動することが可能である。 4 ```
1 15 -2 0 0
4 10 5 1 0
3
4 4 0 0
2 1 3
6
1 1 0 0
2 2 4
3000032.0
```
最後に、ジャッジ側から時刻 $ 4 $ でのデータが与えられる。
1 行目: 頂点 1 にあるナノグリッドの時刻 $ 4 $ での蓄電量は $ 15 $ であり、前時刻 $ t=3 $ における実際の電力需給、余って捨てられた電気の量、電力不足で系統から購入した電気の量がそれぞれ $ -2,\ 0,\ 0 $ である。
2 行目: 頂点 4 にあるナノグリッドの時刻 $ 4 $ での蓄電量は $ 10 $ であり、前時刻 $ t=3 $ における実際の電力需給、余って捨てられた電気の量、電力不足で系統から購入した電気の量がそれぞれ $ 5,\ 1,\ 0 $ である(電力需給の予測値は $ 4 $ だがゆらぎにより実際の値は $ 5 $ となった)。
次の $ 3 $ 行 ($ 3 $ - $ 5 $ 行目) は、EV $ 1 $ の状態を表す。
3 行目: EV $ 1 $ の時刻 $ 4 $ での蓄電量は $ 3 $ である。
4 行目: EV $ 1 $ は時刻 $ 4 $ において頂点 $ 4 $ 上に位置する。
5 行目: EV $ 1 $ が `move` コマンドでその方向に向かって移動可能な頂点は $ N_{\mathrm{adj},1}\ =\ 2 $ 個あり、頂点 $ 1 $ および頂点 $ 3 $ である。
次の $ 3 $ 行 ($ 6 $ - $ 8 $ 行目) は、EV $ 2 $ の状態を表す。
6 行目: EV $ 2 $ の時刻 $ 4 $ での蓄電量は $ 6 $ である。
7 行目: EV $ 2 $ は時刻 $ 4 $ において頂点 $ 1 $ 上に位置する。
8 行目: EV $ 2 $ が `move` コマンドでその方向に向かって移動可能な頂点は $ N_{\mathrm{adj},2}\ =\ 2 $ 個あり、頂点 $ 2 $ および頂点 $ 4 $ である。
次の $ 1 $ 行 ($ 9 $ 行目) は、スコアを表す。
9 行目: スコアは $ 3000032.0 $ となる。
計算方法: EV $ 2 $ 台の最終時刻の蓄電量がそれぞれ $ 3 $、$ 6 $ であり、ナノグリッド $ 2 $ 箇所の最終時刻の蓄電量がそれぞれ $ 15 $、$ 10 $ であるため、総残電力は $ 34 $ となる。また、系統からの購入電力量が合計で $ 4 $ (頂点 $ 4 $ のナノグリッドが時刻 $ 0 $ と $ 1 $ でそれぞれ $ 2 $ ずつ購入)なので、補正を除いたスコアは $ 34-0.5\ \times\ 4=32.0 $ となる。補正も含めたスコアは $ 3000032.0 $ となる。 サンプルコード A
-----------
問題Aのツールキット一式は[ここ](https://img.atcoder.jp/hokudai-hitachi2020/01432768d288b809f469d88ea607e394.zip)からダウンロードできます。
このツールキットを用いて、手元の環境で入力サンプル(テストケース)の生成や、ジャッジの実行が可能です。また、ビギナー向けのサンプルコードも用意しています。
**小さなバグが見つかったため、ツールキットを修正しました(12/18)。**
**windowsでも利用可能なツールキットを公開しました(Cygwin,WSLで動作確認済)。合わせて英語版のREADME(short ver.)も追加しました。また、辺数の制約に関するバグの修正をしています。(12/18)**
**英語版のREADME(full ver.)を公開しました。また、日本語版のREADMEの細かな誤りを修正しました。(12/21)**
**ジャッジシステムの修正(python等投稿対応)に合わせてツールキットを修正しました。また、Pythonのサンプルコードも同梱しました。使い方はREADMEを御覧ください。(1/6)**
**ツールキットを修正しました(DEBUG\_LEVELに関する修正など)。また、サンプルコードの微修正も行いました。(1/12)**
- 入力サンプルジェネレータ
- テスター
- ビキナー向けのサンプルコード