← 返回题目列表

AtCoder · ahc043_a

A. 铁路公司

中文机器翻译题面 查看原题

故事

日本桥模拟器是一款回合制模拟游戏,您在虚构的国家 R 中管理铁路公司 X。作为这款游戏的忠实粉丝,您的目标是让该公司获得高额利润。通过合理建设铁路和车站,帮助R国人民的通勤,同时将X发展成为最好的铁路公司!

问题陈述

国家 R 由排列在一个 N \times N 网格。该部分在 i从顶部算起的第行 (0 \le i < N),以及 j左起第 列 (0 \le j < N) 表示为 (i,j)。 每个部分可以是空的、铁路的或车站的:

  • 空
    • 不连接到其他部分。
    • 可以通过支付费用更改为车站或铁路。
  • 铁路
    • 最多连接到上、下、左、右两个相邻的非空部分。导轨有六种类型,根据其连接方式编号如下图所示。
    • 可以通过支付费用来更改电台。
  • 站
    • 最多连接到上、下、左、右四个相邻的非空部分。

1 2 3 4 5 6 导轨类型

有 M 居住在 R 国的人。人的家 c 位于部分 (i_{c,s}, j_{c,s}),工作场所位于部分 (i_{c,t}, j_{c,t}),他/她在其之间通勤。

游戏开始时,铁路公司 X 有钱 K,所有部分都是空的。比赛将继续进行 T 转。

游戏进展如何

每回合都由构建阶段和收集阶段组成。

施工阶段

在构建阶段,执行以下操作之一:放置铁轨、放置车站或等待。不允许采取导致资金低于零的行为。 检查资金是否低于零是在收集阶段之前执行的。

  • 放置导轨:选择一个空部分并将其更改为六种导轨之一。金钱减少 100。
  • 放置车站:选择一个空的或铁路部分并将其更改为车站。金钱减少了5000。
  • 等待:部分的状态和金钱没有改变。

收集阶段

居住在 R 国的人们同时通勤。人 c 仅当存在路段时才会乘坐火车并向铁路公司 X 支付票价 (i_p, j_p) 和 (i_q, j_q) 满足以下条件:

  • 部分 (i_p, j_p), (i_q, j_q) 是电台。
  • 可以到达部分 (i_q, j_q) 来自部分 (i_p, j_p) 通过零个或多个连接的车站或铁路段。
  • | i_{c,s} - i_p| + | j_{c,s} - j_p| \leq 2
  • | i_{c,t} - i_q| + | j_{c,t} - j_q| \leq 2

当人 c 使用火车,铁路公司X的钱增加 |i_{c,s} - i_{c,t}| + |j_{c,s} - j_{c,t}|.


请确定在回合结束时最大化金钱的行动 T.


评分

对于每个测试用例,获得的绝对分数是最后的金钱价值 T 转动,我们计算 相对分数 \mathrm{round}(10^9\times \frac{\mathrm{YOUR}}{\mathrm{MAX}}),其中 YOUR 是您的绝对分数,MAX 是在该测试用例中获得的所有竞争对手中的最大绝对分数。提交的分数是相对分数的总和。 在 MAX 的测试用例中 0,所有收到的参与者的相对分数 AC 将是 分别为 10^9.

如果产生以下无效输出,则判断为 WA。

  • 将轨道放入车站或轨道部分
  • 将电台放入电台部分
  • 导致金钱小于 0 的操作
  • 轨道类型或截面位置不正确时操作无效
  • 输出的动作数量不是 T

最终排名将由比赛结束后系统进行更多投入的测试来决定。 在临时/系统测试中,如果您提交的测试用例产生非法输出或超出了某些测试用例的时间限制,则只有这些测试用例的分数为零,并且您的提交将被排除在这些测试用例的 MAX 计算之外。

系统测试将仅执行 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。

测试用例数量

  • 临时测试:50
  • 系统测试:2000
    • 我们将发布 种子.txt (sha256=ed5b3f922dc3633bade3f70cc6f1dd1bb3087dba36ce26ce9d4888ce2ec7a247) 比赛结束后。

关于相关评价体系

在临时/系统测试中,排名将仅使用收到除以下结果之外的最后提交的结果来计算: CE。 在计算相对分数时,仅使用最后提交的内容来计算每个测试用例的 MAX。

排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。 另一方面,提交页面上显示的每个提交的分数是每个测试用例的绝对分数的总和,并且不显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。

关于执行时间

每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或确保有足够的执行时间。


输入

输入将从标准输入以以下格式提供。

\(
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} \\
\vdots \\
i_{M-1, s} ~ j_{M-1, s} ~ i_{M-1, t} ~ j_{M-1, t}
\)
  • 第一行有四个整数 N,M,K,T 以空格分隔。 坐标平面上的
    • N 表示R国的行数和列数,满足 N = 50.
    • M 代表R国的人口数量,满足 50 \le M \le 1600.
    • K 代表铁路公司X的初始资金并满足 11000 \leq K \leq 20000.
    • T 代表游戏的回合数,满足 T = 800.
  • 以下 M 线路提供有关居住在 R 国的人们的通勤信息。 每行包含四个空格分隔的整数,其中 person 的家 c 位于部分 (i_{c,s}, j_{c,s}) 工作地点位于 (i_{c, t}, j_{c,t} )。 满足以下条件: 0 \leq i_{c, s}, i_{c, t} \lt N, 0 \leq j_{c, s}, j_{c, t} \lt N, | i_{c,s} - i_{c,t} | + | j_{c,s} - j_{c,t} | \gt 4 (0 \leq c \lt M).

输出

输出 T 行。对于 t-第行,输出期间采取的操作 t-第构建阶段,格式如下:

  • 放置导轨时
    如果您正在建造类型为 p 部分 (i, j),输出 p, i, j 以空格分隔。 坐标平面上的
    导轨类型根据问题陈述中提供的图表进行编号。
  • 放置电台时
    如果您正在路段建设车站 (i, j),输出 0, i, j 以空格分隔。 坐标平面上的
  • 等待时
    输出 -1.

显示示例

输入生成

详情

让 \mathrm{rand}(L, U) 是一个生成均匀随机整数的函数 L 和 U,包含在内, 和 \mathrm{rand\_double}(L, U) 是一个生成大于或等于的均匀随机实数的函数 L 且小于 U, 和 \mathrm{normal}(\mu,\sigma) 是一个从均值正态分布生成随机实数的函数 \mu 和标准差 \sigma.

的一代 M

M = \mathrm{round}(50 \times 2 ^{\mathrm{rand\_double}(0,5)})

生成家庭和工作场所的位置

创建高斯混合模型来生成家庭位置,如下所示:
生成簇数 \mathrm{rand}(5,15)。 对于每个簇 i,生成权重 w_i = \mathrm{rand\_double}(0, 1),中心坐标 (r_i, c_i) = (\mathrm{rand\_double}(0, N-1), \mathrm{rand\_double}(0, N-1)),以及标准差 \sigma_i = \mathrm{rand\_double}(2, 15).
同样,创建高斯混合模型来生成工作场所位置。

重复以下过程 M 次生成人们的家庭和工作场所位置:

  1. 随机选择一个簇 i 来自高斯混合模型,用于以与权重成比例的概率生成家庭位置 w_i.
  2. 对于选定的 i,生成家庭位置为 r_0 = \text{round}(\text{normal}(r_i, \sigma_i)), c_0 = \text{round}(\text{normal}(c_i, \sigma_i)).
  3. 如果生成的位置 (r_0, c_0) 不满足 0 \leq r_0 \lt N or 0 \leq c_0 \lt N ,从步骤 1 开始。
  4. 同样,生成工作场所位置 (r_1, c_1) .
  5. 如果曼哈顿与住所位置之间的距离 (r_0, c_0) 和工作地点 (r_1, c_1) 小于或等于 4,从步骤 1 开始。

的一代 K

对于 M 人们,让他们的家和工作地点之间的最小曼哈顿距离为 d. K 生成为 \mathrm{rand}(\mathrm{max}(10, d) \times 100, 2 \times N \times 100) + 10000.

工具(输入生成器和可视化工具)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。

您的程序可能会输出以以下开头的注释行 #。 可视化工具的 Web 版本显示注释行以及相应的输出,这对于调试和分析可能很有用。 由于判断程序会忽略所有注释行,因此您可以提交按原样输出注释行的程序。

示例解决方案

Python 中的示例实现
import sys

Pos = tuple[int, int]
EMPTY = -1
DO_NOTHING = -1
STATION = 0
RAIL_HORIZONTAL = 1
RAIL_VERTICAL = 2
RAIL_LEFT_DOWN = 3
RAIL_LEFT_UP = 4
RAIL_RIGHT_UP = 5
RAIL_RIGHT_DOWN = 6
COST_STATION = 5000
COST_RAIL = 100


class UnionFind:
    def __init__(self, n: int):
        self.n = n
        self.parents = [-1 for _ in range(n * n)]

    def _find_root(self, idx: int) -> int:
        if self.parents[idx] < 0:
            return idx
        self.parents[idx] = self._find_root(self.parents[idx])
        return self.parents[idx]

    def is_same(self, p: Pos, q: Pos) -> bool:
        p_idx = p[0] * self.n + p[1]
        q_idx = q[0] * self.n + q[1]
        return self._find_root(p_idx) == self._find_root(q_idx)

    def unite(self, p: Pos, q: Pos) -> None:
        p_idx = p[0] * self.n + p[1]
        q_idx = q[0] * self.n + q[1]
        p_root = self._find_root(p_idx)
        q_root = self._find_root(q_idx)
        if p_root != q_root:
            p_size = -self.parents[p_root]
            q_size = -self.parents[q_root]
            if p_size > q_size:
                p_root, q_root = q_root, p_root
            self.parents[q_root] += self.parents[p_root]
            self.parents[p_root] = q_root


def distance(a: Pos, b: Pos) -> int:
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


class Action:
    def __init__(self, type: int, pos: Pos):
        self.type = type
        self.pos = pos

    def __str__(self):
        if self.type == DO_NOTHING:
            return "-1"
        else:
            return f"{self.type} {self.pos[0]} {self.pos[1]}"


class Result:
    def __init__(self, actions: list[Action], score: int):
        self.actions = actions
        self.score = score

    def __str__(self):
        return "\n".join(map(str, self.actions))


class Field:
    def __init__(self, N: int):
        self.N = N
        self.rail = [[EMPTY] * N for _ in range(N)]
        self.uf = UnionFind(N)

    def build(self, type: int, r: int, c: int) -> None:
        assert self.rail[r][c] != STATION
        if 1 <= type <= 6:
            assert self.rail[r][c] == EMPTY
        self.rail[r][c] = type

        # connect adjacent cells
        # top
        if type in (STATION, RAIL_VERTICAL, RAIL_LEFT_UP, RAIL_RIGHT_UP):
            if r > 0 and self.rail[r - 1][c] in (STATION, RAIL_VERTICAL, RAIL_LEFT_DOWN, RAIL_RIGHT_DOWN):
                self.uf.unite((r, c), (r - 1, c))
        # bottom
        if type in (STATION, RAIL_VERTICAL, RAIL_LEFT_DOWN, RAIL_RIGHT_DOWN):
            if r < self.N - 1 and self.rail[r + 1][c] in (STATION, RAIL_VERTICAL, RAIL_LEFT_UP, RAIL_RIGHT_UP):
                self.uf.unite((r, c), (r + 1, c))
        # left
        if type in (STATION, RAIL_HORIZONTAL, RAIL_LEFT_DOWN, RAIL_LEFT_UP):
            if c > 0 and self.rail[r][c - 1] in (STATION, RAIL_HORIZONTAL, RAIL_RIGHT_DOWN, RAIL_RIGHT_UP):
                self.uf.unite((r, c), (r, c - 1))
        # right
        if type in (STATION, RAIL_HORIZONTAL, RAIL_RIGHT_DOWN, RAIL_RIGHT_UP):
            if c < self.N - 1 and self.rail[r][c + 1] in (STATION, RAIL_HORIZONTAL, RAIL_LEFT_DOWN, RAIL_LEFT_UP):
                self.uf.unite((r, c), (r, c + 1))

    def is_connected(self, s: Pos, t: Pos) -> bool:
        assert distance(s, t) > 4  # precondition
        stations0 = self.collect_stations(s)
        stations1 = self.collect_stations(t)
        for station0 in stations0:
            for station1 in stations1:
                if self.uf.is_same(station0, station1):
                    return True
        return False

    def collect_stations(self, pos: Pos) -> list[Pos]:
        stations = []
        for dr in range(-2, 3):
            for dc in range(-2, 3):
                if abs(dr) + abs(dc) > 2:
                    continue
                r = pos[0] + dr
                c = pos[1] + dc
                if 0 <= r < self.N and 0 <= c < self.N and self.rail[r][c] == STATION:
                    stations.append((r, c))
        return stations


class Solver:
    def __init__(self, N: int, M: int, K: int, T: int, home: list[Pos], workplace: list[Pos]):
        self.N = N
        self.M = M
        self.K = K
        self.T = T
        self.home = home
        self.workplace = workplace
        self.field = Field(N)
        self.money = K
        self.actions = []

    def calc_income(self) -> int:
        income = 0
        for i in range(self.M):
            if self.field.is_connected(self.home[i], self.workplace[i]):
                income += distance(self.home[i], self.workplace[i])
        return income

    def build_rail(self, type: int, r: int, c: int) -> None:
        self.field.build(type, r, c)
        self.money -= COST_RAIL
        self.actions.append(Action(type, (r, c)))

    def build_station(self, r: int, c: int) -> None:
        self.field.build(STATION, r, c)
        self.money -= COST_STATION
        self.actions.append(Action(STATION, (r, c)))

    def build_nothing(self) -> None:
        self.actions.append(Action(DO_NOTHING, (0, 0)))

    def solve(self) -> Result:
        # find a person to connect
        rail_count = (self.K - COST_STATION * 2) // COST_RAIL
        person_idx = 0
        while person_idx < self.M:
            if distance(self.home[person_idx], self.workplace[person_idx]) - 1 <= rail_count:
                break
            person_idx += 1
        assert person_idx != self.M

        # build stations
        self.build_station(*self.home[person_idx])
        self.build_station(*self.workplace[person_idx])

        # connect stations with rails
        r0, c0 = self.home[person_idx]
        r1, c1 = self.workplace[person_idx]
        # r0 -> r1
        if r0 < r1:
            for r in range(r0 + 1, r1):
                self.build_rail(RAIL_VERTICAL, r, c0)
            if c0 < c1:
                self.build_rail(RAIL_RIGHT_UP, r1, c0)
            elif c0 > c1:
                self.build_rail(RAIL_LEFT_UP, r1, c0)
        elif r0 > r1:
            for r in range(r0 - 1, r1, -1):
                self.build_rail(RAIL_VERTICAL, r, c0)
            if c0 < c1:
                self.build_rail(RAIL_RIGHT_DOWN, r1, c0)
            elif c0 > c1:
                self.build_rail(RAIL_LEFT_DOWN, r1, c0)
        # c0 -> c1
        if c0 < c1:
            for c in range(c0 + 1, c1):
                self.build_rail(RAIL_HORIZONTAL, r1, c)
        elif c0 > c1:
            for c in range(c0 - 1, c1, -1):
                self.build_rail(RAIL_HORIZONTAL, r1, c)

        income = self.calc_income()
        self.money += income

        # do nothing for the rest of the time
        while len(self.actions) < self.T:
            self.build_nothing()
            self.money += income

        return Result(self.actions, self.money)


def main():
    N, M, K, T = map(int, input().split())
    home = []
    workplace = []
    for _ in range(M):
        r0, c0, r1, c1 = map(int, input().split())
        home.append((r0, c0))
        workplace.append((r1, c1))

    solver = Solver(N, M, K, T, home, workplace)
    result = solver.solve()
    print(result)
    print(f"score={result.score}", file=sys.stderr)


if __name__ == "__main__":
    main()

实施以下流程:

  1. 检查人 0, 1, \ldots 为了找到第一个可以在其家庭和工作地点放置车站并以初始资金将其与轨道连接的人。
  2. 在已识别人员的家庭和工作场所位置放置车站,并放置铁路以连接从家庭到工作场所。
  3. 之后,等待轮到 T.

该代码包含货币变化的模拟。您可以在创建解决方案时将其用作参考。