← 返回题目列表

AtCoder · awtf2025heuristic_a

A. 群组命令和墙规划

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

问题陈述

有一个 N \times N 网格。 左上角单元格的坐标是 (0, 0),以及单元格的坐标 i 向下行并 j 右侧的列是 (i, j)。 一些相邻的牢房之间有墙壁。

有 K 网格上的机器人。 的初始位置 k第一个机器人是 (i_k, j_k),其目的地是 (i_k', j_k')。 高桥想要操作这些机器人,将它们全部带到各自的目的地。

在采取任何行动之前,可以做以下两类准备工作:

  1. 除了现有墙壁之外,您还可以在任何相邻单元格之间添加墙壁。
  2. 将机器人分组。每个机器人都属于一个组,并且同一组中的所有机器人可以同时操作。

这些准备工作必须在第一步之前完成。此后,不能放置额外的墙,也不能更改组分配。

接下来,可以通过重复执行以下两种类型的操作来移动机器人:

  1. 组命令:指定组和方向(上、下、左或右)。该组中的所有机器人将尝试沿指定方向移动一个单元。如果当前单元格和目标单元格之间有墙,或者目标单元格中​​有另一个机器人,则机器人不会移动。在属于该组的机器人中,那些在移动方向上最远的机器人将首先尝试移动。例如,如果机器人位于 (1, 0) 和 (2, 0) 且方向向上,机器人位于 (1, 0) 将移至 (0, 0) 首先(因为它有一个较小的 i 坐标),然后机器人在 (2, 0) 将移至现在为空的位置 (1, 0).

  2. 单独命令:指定机器人和方向(上、下、左或右)。指定的机器人将尝试沿指定方向移动一个单元。如果当前单元格和目标单元格之间有墙,或者目标单元格中​​有另一个机器人,则机器人不会移动。

即使机器人到达目的地一次,如果由于后续操作而远离目的地,则不被视为已到达目的地。

您最多可以执行 K N^2 操作。 使用尽可能少的操作引导所有机器人到达目的地。

评分

让 T 是执行的操作数,并让 d_k 是机器人最终位置和目的地之间的曼哈顿距离 k。然后,您将获得以下绝对分数: \[ T + 100 \times \sum_k d_k \]

绝对分数越低越好。

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

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

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

测试用例数量

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

关于相关评价体系

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

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

关于执行时间

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


输入

输入由标准输入按以下格式给出。

N K
i_0 j_0 i_0' j_0'
\vdots
i_{K-1} j_{K-1} i_{K-1}' j_{K-1}'
v_{0,0} \cdots v_{0,N-2}
\vdots
v_{N-1,0} \cdots v_{N-1,N-2}
h_{0,0} \cdots h_{0,N-1}
\vdots
h_{N-2,0} \cdots h_{N-2,N-1}
  • 在所有测试用例中, N=30 已修复。
  • 10 \leq K \leq 100
  • (i_k, j_k) 代表初始位置 k第一个机器人。
  • (i_k', j_k') 代表目的地 k第一个机器人。
  • 所有初始位置和所有目的地都是相互不同的,但机器人的初始位置 k 可能与机器人的目的地一致 k'.
  • 每个 v_{i,0} \cdots v_{i,N-2} 是长度为的二进制字符串 N-1。的 j- 第一个字符 板上显示的字符串的 v_{i,j} 表示是否有墙(1)或不(0) 单元格之间 (i, j) 和 (i, j+1).
  • 每个 h_{i,0} \cdots h_{i,N-1} 是长度为的二进制字符串 N。的 j- 第一个字符 板上显示的字符串的 h_{i,j} 表示是否有墙(1)或不(0) 单元格之间 (i, j) 和 (i+1, j).
  • 保证所有单元格相互可达。

输出

首先,将以下格式的墙壁放置信息输出到标准输出。

v'_{0,0} \cdots v'_{0,N-2}
\vdots
v'_{N-1,0} \cdots v'_{N-1,N-2}
h'_{0,0} \cdots h'_{0,N-1}
\vdots
h'_{N-2,0} \cdots h'_{N-2,N-1}
  • 每个 v_{i,0}' \cdots v_{i,N-2}' 是长度为的二进制字符串 N-1。的 j- 第一个字符 板上显示的字符串的 v_{i,j}' 表示是否放置了墙(1)或不(0) 单元格之间 (i, j) 和 (i, j+1).
  • 每个 h_{i,0}' \cdots h_{i,N-1}' 是长度为的二进制字符串 N。的 j- 第一个字符 板上显示的字符串的 h_{i,j}' 表示是否放置了墙(1)或不(0) 单元格之间 (i, j) 和 (i+1, j).
  • 对于已经存在墙壁的位置, 可以输出 0 or 1 。

接下来,按以下格式将组分配信息输出到标准输出。

g_0 \cdots g_{K-1}
  • g_k 是介于 0 和 K-1 代表该组 k第一个机器人属于。如果 g_k = g_{k'},然后是机器人 k 和机器人 k' 属于同一组。

最后,按以下格式将操作序列输出到标准输出。

a_0 b_0 d_0
\vdots
a_{T-1} b_{T-1} d_{T-1}
  • a_t 是单个字符,指定回合操作类型 t。使用 g 用于组命令和 i 用于单个命令。
  • b_t 是介于 0 和 K-1 表示轮次操作的对象组编号或机器人编号 t。如果指定了没有机器人的组,则不会发生任何情况。
  • d_t 是单个字符,指示转弯操作的方向 t,如下:
    • 上: U
    • 向下: D
    • 左: L
    • 右: R

显示示例

输入生成

让 \mathrm{rand}(L, U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。

机器人一代

机器人数量 K 由下式确定 K = \mathrm{rand}(10, 100).
机器人的初始位置通过选择 K 均匀随机的不同坐标 N^2 细胞。
机器人的目的地同样通过选择 K 均匀随机的不同坐标 N^2 细胞。

墙生成

墙段数量 W 由下式确定 W = \mathrm{rand}(0, 2).

重复以下操作 W 次:

  1. 从上、下、左或右中随机选择墙壁的方向。
  2. 确定墙长 L = \mathrm{rand}(10, 20).
  3. 对于垂直墙,选择起点 (i, j) by i = \mathrm{rand}(5, N-5),\ j = \mathrm{rand}(4, N-6).
    如果选择 j 的绝对距离为 4 来自任何 j 用于先前生成的垂直墙,重做方向选择。
    对于向上的墙壁,设置 v_{i-L+1, j}, \cdots, v_{i, j} to 1。对于向下的墙,设置 v_{i, j}, \cdots, v_{i+L-1, j} to 1。忽略任何超出范围的部分。
  4. 对于水平墙,选择起点 (i, j) by i = \mathrm{rand}(4, N-6),\ j = \mathrm{rand}(5, N-5).
    如果选择 i 的绝对距离为 4 来自任何 i 用于先前生成的水平墙,重做方向选择。
    对于左侧墙壁,设置 h_{i, j-L+1}, \cdots, h_{i, j} to 1。对于右侧墙壁,设置 h_{i, j}, \cdots, h_{i, j+L-1} to 1。忽略任何超出范围的部分。
  5. 生成墙后,检查所有单元格是否仍可相互可达。如果没有,请重置墙壁并重新启动 W 迭代。

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

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


示例输入 1

30 59
8 18 11 17
8 23 17 15
1 12 11 7
19 17 24 22
23 9 8 20
21 17 26 10
4 19 12 29
19 29 7 7
19 24 12 19
24 26 19 10
12 23 4 18
8 22 26 11
23 18 16 26
28 14 8 14
6 12 21 12
28 18 13 21
21 28 17 3
5 14 11 20
28 13 19 28
27 18 18 8
7 21 28 23
25 13 0 17
15 17 4 24
15 19 7 0
3 26 10 25
26 20 7 6
17 10 28 17
8 9 5 21
2 26 12 9
18 29 21 10
7 20 10 24
23 5 11 18
24 12 4 9
9 19 26 13
1 0 15 12
9 8 3 8
29 9 15 24
22 14 3 18
15 16 15 1
1 29 19 4
9 12 27 21
2 23 9 4
18 24 14 18
22 7 8 1
20 29 24 3
3 2 12 17
10 11 15 20
16 6 24 0
6 5 29 17
29 20 26 16
14 18 0 9
29 11 26 20
24 22 1 13
1 5 15 9
26 10 27 26
20 20 2 6
6 28 15 2
22 6 0 0
6 17 16 13
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000000000000000000000
00000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000

示例输出 1

00000000000000000000000000000
01000000000000000000000000000
00000000000000000000000000000
00000000000000000000001000000
00000000000100000000000000000
00000000000000000000000000001
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000100000000000000000
00000000000100000000010000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100001000000000000
00000000000100000000000100000
00000000000100000000000001000
00010000000100000000000000000
00000000000100000000000000000
00000010000100000000000000000
01000000000100000000000000000
00000000000100000000000000100
00000000000100000000000000000
00000001000100000000000000000
00000000000100000000000000000
00000000000100000000000001010
00000000000100000000000000000
00000000000100000000000000000
00000000000000000000000000000
00000000000000000000000000000
000000100000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000100000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000001000000
000000000000000000000000000000
000000000000000000000000000100
000001000000000000000000000000
000000000000000000000100100000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000010000000000000
000000000000000000000000100000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000010000
000000100000000000000000000000
000000000000000000000000000000
000000000000000010000000000000
000000000000000100000000000000
000000000000000000000000000000
000000000000000000000000000000
000000001000000000000000000000
6 2 3 3 8 9 0 1 8 0 9 7 5 6 3 6 7 5 4 6 7 3 0 1 5 8 3 4 5 6 7 0 0 3 9 5 4 6 2 8 8 6 6 0 9 7 2 1 3 9 3 6 2 6 5 4 0 3 8
i 16 D
g 0 U
i 27 U
g 1 L
i 0 D
g 5 D
i 58 D
i 52 U
i 44 D
i 17 D
g 0 U
g 4 U
i 32 U
g 2 U
i 31 U
g 9 L
g 0 U
g 2 L
i 30 D
g 3 D
i 48 D
g 2 L
i 14 D
i 1 D
g 7 D
g 3 D
i 14 D
g 1 L
i 32 U
i 57 U
i 56 D
i 21 U
g 6 D
i 4 U
i 20 D
g 7 D
i 7 U
i 39 D
i 42 U
g 7 D
i 15 U
i 32 U
i 6 D
g 6 D
i 50 U
g 5 D
g 4 U
g 2 L
i 40 D
g 2 L
i 29 D
i 1 D
g 7 D
g 7 D
i 41 D
g 9 L
i 48 D
i 16 D
g 8 L
g 5 D
g 6 D
i 14 D
i 50 L
g 6 U
i 29 D
i 46 R
g 6 L
i 9 D
g 6 D
i 16 L
i 7 U
i 2 D
g 9 D
g 5 D
g 8 L
g 8 L
i 4 R
i 40 D
i 10 U
g 4 R
i 50 L
g 9 L
i 28 L
i 32 U
g 3 D
i 4 U
i 6 D
i 35 U
i 33 D
g 0 U
g 7 R
i 23 U
g 4 R
g 6 D
i 7 U
i 57 U
g 0 U
g 5 D
g 6 D
g 3 D