← 返回题目列表

AtCoder · ahc045_a

A. Oracle 引导的道路网络规划

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

故事

很久以前,高桥王国各地散布着许多城市。但当时没有道路,人们在城市之间出行很困难。 为了发展国家,高桥国王决定将城市分成几个组,并修建道路,以便人们可以在同一组中的任意两个城市之间通行。 高桥希望道路的总长度尽可能短。但王国没有好的地图,所以没有人知道城市的具体位置。

高桥不知道如何修路,所以他向王国最伟大的算命先生寻求帮助。 算命先生可以找到用道路连接一组选定的城市的最短路线,以便所有这些城市都可以相互到达。 不过,算命的次数是有限制的。

请想办法用算命的办法修路,让总长度尽可能的短。

问题陈述

有 N 二维平面上的城市,编号为 0 to N-1。 城市的准确坐标 i 在判断器内部固定为 (x_i, y_i),但输入中未给出它们。 相反,对于每个城市 i,输入提供可能坐标的矩形区域: lx_i, rx_i, ly_i,和 ry_i,这样 lx_i \le x_i \le rx_i 和 ly_i \le y_i \le ry_i。 两个城市之间的距离定义为欧几里德距离向下舍入到最接近的整数: \mathrm{dist}(i, j) = \left\lfloor \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} \right\rfloor.

给你一个数组 G 长度 M。 你的目标是将城市划分为 M 分组,以便每组的大小为 G_0, G_1, \dots, G_{M-1},并修建道路,以便连接每个组内的所有城市。

在输出你的最终答案之前,你可以补充 Q 算命查询,格式如下:

  • 选择城市子集 C \subset \{0,1,\cdots,N-1\}。尺寸 l = |C| 必须满足 2 \le l \le L,其中 L 是输入中给出的限制。
  • 作为对查询的回应,您收到 l - 1 在集合上形成最小生成树 (MST) 的城市对 C。 MST 使用以下算法构建:
    • 初始化边列表 E 中每对城市之间的所有边 C.
    • 排序 E 通过增加城市之间的距离,使用真实坐标。如果两条边的距离相同,则按城市对的字典顺序对它们进行排序 (u, v) 他们连接,在哪里 u < v.
    • 遍历中的边缘 E 按顺序。对于每条边,如果添加它不会创建环,则将其包含在 MST 中。
    • 对于组成 MST 的每条边,对查询的响应按城市对按字典顺序排序 (u, v) 他们连接,在哪里 u < v.

执行查询后,输出满足以下条件的城市分组和道路建设规划:

  • 划分 N 城市成 M 组。各组 i 必须完全包含 G_i 城市。任何城市不得未分配或分配给多个组。
  • 对于每个组 i,选择 G_i - 1 连接组中城市的道路,使得所有城市都可以通过这些道路相互到达,即由道路形成的图必须是连接的。

请注意,每条道路恰好连接两个城市。即使平面上有多条道路交叉,你也无法从一条道路移动到另一条道路。

评分

您获得的绝对分数是输出中所有道路的总长度。 连接城市的道路长度 i 和城市 j 使用真实坐标计算, \mathrm{dist}(i, j) = \left\lfloor \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} \right\rfloor. 绝对分数越小越好。

对于每个测试用例,我们计算 相对分数 \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}),其中 YOUR 是您的绝对分数,MIN 是在该测试用例中获得的所有竞争对手中最低的绝对分数。提交的分数是相对分数的总和。

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

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

测试用例数量

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

关于相关评价体系

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

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

关于执行时间

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

输入和输出

首先,给你城市的数量 N,组数 M,最大查询数 Q,上限 L 查询中使用的城市集的大小,最大可能的宽度或高度 W 可能包含城市坐标的矩形,数组 G 代表分配给每个组的城市数量,对于每个城市,直角坐标范围 lx_i, rx_i, ly_i, ry_i ,它可能存在于其中,采用标准输入的以下格式。

N M Q L W
G_0 G_1 \cdots G_{M-1}
lx_0 rx_0 ly_0 ry_0
\vdots
lx_{N-1} rx_{N-1} ly_{N-1} ry_{N-1}

每个值满足以下约束:

  • N = 800
  • 1 \leq M \leq 400
  • Q = 400
  • 3 \leq L \leq 15
  • 500 \leq W \leq 2500
  • 1 \leq G_i \leq N
  • \sum_{i=0}^{M-1} G_i = N
  • 0 \leq lx_i \leq rx_i \leq 10000
  • 0 \leq rx_i - lx_i \leq W
  • 0 \leq ly_i \leq ry_i \leq 10000
  • 0 \leq ry_i - ly_i \leq W
  • 所有输入值均为整数。

阅读以上输入后,您最多可以执行 Q 查询。

在每个查询中,选择城市的子集 C \subset \{0,1,\cdots,N-1\}。 尺寸 l = |C| 必须满足 2 \le l \le L,其中 L 在输入中给出。 按以下格式将所选子集打印到标准输出:

\mathrm{?} l C_0 C_1 \cdots C_{l-1}

输出后面必须跟有新行,并且您必须刷新标准输出。 否则,提交内容可能会被判定为 TLE.

输出后,您将收到来自标准输入的 l - 1 双城市 a_i, b_i \in C,每个代表集合上最小生成树中道路的端点 C,格式如下:

a_0 b_0
\vdots
a_{l-2} b_{l-2}

完成后 Q 查询,输出仅包含该字符的行 \mathrm{!} 到标准输出。

\mathrm{!}

然后,对于每个 M 组,按以下格式输出你的答案。 团体用 k,输出城市集合 C \subset {0, 1, \cdots, N - 1} 分配给该组,以及连接这些城市的道路集,其中每条道路由一对城市表示 a_i, b_i \in C,格式如下:

C_0 C_1 \cdots C_{G_k-1}
a_0 b_0
\vdots
a_{G_k-2} b_{G_k-2}

您的输出必须满足以下条件:

  • 每个城市必须恰好分配到一组。任何城市不得未分配或分配给多个组。
  • 每组中的城市必须可以通过这些道路相互到达,即道路形成的图必须是相连的。

示例

q 输出 输入
先前信息
5 2 3 3 500
3 2
1375 1648 351 624
1773 1900 3660 3787
2922 3231 558 867
5358 5640 8585 8867
3218 3684 3330 3796
0
? 3 4 1 2
1 4
2 4
1
? 3 1 3 4
1 4
3 4
答案
!
3 4 1
3 4
1 4
2 0
0 2

显示示例

输入生成

  • \mathrm{rand}(L,U): 均匀地随机生成一个整数 L 和 U,包括在内。
  • \mathrm{rand\_double}(L,U): 均匀地随机生成一个实数 L 和 U,包括在内。

的一代 M, L, W

  • M = \left\lfloor (\mathrm{rand\_double}(1.0, 20.0))^2 \right\rfloor
  • L = \mathrm{rand\_int}(3, 15)
  • W = \mathrm{rand\_int}(500, 2500)

的一代 G

  • 生成 M - 1 之间均匀随机的不同整数 1 和 N - 1,包含在内,并按升序对它们进行排序。让这些成为 A_1, A_2, \cdots, A_{M-1}.
  • 定义 A_0 = 0 和 A_M = N,并设置 G_i = A_{i+1} - A_i.

的一代 x_i, y_i, lx_i, rx_i, ly_i, ry_i

  • x_i = \mathrm{rand\_int}(0, 10000)
  • y_i = \mathrm{rand\_int}(0, 10000)
  • w_i = \mathrm{rand\_int}(0, W)
  • dx_i = \mathrm{rand\_int}(0, w_i)
  • rx_i = x_i + dx_i
  • lx_i = rx_i - w_i
  • dy_i = \mathrm{rand\_int}(0, w_i)
  • ry_i = y_i + dy_i
  • ly_i = ry_i - w_i
  • 如果有任何 lx_i, rx_i, ly_i,或 ry_i 小于 0,替换为 0;如果超过 10000,替换为 10000.

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

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

工具使用的输入文件规范

提供给本地测试器的输入文件包括附加到提供给解决方案程序的先验信息末尾的以下格式的附加信息。

x_0 y_0
\vdots
x_{N-1} y_{N-1}

x_i, y_i 是城市的真实坐标 i,并且它们不会提供给您的程序。

示例解决方案

Python 中的示例解决方案。
def query(c):
    print("?", len(c), *c, flush=True)
    return [tuple(map(int, input().split())) for _ in range(len(c) - 1)]


def answer(groups, edges):
    print("!")
    for i in range(len(groups)):
        print(*groups[i])
        for e in edges[i]:
            print(*e)


# read input
N, M, Q, L, W = map(int, input().split())
G = list(map(int, input().split()))
lx, rx, ly, ry = [], [], [], []
for _ in range(N):
    a, b, c, d = map(int, input().split())
    lx.append(a)
    rx.append(b)
    ly.append(c)
    ry.append(d)

# use center of rectangle
x = [(l + r) // 2 for l, r in zip(lx, rx)]
y = [(l + r) // 2 for l, r in zip(ly, ry)]

# split cities into groups
cities = list(range(N))
cities.sort(key=lambda i: (x[i], y[i]))
groups = []
start_idx = 0
for g in G:
    groups.append(cities[start_idx : start_idx + g])
    start_idx += g

# get edges from queries
edges = []
for k in range(M):
    edges.append([])
    for i in range(0, G[k] - 1, 2):
        if i < G[k] - 2:
            ret = query(groups[k][i : i + 3])
            edges[k].extend(ret)
        else:
            edges[k].append(groups[k][i : i + 2])

# output answer
answer(groups, edges)

实施以下程序:

  1. 按中心坐标对城市进行排序 (\frac{lx_i + rx_i}{2}, \frac{ly_i + ry_i}{2}) 给定的矩形范围并按顺序将它们分成组。
  2. 对于每个组,通过滑动大小为 2 的窗口执行 3 个城市查询,并将查询响应中返回的边直接添加到最终答案中。
  3. 如果组中的最后一个城市无法包含在任何查询中,请添加一条将其连接到组中前一个城市的边作为最终答案。