AT_ahc043_a [AHC043A] Railway Company
题目背景
Nihonbashi Simulator は架空の国Rの鉄道会社Xを経営するターン制のシミュレーションゲームである。あなたはこのゲームの大ファンであり、高い収益を上げる会社にすることを目標としている。線路と駅を適切に建設することで、R国に住む人の通勤を手助けしつつ、Xを最高の鉄道会社に育て上げよう!
### 問題文
R国は $ N $ 行 $ N $ 列のグリッド状に分けられた区画からなる。上から $ i $ 行目 $ (0 \le i < N) $ 、左から $ j $ 列目 $ (0 \le j < N) $ の区画を $ (i,j) $ とする。各区画は更地、線路、駅のいずれかである:
- 更地
- 他の区画と接続しない。
- コストを払うことで、駅または線路を建設することができる。
- 線路
- 上下左右の更地でない区画のうち、最大2つの区画と接続する。線路は接続先に応じて6種類あり、以下の図のように番号付けられる。
- コストを払うことで、駅に置き換えることができる。
- 駅
- 上下左右の最大4つの更地でない区画と接続する。
1 2 3 4 5 6 線路の種類
R国には $ M $ 人の人が住んでいる。人 $ c $ の家は区画 $ (i_{c,s}, j_{c,s}) $ 、職場は区画 $ (i_{c,t}, j_{c,t}) $ にあり、この間を通勤している。
ゲーム開始時、鉄道会社Xは $ K $ の資金を持っており、全ての区画は更地である。ここから $ T $ ターンの間ゲームを行う。
### ゲームのすすめ方
各ターンでは、建設フェーズと集金フェーズがこの順で実行される。
#### 建設フェーズ
建設フェーズでは、線路の配置・駅の配置・待機のうち1つの行動を行う。ただし、資金が0未満になるような行動はできない。資金が0未満かどうかの判定は集金フェーズの前に行われる。
- 線路の配置: 更地の区画を1つ選び、その区画を6種類の線路のいずれか1つに変更する。資金が100減る。
- 駅の配置: 更地または線路の区画を1つ選び、その区画を駅に変更する。資金が5000減る。
- 待機: 区画の状態と資金は変化しない。
#### 集金フェーズ
R国に住む人が一斉に通勤を行う。人 $ c $ は、以下の条件を満たす区画 $ (i_p, j_p) $ , $ (i_q, j_q) $ が存在するときのみ、鉄道会社Xの鉄道を利用して料金を払う。 人 $ c $ が鉄道を利用したとき、鉄道会社Xの資金が $ |i_{c,s} - i_{c,t}| + |j_{c, s} - j _{c, t} | $ 増える。
- 区画 $ (i_p, j_p), (i_q, j_q) $ は駅である。
- 区画 $ (i_p, j_p) $ から、 $ 0 $ 個以上の互いに接続された駅の区画または線路の区画を経由して、 $ (i_q, j_q) $ に到達できる。
- $ | i_{c,s} - i_p| + | j_{c,s} - j_p| \leq 2 $
- $ | i_{c,t} - i_q| + | j_{c,t} - j_q| \leq 2 $
$ T $ ターン終了時点での資金ができるだけ大きくなるように行動を決めよ。
题目描述
[problemUrl]: https://atcoder.jp/contests/ahc043/tasks/ahc043_a
Nihonbashi Simulator 是一款以虚构国家 R 的铁路公司 X 为经营对象的回合制模拟游戏。你是这款游戏的忠实粉丝，目标是将公司经营得利润丰厚。通过合理建设铁路和车站，帮助 R 国居民通勤，将 X 培养成最棒的铁路公司吧！
R 国被划分为 $N$ 行 $N$ 列的网格区域。第 $i$ 行（$0 \leq i < N$）和第 $j$ 列（$0 \leq j < N$）的区域记作 $(i, j)$。每个区域可以是空地、铁路或车站之一：
- 空地
- 不与其他区域相连。
- 可以支付费用建设车站或铁路。
- 铁路
- 最多与上下左右的非空地区域中的 2 个区域相连。根据连接方式有 6 种类型，编号如下图所示。
- 可以支付费用将其替换为车站。
- 车站
- 最多与上下左右的 4 个非空地区域相连。
R 国有 $M$ 名居民。第 $c$ 个人的家在 $(i_{c,s}, j_{c,s})$，工作地点在 $(i_{c,t}, j_{c,t})$，他们需要在两地通勤。
游戏开始时，铁路公司 X 拥有 $K$ 资金，所有区域均为空地。游戏共进行 $T$ 回合。
## 游戏流程
每回合依次执行建设阶段和收款阶段。
### 建设阶段
在建设阶段，你可以选择以下三种操作之一：铺设铁路、建设车站或等待。不能进行导致资金为负的操作（在收款阶段前判断）。
- 铺设铁路：选择一个空地，将其变为 6 种铁路之一。资金减少 100。
- 建设车站：选择一个空地或铁路，将其变为车站。资金减少 5000。
- 等待：区域和资金均不变。
### 收款阶段
R 国居民同时进行通勤。对于第 $c$ 个人，若存在区域 $(i_p, j_p)$ 和 $(i_q, j_q)$ 满足以下条件，则他会使用铁路公司 X 的铁路并支付费用。每当居民使用铁路时，公司资金增加 $|i_{c,s} - i_{c,t}| + |j_{c,s} - j_{c,t}|$。
- 区域 $(i_p, j_p)$ 和 $(i_q, j_q)$ 均为车站。
- 从 $(i_p, j_p)$ 出发，经过若干相连的车站或铁路（可为 0 个），可以到达 $(i_q, j_q)$。
- $|i_{c,s} - i_p| + |j_{c,s} - j_p| \leq 2$
- $|i_{c,t} - i_q| + |j_{c,t} - j_q| \leq 2$
请在 $T$ 回合结束时，使资金尽可能多。
#
输入格式
输入通过标准输入给出，格式如下：
```
N M K T
i_{0, s} j_{0, s} i_{0, t} j_{0, t}
i_{1, s} j_{1, s} i_{1, t} j_{1, t}
⋮
i_{M-1, s} j_{M-1, s} i_{M-1, t} j_{M-1, t}
```
- 第 1 行为 4 个整数 $N, M, K, T$，以空格分隔。
- $N$：区域的行数和列数，$N = 50$。
- $M$：R 国居民人数，$50 \leq M \leq 1600$。
- $K$：铁路公司 X 的初始资金，$11000 \leq K \leq 20000$。
- $T$：游戏回合数，$T = 800$。
- 接下来的 $M$ 行，每行 4 个整数，描述居民的通勤信息。第 $c$ 个人的家在 $(i_{c,s}, j_{c,s})$，工作在 $(i_{c,t}, j_{c,t})$。$0 \leq i_{c,s}, i_{c,t} < N, 0 \leq j_{c,s}, j_{c,t} < N, |i_{c,s} - i_{c,t}| + |j_{c,s} - j_{c,t}| > 4$。
#
输出格式
请输出 $T$ 行，每行描述第 $t$ 回合建设阶段的操作，格式如下：
- 铺设铁路
在区域 $(i, j)$ 建设类型为 $p$ 的铁路时，输出：`p i j`（以空格分隔）。铁路类型编号见题面说明。
- 建设车站
在区域 $(i, j)$ 建设车站时，输出：`0 i j`。
- 等待
输出 `-1`。
#
说明/提示
### 得分
每个测试用例，$T$ 回合结束时的资金为**绝对得分**，相对评价得分为 $\text{round}(10^9 \times \left(\frac{\text{自身绝对得分}}{\text{全体参赛者最大绝对得分}}\right))$，所有测试用例的相对得分之和为最终得分。若某测试用例全体参赛者最大绝对得分为 $0$，则 AC 的所有参赛者该测试用例得分为 $10^9$。
若输出不合法，判为 WA，包括：
- 在已有车站或铁路的区域铺设铁路
- 在已有车站的区域建设车站
- 资金为负的操作
- 铁路类型或区域指定不合法
- 输出操作数不是 $T$ 行
最终排名以系统测试（2000 个测试用例）得分为准，仅以最后一次非 CE 提交为准。
### 输入生成方法
- $M = \mathrm{round}(50 \times 2^{\mathrm{rand\_double}(0,5)})$
- 居民家和工作地点的坐标通过混合高斯分布生成，具体见原文。
- $K = \mathrm{rand}(\max(10, d) \times 100, 2 \times N \times 100) + 10000$，$d$ 为所有居民家与工作地点曼哈顿距离的最小值。
### 其它说明
- 可在输出中包含以 `#` 开头的注释行，评测时会忽略。
- 参见题面提供的样例程序和可视化工具。
# 输入格式
```
N M K T
i_{0, s} j_{0, s} i_{0, t} j_{0, t}
i_{1, s} j_{1, s} i_{1, t} j_{1, t}
⋮
i_{M-1, s} j_{M-1, s} i_{M-1, t} j_{M-1, t}
```
- 第 1 行：4 个整数 $N, M, K, T$，以空格分隔。
- 接下来的 $M$ 行：每行 4 个整数，描述第 $c$ 个人的家和工作地点坐标。
# 输出格式
输出 $T$ 行，每行描述第 $t$ 回合的操作：
- 铺设铁路：`p i j`（$p$ 为铁路类型编号，$i, j$ 为坐标）
- 建设车站：`0 i j`
- 等待：`-1`
# 提示
- 题目为模拟与优化题，目标是最大化 $T$ 回合结束时的资金。
- 具体铁路类型编号、连接规则、输入生成方法等详见题面说明。
- 可在输出中添加注释行，评测时会忽略。
- 参见题面提供的样例程序与可视化工具。
由 ChatGPT 4.1 翻译