← 返回题目列表

AtCoder · ahc027_a

A. 重复清洁路线

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

故事

F公司开发了一款机器人吸尘器,高桥君清洁工No.2,并决定委托它来清洁他们的办公室。 高桥君2号吸尘器可以通过太阳能无限期地运行,并在预定的路线上无限期地重复清洁。 办公室的不同区域对污垢的敏感程度不同,通过经常清洁更容易污垢的区域,可以保持整个办公室的清洁。

问题陈述

有一个 N\times N 方板。 让 (0, 0) 是左上角正方形的坐标,并且 (i, j) 是所在正方形的坐标 i 向下平方并 从那里向右走 j 方块。 的周长 N\times N 棋盘周围有墙壁,相邻方格之间也可能有墙壁。

每个方格 (i,j) 被赋值 d_{i,j} 代表其对污垢的敏感性。 你的任务是通过在棋盘上移动来清理这些方块。 您可以移动到未被墙壁阻挡的相邻方格。 移动后,你移动到的方格的脏度会变成 0,以及所有其他方块的脏度 (i, j) 增加 d_{i, j}。 考虑一条开始和结束于 (0, 0),长度(移动次数)不超过 10^5。 清洁路线可以多次经过同一广场,但必须至少访问每个广场一次。

让 a_{t,i,j} 表示每个方格的脏度 (i,j) 之后 t第一步,让 S_t=\sum_{i=0}^{N-1}\sum_{j=0}^{N-1} a_{t,i,j} 表示总脏度。 在 t=0,我们假设所有方格的脏度是 a_{0,i,j}=0。 定义 平均脏度 作为 \[ \bar{S}=\frac{1}{L}\sum_{t=L}^{2L-1}S_t, \] 这是该期间总脏度的平均值 t=L,L+1,\cdots,2L-1 清扫路线长度时 L 无限重复。

请找到一条尽可能减少平均脏度的清洁路线。

平均脏度的含义

我们可以证明 a_{t,i,j}=a_{t+L,i,j} 为 t\geq L 清扫路线长度时 L 无限重复。 因此,考虑到平均 \frac{1}{T} \sum_{t=0}^{T-1} S_t 总脏度高达 T 转,其极限为 T \to \infty 与平均脏度一致。

评分

让 \bar{S} 是输出清洁路线的平均脏度。 那么你将获得绝对分数 \mathrm{round}(\bar{S})。 绝对分数越低越好。 如果输出非法清洁路线(长度超过 10^5,不返回 (0,0),有未访问过的方格,或者撞到了墙),会判断为 WA.

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

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

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

测试用例数量

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

关于相关评价体系

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

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

关于执行时间

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


输入

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

N
h_{0,0}\cdots h_{0,N-1}
\vdots
h_{N-2,0} \cdots h_{N-2,N-1}
v_{0,0} \cdots v_{0,N-2}
\vdots
v_{N-1,0} \cdots v_{N-1,N-2}
d_{0,0} \cdots d_{0,N-1}
\vdots
d_{N-1,0} \cdots d_{N-1,N-1}
  • N 是棋盘的水平和垂直尺寸,满足 20\leq N\leq 40.
  • h_{i,0}\cdots h_{i,N-1} 是一个长度为的字符串 N 仅包含 0 和 1. h_{i,j}=1 当且仅当方块之间有一堵墙 (i,j) 及其下邻居 (i+1,j).
  • v_{i,0}\cdots v_{i,N-2} 是一个长度为的字符串 N-1 仅包含 0 和 1. v_{i,j}=1 当且仅当方块之间有一堵墙 (i,j) 及其右邻居 (i,j+1).
  • 所有方块都保证可以从 (0, 0).
  • d_{i,j} 是一个整数值,表示方块对污垢的敏感性 (i,j) 并满足 1\leq d_{i,j}\leq 10^3.

输出

表示向上、向下、向左或向右移动 分别为 U, D, L,或 R。 代表清洁路线的长度 L 作为字符串 L 字符对应于每个动作,并将其以单行输出到标准输出。

显示示例

示例解决方案

这是 Python 中的示例解决方案。 在这个程序中,从(0,0)开始沿着深度优先搜索树移动,树中的每条边都经过两次,一次在途中,一次在返回时,程序输出一条返回(0,0)的清洁路线。
import sys
sys.setrecursionlimit(1000000)

N = int(输入()) h = [输入() for _ in range(N-1)] v = [输入() for _ in range(N)] d = [list(map(int, input().split())) for _ in range(N)]

访问过 = [[范围 (N) 中的 _ 为假] 范围 (N) 中的 _ ] DIJ = [(0, 1), (1, 0), (0, -1), (-1, 0)] 目录=“RDLU”

def dfs(i, j): 访问过[i][j] = True 对于范围(4)中的目录: di, dj = DIJ[目录] i2 = i + di j2 = j + dj 如果 0 <= i2 < N 且 0 <= j2 < N 并且未访问过[i2][j2]: 如果 di == 0 且 v[i][min(j, j2)] == '0' 或 dj == 0 且 h[min(i, i2)][j] == '0': 打印(DIR [目录],结束='') dfs(i2, j2) print(DIR[(dir + 2) % 4], end='')

dfs(0, 0) 打印()

输入生成

让 \mathrm{randint}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。 让 \mathrm{randdouble}(L,U) 是一个至少生成均匀随机浮点数的函数 L 且小于 U.

的一代 N

N=\mathrm{randint}(20,40).

的一代 h 和 v

生成参数 w=\mathrm{randint}(1,N) 控制墙的数量。 从没有墙壁的状态开始,通过重复以下操作生成墙壁 w 次。

随机选择四个方向(上、下、左、右)之一。 对于左方向,生成 i=\mathrm{randint}(0,N-2), j=\mathrm{randint}(0,N-1),和 k=\mathrm{randint}(3,\lfloor N/2\rfloor)。 然后,设置 h_{i,j}\cdots h_{i,\max(j-k+1, 0)} to 1。 同样,对于正确的方向,以相同的方式生成值,并设置 h_{i,j}\cdots h_{i,\min(j+k-1, N-1)} to 1。 对于向上的方向,生成 i=\mathrm{randint}(0,N-1), j=\mathrm{randint}(0,N-2),和 k=\mathrm{randint}(3,\lfloor N/2\rfloor)。 然后,设置 v_{i,j}\cdots v_{\max(i-k+1, 0),j} to 1。 同理,对于向下的方向,以同样的方式生成值,并设置 v_{i,j}\cdots v_{\min(i+k-1, N-1),j} to 1.

之后 w 迭代完成,检查是否所有方块都可以从 (0, 0),如果有无法到达的方块,则移除所有墙壁并重做 w 迭代。

的一代 d

生成参数 c=\mathrm{randint}(1,\lfloor N/2\rfloor) 确定易感区域的数量。 创建一个数组 d' 与 d'_{i,j}=0 对于所有人 (i,j),并更新 d' 重复以下过程 c 次。

生成 i=\mathrm{randint}(0,N-1), j=\mathrm{randint}(0,N-1), m=\mathrm{randint}(N,\lfloor N^2/c\rfloor),和 b=\mathrm{randdouble}(0,2)。 生成一组 S 从开始 S=\{(i,j)\} 并重复以下过程,直到大小 S 变为 m.

随机选择 p\in S,并随机选择四个方向之一(上、下、左、右)。如果从那个方向没有墙 p,添加相邻的方块 q to S.

对于每个方格 (i',j')\in S 包含在生成的 S,覆盖 d'_{i',j'}=b.

之后 c 迭代完成,生成 d_{i,j}=\mathrm{round}(10^{d'_{i,j}+\mathrm{randdouble}(0,1)}) 对于每个 (i,j).

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

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


样本输入 1

20
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000100000000000000
0000100000000000000
0000100000000000000
0000100000000000000
0000100000000000000
0000100000000000000
0000100000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
251 348 2 2 5 4 14 13 13 43 7 10 8 36 11 10 3 5 1 6
179 68 3 7 6 13 25 25 30 26 13 6 16 11 20 9 1 5 10 1
135 42 1 1 4 3 2 39 24 20 51 13 29 47 8 21 4 2 2 3
57 138 133 46 4 4 7 18 26 6 17 43 29 48 10 21 2 8 3 1
148 77 220 100 127 2 3 8 41 9 19 14 17 1 2 1 2 1 2 3
237 65 193 245 244 10 1 2 7 20 5 5 4 6 4 5 4 8 2 2
107 73 85 176 1 5 6 22 11 17 4 12 20 5 1 3 8 2 7 4
262 201 56 4 9 9 6 2 2 1 20 25 8 1 1 4 1 3 3 6
3 93 1 3 1 6 4 5 7 4 3 29 17 18 9 2 6 9 2 5
68 184 236 102 3 2 2 4 16 20 5 26 21 19 124 276 1 11 39 2
5 4 2 3 8 1 4 2 6 16 3 7 25 17 5 501 172 5 279 8
1 4 5 6 7 5 3 2 1 4 9 7 245 151 6 4 10 2 78 13
2 4 4 9 6 4 2 4 8 4 4 14 17 657 15 3 4 10 474 9
7 3 9 3 1 2 2 2 4 2 3 8 15 7 12 9 8 7 5 630
2 1 2 4 3 1 3 1 3 7 4 4 8 8 10 3 4 10 203 220
3 6 9 1 2 4 6 2 3 2 1 40 24 6 3 8 4 7 248 287
6 6 1 4 2 8 2 7 3 6 4 3 1 12 12 3 11 16 85 222
7 6 2 7 2 5 2 5 4 8 2 6 1 5 9 2 4 7 1 8
3 2 9 3 2 2 6 2 3 5 2 4 7 3 5 11 7 128 7 5
4 3 4 9 1 1 4 3 4 3 3 5 1 1 2 18 9 2 9 6

示例输出 1

RRRRRRRRRRRRRRRRRRRDDDDDDDDDDDDDDDDDDDLLLLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRRRRRULLLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRRRRRULLLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRRRRRULLLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRRRRRULLLLLLLLLLLLLLLLLLURRRRULLLLURRRRULLLLURRRRULLLLURRRRURRRRRRRRRRRRRRDDDDDDDLLLLLLLLLLLLLURRRRRRRRRRRRULLLLLLLLLLLLURRRRRRRRRRRRULLLLLLLLLLLLURRRRRRRRRRRRULLLLLLLLLLLLRRRRRRRRRRRRDLLLLLLLLLLLLDRRRRRRRRRRRRDLLLLLLLLLLLLDRRRRRRRRRRRRDLLLLLLLLLLLLDRRRRRRRRRRRRRUUUUUUUULLLLLLLLLLLLLLLDLLLURRURRRRRRRRRRRRRRRRLLLLLLLLLLLLLLLLLLRRDLLDRRRURRRRRRRRRRRRRRRDLLLLLLLLLLLLLLDLLLLDRRRRDLLLLDRRRRDLLLLDRRRRDLLLLDRRRRRRRRRRRRRRRRRRDLLLLLLLLLLLLLLLLLLDRRRRRRRRRRRRRRRRRRDLLLLLLLLLLLLLLLLLLDRRRRRRRRRRRRRRRRRRDLLLLLLLLLLLLLLLLLLDRRRRRRRRRRRRRRRRRRDLLLLLLLLLLLLLLLLLLDRRRRRRRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLLLLLLLL