問題概要

• 問題のねらい: 本プログラミングコンテストは、買い物支援(配達)サービスの最適化をテーマとしている。本サービスを利用する顧客はそれぞれ異なる品物をお店に注文する（顧客からの注文には固有の$\\text{ID}$が割り振られる）。お店が利用できる車は一台のため、配達中に注文された商品については、お店に戻ってその商品を車に積んでから、顧客のもと商品を届けなければならない。
• 得点: 最適化の目的は、制限時間 $T_{\\max}$ の間に「できるだけ多くの」商品を「できるだけ早く」顧客に届けることである。なお、注文は時刻 $0$ から時刻 $0.95 \\times T_{\\max}$ の間に発生する可能性がある。
• 諸制約: 本コンテストでは、車に積むことのできる商品の数に制限はない。ただし、ある注文に対応する商品をお店まで取りに行き、車に積めるのは、その商品が注文された以降の時刻に限る ことに注意せよ。
• 問題 A: この問題においては、注文が発生する時刻及び、注文がどの頂点で発生したかなど、注文に関する情報が事前に与えられる。
• 問題 B: この問題においては、事前に注文に関する情報は与えられず、全ての注文は配達中にオンラインで発生する。

時間・空間について

• 時間: $t$ は $0 \\leq t < T_{\\max}$ を満たす整数時刻であるとし、各 $t$ において、あなたは時刻 $t$ から $t+1$ にかけての行動を決定しなければならない。
• 空間: 単純かつ無向であるグラフ $G = (V, E)$ を考える。ここで $V$ は頂点集合、$E$ は辺集合である。車の移動・注文の発生はすべて、このグラフ内で起こるものとする。
• 店および顧客の位置: それぞれの頂点 $u \\in V$ は $1$ から $|V|$ までで番号付けられている。頂点 $u = 1$ は店がある頂点であるとし、$u = 2, \\dots, |V|$ は顧客がいる頂点であるとする。
• 道路: それぞれの辺 $\\left\\{ u, v \\right\\}$ は、頂点 $u$ と頂点 $v$ を直接結ぶ道路であるとする。辺には整数距離が定められており、これを $d_{u, v} \\geq 1$ と表記する。
• グラフの生成方法: 地図を表すグラフは、後述のアルゴリズムによってランダムに生成される。

グラフ $G$ の生成について すべてのテストケースにおいて、与えられるグラフ $G = (V, E)$ は以下のアルゴリズムによって生成される。

• 入力:$|V|$, $|E|$, $\\mathrm{MaxDegree}=5$(最大次数)
• 頂点(店舗＋顧客)の生成方法:
  • はじめに、$|V| = R^{2} + r$ を満たす最大の非負整数$R$ を見つける（ただし、$r$ も非負整数とする）。
  • 次に、$0 \\leq x, y < R$ を満たす$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|$までの番号をランダムに割り振る。番号$1$を割り振られた頂点を店舗とする。
• 高速道路の作成方法:
  • 頂点間をつなぐ道路のうち、まず高速道路を作成する。生成した頂点集合 $u \\in V$ に対して、完全グラフ $G_{\\text{comp}}$ を生成する。各頂点ペア $u, v \\in V \\times V$ に対する頂点間のユークリッド距離を、完全グラフにおける辺の重み $W_{u, v}$ と定める。
  • 次に、完全グラフ $G_{\\text{comp}}$ に対して、最小全域木 を生成する。最小全域木の $|V|-1$ 本の辺がグラフ $G$ の高速道路網となる。これらの辺の重み $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 4 \\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$ に注文頻度 $f_u \\in \\left\\{0,1,2\\right\\}$ を割り当てる。
  • 店舗の注文頻度を$0$に初期化する: $f_1 \\leftarrow 0$.
  • 顧客の注文頻度を$1$に初期化する: $f_u \\leftarrow 1$
  • 以下、注文頻度$2$の顧客を定める。そのためにまず、座標平面上の \[R/4,3R/4\]\\times\[R/4,3R/4\] の領域内に一様ランダムに1点、中心点 $c=(c_x,c_y)$ をプロットする（c=(c_x,c_y)\\in \[R/4,3R/4\]\\times\[R/4,3R/4\]）。次に全ての顧客 $u=2,...,|V|$ に対して以下の処理を行う:
    • $\\mathrm{EuclideanDistance}(c,u)\\le R/8 + \\mathrm{uniformRandom}\[0,R/8\]$ の場合、 $f_{u} \\leftarrow 2$ とする。

車の位置と移動について

配達には車を利用する必要がある。車の位置は次に示すように二種類に分類される。

• 車の位置: 以下の二種類に分類される。
  • 頂点 $u \\in V$ 上にいる場合
  • 辺 $\\left\\{ u, v \\right\\}$ 上にいる場合。より具体的に言えば、$u$ から $v$ の方向に $x$ $(0 < x < d_{u, v})$ だけ離れている場合である

また、毎時刻 $t$ において、あなたは以下に示すとおりに車を操作できる。

• 車の移動: あなたが取れる行動は以下の二種類である。

  • stay: 移動せずその場にとどまる
  • move w: $w \\in V$ の方向に向かって距離 $1$ だけ進む

  move w を選択するとき、$w$ は以下の条件を満たさなければならない。これらの条件を満たさない場合は WA (Wrong Answer) となることに注意せよ。

  • $w$ は $w \\in V$ を満たす頂点である
  • 車が頂点 $u \\in V$ 上にいる場合、頂点対 $\\left\\{ u, w \\right\\}$ がグラフの辺集合に含まれていなければならない。すなわち、$\\left\\{ u, w \\right\\} \\in E$ でなければならない
  • 車が辺 $\\left\\{ u, v \\right\\}$ 上にいる場合、$w = u$ または $w = v$ でなければならない

注文・配達等について

• 注文: それぞれの注文は「注文 ID」「配達先 $v \\in V$」「注文が発生した時刻 $t$」の三種類の情報を持つ。詳しくは、後述の入力フォーマットを参照のこと。
• 注文発生について: 顧客からの新しい注文は、$0 \\leq t \\leq T_{\\mathrm{last}} = 0.95 \\times T_{\\max}$ を満たす時刻 $t$ において確率 $p_{\\mathrm{order}}(t)$ で発生する。それぞれの頂点には注文頻度 $f_i$ が定められており、注文が発生するときにその配送先が頂点 $i$ となる確率は $\\frac{f_i}{\\sum_{k} f_k}$ である。詳しくは以下の疑似コードまたはサンプルコードを参考のこと。

注文発生について

• 入力: 注文が発生しうる時刻の最大値 $T_{\\mathrm{last}}$ と、時刻ごとの注文発生確率を表す関数 $p_{\\mathrm{order}}(t)$.

• 初期化: $\\mathrm{ID} \\leftarrow 0$

• 各時間ステップ $t = 0, ..., T_{\\mathrm{last}}$ で以下を実行する:

  • 実数 r \\in \\left\[ 0,1 \\right\] を一様ランダムに生成する
  • $r \\le p_{\\mathrm{order}}(t)$ の場合:
    • 1つの頂点 $u$ ($u \\in V, u \\neq 1$) を、それぞれの頂点に割り当てられた頻度 $f_{u}$ で重み付けをしてランダムに選択する
    • $\\mathrm{ID} \\leftarrow \\mathrm{ID} + 1$
    • 注文を発生させる。ここで注文は(注文ID, 注文時間 $t$, (お届け先の)頂点番号 $u \\in V$)を含む。
  • 上記以外 ( $r \\gt p_{\\mathrm{order}}(t)$) の場合: 注文は発生しない

• 時刻ごとの注文発生確率を表す関数 $p_{\\mathrm{order}}(t)$ を下記のように定める:

• $p_{\\text{order}}(t) = \\begin{cases} t / T_{\\text{peak}}, & \\text{if } 0\\le t \\lt T_{\\text{peak}}, \\\\ (T_{\\text{last}} - t) / (T_{\\text{last}}- T_{\\text{peak}}), & \\text{if } T_{\\text{peak}} \\le t \\lt T_{\\text{last}}, \\\\ 0, & \\text{if } T_{\\text{last}} \\le t, \\end{cases}$

• ここで $T_{\\text{last}}:=0.95 \\times T_{\\max}$ であり、 $T_{\\text{peak}}$ は区間 \[0, T_{\\text{last}}\] から一様ランダムに定める

• 注意: $T_{\\text{peak}}$ の値は、入力では与えられない。