← 返回题目列表

AtCoder · ahc063_a

A. 多彩衔尾蛇

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

故事

高桥有一条宠物蛇,名叫“衔尾蛇”。 喂食后,这条蛇的尾巴会长1米,新长出的部分呈现出食物的颜色。 它还可以咬掉自己的身体,被咬掉的尾巴部分就变成了食物。

高桥计划按顺序喂食衔尾蛇,使其身体颜色的顺序符合他的喜好。 然而,他不小心把食物掉在地上,散落在房间里。 你的任务是给衔尾蛇下达指令,让它吃掉所有的食物,并使最终的身体颜色顺序尽可能接近高桥的喜好。 指令越少越好。

example

问题陈述

有一个 N \times N 网格。 左上角单元格的坐标是 (0,0),以及移动得到的单元格的坐标 i 细胞向下并且 j 右侧的单元格是 (i,j).

有 M-5 放置在网格上的食物块,每块食物都有一个由整数表示的颜色 1 to C.

一条蛇在此网格上移动。 一条蛇的长度 k 由一系列表示 k 坐标 (i_0,j_0),\cdots,(i_{k-1},j_{k-1}) 和颜色 c_0,\cdots,c_{k-1},从头到尾。 (i_0,j_0) 被称为 头, (i_1,j_1),\cdots,(i_{k-2},j_{k-2}) 这 身体,和 (i_{k-1},j_{k-1}) 这 尾巴。 尾巴可以与其他部分共享相同的坐标,但所有其他坐标必须不同。

最初,蛇有长度 5,所有颜色均为 1,它占据 (4,0),(3,0),(2,0),(1,0),(0,0)。 初始状态下蛇占据的细胞上没有放置任何食物。

以下操作最多重复 100000 转。

在每一回合中,您指定上、下、左或右四个方向之一,然后蛇将按以下顺序行动。

  1. 移动: 首先,蛇朝该方向移动一个单元格。 让 (i_0',j_0') 是从头部沿 方向移动一个单元格所到达的坐标 d。那么,移动之后,蛇的坐标就变成了 (i_0',j_0'),(i_0,j_0),\cdots,(i_{k-2},j_{k-2})。 导致掉头的方向,即这样的方向 (i_0',j_0')=(i_1,j_1),或超出范围的方向 N \times N 网格,无法指定。
  2. 吃: 如果有一块有颜色的食物 c' 在目标单元格,蛇的长度增加了 1,其坐标变为 (i_0',j_0'),(i_0,j_0),\cdots,(i_{k-2},j_{k-2}),(i_{k-1},j_{k-1}),其颜色变为 c_0,\cdots,c_{k-1},c'.
  3. 咬断: 考虑这样的情况:移动后,头部位于身体占据的单元格上。 设其索引为 h。也就是说,假设 1\leq h\leq k-2 和 (i_0',j_0')=(i_h',j_h') 表示移动后的坐标序列, (i_0',j_0'),\cdots,(i_{k-1}',j_{k-1}')。 在这种情况下,蛇咬掉了自己的身体,它的长度变成 h+1,剩余的尾侧变成相应颜色的食物。 更准确地说,蛇的坐标变成 (i_0',j_0'),\cdots,(i_h',j_h'),并且对于每个 p=h+1,\cdots,k-1,一块彩色食物 c_p 位于 (i_p',j_p')。 咬断后,尾巴和头部共享相同的坐标。 请注意,吃和咬不会同时发生。

首选颜色序列 给出了 d_0,\cdots,d_{M-1} 。 您的任务是使用尽可能短的操作序列,使蛇的最终颜色序列尽可能接近首选颜色序列。

评分

让 T 是输出操作序列的长度, k 是操作结束时蛇的长度,并且 c_0,\cdots,c_{k-1} 是蛇的颜色序列。 在这里, k 可能小于 M。 另外,让错误 E 是索引的数量 p=0,\cdots,k-1 这样 c_p\neq d_p.

然后,获得以下绝对分数。

\[ T + 10000 \times (E + 2(M-k)) \]

绝对分数越小越好。

对于每个测试用例,您将获得 排名分数 根据您的绝对分数较低者确定的排名。提交的分数是每个测试用例的总排名分数。排名分数的计算方式如下,排名分数越高越好。

让 n_{submit} 是提交作品的参赛者数量, n_{lose} 是获得绝对分数低于您的参赛者的数量,并且 n_{tie} 是获得与您相同的绝对分数的其他参赛者的数量。那么你在这个测试用例中的排名被确定为 r=n_{lose}+0.5 n_{tie},您的排名分数是 \mathrm{round}(10^9\times (1-\frac{r}{n_{submit}})).

最终排名将由比赛结束后系统进行更多投入的测试来决定。 在临时/系统测试中,如果您提交的测试用例产生非法输出或超出了某些测试用例的时间限制,则只有这些测试用例的排名分数将为零。 系统测试仅针对 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。

测试用例数量

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

关于相关评价体系

在临时/系统测试中,排名将仅使用收到除以下结果之外的最后提交的结果来计算: CE.

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

关于执行时间

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


输入

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

N M C
d_0 \cdots d_{M-1}
f_{0,0} \cdots f_{0,N-1}
\vdots
f_{N-1,0} \cdots f_{N-1,N-1}
  • N,网格的大小,是介于 8 和 16,包括在内。
  • M 表示首选颜色序列的长度,是介于 N^2/4 和 3N^2/4,包括在内。
  • C,颜色数量,是介于 3 和 7,包括在内。
  • d_0,\cdots,d_{M-1} 代表首选颜色序列,每个 d_p 是介于 1 和 C,包括在内。可以保证 d_0=\cdots=d_4=1.
  • f_{i,j} 是介于 0 和 C 代表放置在单元格中的食物的颜色 (i,j) 处于初始状态。
    • If f_{i,j}=0,该单元格上没有放置食物。
    • If 1 \leq f_{i,j} \leq C,一块彩色食物 f_{i,j} 被放置在该单元格上。
    • 保证 f_{0,0}=\cdots=f_{4,0}=0.
    • 有食物的细胞数量正好是 M-5.

输出

让 T 是操作次数。 让 a_t 表示转弯时的移动方向 t,由字符之一表示 U, D, L,和 R,对应上、下、左、右。

然后,按以下格式输出到标准输出。

a_0
\vdots
a_{T-1}

显示示例

示例解决方案 (Python)

Python 中的示例解决方案如下所示。 该程序按顺序吃掉所有食物,同时以垂直之字形移动。
import sys
input = sys.stdin.readline

N, M, C = map(int, input().split())
d = list(map(int, input().split()))
f = [list(map(int, input().split())) for _ in range(N)]

ans = []

for _ in range(4, N - 1):
    ans.append('D')

for col in range(1, N):
    ans.append('R')
    if col % 2 == 1:
        for _ in range(N - 1):
            ans.append('U')
    else:
        for _ in range(N - 1):
            ans.append('D')

print('\n'.join(ans))

输入生成

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

的一代 N, M,和 C

  • N=\mathrm{rand}(8,16)
  • M=\mathrm{rand}(\lceil\frac{N^2}{4}\rceil,\lfloor\frac{3N^2}{4}\rfloor)
  • C=\mathrm{rand}(3,7)

的一代 d

设置 d_0=\cdots=d_4=1,并生成剩余的 M-5 值如下。

让 n_0=0 和 n_C=M-5-C。 生成 C-1 随机数 n_1,\cdots,n_{C-1} by \mathrm{rand}(0,M-5-C),并按升序对它们进行排序。 使用这些定义每种颜色出现的次数 m_c by m_c=n_c-n_{c-1}+1。 如果存在一个 c 这样 m_c>(M-5)/2,生成 n 再次从头开始。

准备 m_c 每种颜色的副本 c,并按随机顺序洗牌以获得 d_5,\cdots,d_{M-1}.

的一代 f

选择 M-5 细胞均匀地随机从 N^2-5 初始状态下蛇占据的五个格子以外的格子, (4,0),(3,0),(2,0),(1,0),(0,0),并将它们表示为 (i_5,j_5),\cdots,(i_{M-1},j_{M-1})。 让 d_5',\cdots,d_{M-1}' 是随机排列 d_5,\cdots,d_{M-1}。 使用这些,设置 f_{i_p,j_p}=d_p' 对于每个 p=5,\cdots,M-1.

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

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