← 返回题目列表

AtCoder · ahc011_a

A. 滑动树拼图

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

故事

高桥喜欢拼图,正在玩以下著名的滑动拼图。

有 N^2-1 上的瓷砖 N \times N 板。 有一个空方块,您可以将四个方向中任何一个方向的相邻图块滑入空方块中。 有些图片被分成每个图块。通过反复滑动瓷砖,请对齐图片。

麻烦的是,高桥扔掉了说明书,所以他丢失了目标图片。 根据他的记忆,目标图片是一张 树。 通过重复滑动操作,请完成一棵树。

exampl

问题陈述

有 N^2-1 上的瓷砖 N \times N 板。 让 (i, j) 表示行的坐标 i (0\leq i \leq N-1) 从顶部和列 j (0\leq j\leq N-1) 从左边开始。 每个图块包含一个图形,其线条从其中心朝向四个方向中的一个或多个方向:上、下、左、右。 我们使用位掩码来表示每个图块,其中 1 代表左,2 代表上,4 代表右,8 代表下,如下所示。

瓷砖
二进制 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
十六进制 0 1 2 3 4 5 6 7 8 9 a b c d e f

数字0代表一个空方格,并且正好有一个空方格。 通过一次操作,您可以将与空方格相邻的一块图块向四个方向滑动到空方格的位置。移动后,移动棋子的方格将变成空方格。 最多可以重复滑动操作 T=2\times N^3 次。

完成操作后,考虑一个图表 N^2-1 除空方格以外的方格作为顶点和下面的边。

  • 对于每个 (i, j) (0\leq i\leq N-2, 0\leq j\leq N-1),如果 (i,j) 是一个带有向下线的图块,并且 (i+1,j) 是一个具有向上线的图块,然后在之间构建一条边 (i,j) 和 (i+1,j).
  • 对于每个 (i, j) (0\leq i\leq N-1, 0\leq j\leq N-2),如果 (i,j) 是一个带有向右线的图块, (i,j+1) 是一个带有向左线的图块,然后在之间构建一条边 (i,j) 和 (i,j+1).

你的任务是找到一个短的操作序列,使得该图中最大树的大小(即没有环路的最大连通分量的顶点数)尽可能大。 保证在 T 操作可以构造一个大小的树 N^2-1 中的空方块 (N-1,N-1)。 请注意,空方块的最终位置是任意的,您不必将其移动到 (N-1,N-1).

评分

让 K 是操作次数并且 S 是应用操作序列后画在板上的最大树的大小。 然后,您将得到以下分数。

  • If S<N^2-1, \mathrm{round}\left(500000\times \frac{S}{N^2-1}\right)
  • If S=N^2-1, \mathrm{round}\left(500000\times (2-\frac{K}{T})\right)

如果操作次数超过 T 或者您执行非法操作将不存在的图块移至空方格,将被判定为 WA .

测试用例数量

  • 临时测试:50
  • 系统测试:3000。我们将发布 种子.txt (sha256=041256f962c6ba1a60294ad7a575684d6e401163cba316cf978f2e66a4f7b0e3) 比赛结束后。
  • 临时测试和系统测试都包含相同数量的输入 N=6,7,8,9,10.

提交的分数是每个测试用例的总分。 在临时测试中,如果您的提交产生非法输出或某些测试用例超出时间限制,则提交本身将被判定为 WA or TLE ,提交的分数将为零。 在系统测试中,如果您提交的测试用例产生非法输出或超出时间限制,则只有这些测试用例的分数为零。

关于执行时间

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


输入

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

N T
t_{0,0} \cdots t_{0,N-1}
\vdots
t_{N-1,0} \cdots t_{N-1,N-1}

N 是代表棋盘高度和宽度的整数,满足 6\leq N\leq 10。 在所有测试用例中, T=2\times N^3. t_{i,0} \cdots t_{i,N-1} 是一个长度为的字符串 N。 的 j- 第一个字符 t_{i,j} is 0-9 or a-f 这是图块中包含的数字的十六进制表示 (i,j).

输出

通过单个字符来表示将向上、向下、向左或向右相邻的图块滑入空方格的每个操作 U, D, L or R分别输出序列 K 作为长度字符串进行操作 K 在一行中连接到标准输出。

显示示例

输入生成

的一代 N 和 T

我们生成 N 作为种子值除以 5 + 6 的余数。 因此,您可以生成具有特定的输入 N 值通过调整种子值来实现。 我们设定 T=2\times N^3.

的一代 t_{i,j}

让 [k]=\{0,1,\cdots,k-1\}。 我们随机生成一棵生成树 (V,F) 带有顶点 V=[N]\times [N]\setminus \{(N-1,N-1)\} 如下。

  1. 首先,我们随机打乱边缘 \{\{(i,j),(i+1,j)\}\mid (i,j)\in [N-1]\times [N]\setminus \{(N-2,N-1)\}\}\cup\{\{(i,j),(i,j+1)\}\mid (i,j)\in [N]\times [N-1]\setminus \{(N-1,N-2)\}\} 并获得有序边列表 e_0, e_1, \cdots.
  2. 从 F=\emptyset,对于每个 e_k=\{(i,j),(i',j')\},我们插入 e_k 进入 F if (i,j) 和 (i',j') 未连接 (V,F).

从获得的生成树中,我们构建了图块,其上的树大小为 N^2-1 绘制如下。

  1. 对于每个 (i,j),如果 \{(i,j),(i+1,j)\}\in F,然后在图块上画一条向下的线 (i, j) 和瓷砖上的向上线 (i+1,j).
  2. 对于每个 (i,j),如果 \{(i,j),(i,j+1)\}\in F,然后在图块上画一条向右的线 (i, j) 和图块上的向左线 (i,j+1).

最后,从构造好的tile布局开始,随机执行 T=2\times N^3 滑动操作,并让 t 是操作后的图块布局。 在这里, k (\geq 2)-th 操作是从最多三个方向均匀随机选择的,不包括恢复操作的方向 (k-1)-第次操作。

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

比赛期间,您可以在 Twitter 上分享提供的 Seed=0 可视化工具的输出图像 (PNG)。 请注意,禁止以视频格式共享。 您必须使用指定的主题标签和公共帐户。 您只能共享seed=0 的可视化结果和分数。 请勿分享 GIF、输出本身、其他种子的分数或提及解决方案或讨论。 (已添加)可视化工具具有更改 N 值的功能,但也禁止共享已更改输入的可视化结果。

共享图像列表


示例输入 1

6 432
62ce43
a068f9
a89da9
5d93cb
276253
424ba8

示例输出 1

RRRDLUULDDDDLUUUR