← 返回题目列表

AtCoder · ahc038_a

A. 树机器人手臂

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

故事

首席执行官高桥,谁爱 章鱼烧 (日本食品)正在开发一种机械臂,以协助在章鱼烧炊具上移动章鱼烧。 在以二维网格为代表的章鱼烧炉上,多个章鱼烧被放置在某些网格方块上。 您需要使用机械臂将章鱼烧从这些方格移动到一组指定的目标方格。 机械臂有多个指尖,结构像一棵树,以关节和指尖为顶点。 在单次转动中,机械臂可以同时执行以下动作:将整个手臂向上、向下、向左或向右移动;绕关节旋转 90 度;用指尖抓住或松开章鱼烧。 设计机械臂并确定操作方法,尽可能减少转动次数。

example

问题陈述

有一个 N \times N 章鱼烧炊具。 让 (0,0) 是左上角方块的坐标, (i,j) 是所在正方形的坐标 i 向下平方并 从那里向右走 j 方块。

最初,章鱼烧被放置在 M 不同的方块,你需要将它们移动到 M 指定的目标方块。

首先,您必须设计机械臂。 机械臂被表示为一棵树,其中“关节”和“指尖”是顶点,连接它们的刚性段是边缘。
指尖对应于树的叶子,而关节对应于其他顶点。
连接顶点的边的长度 u 及其子项 v 表示为 L(u,v).

给定了顶点数 V 可用于机械臂,你的任务是设计一棵不超过 V 顶点并将其与根的初始位置一起输出。 每条边的长度 L(u,v) 必须是满足以下条件的整数 1 \leq L(u,v) \leq N-1.

接下来,您必须操作设计的机械臂来移动章鱼烧。 从根位于指定位置且所有边都向右延伸的初始位置开始,每回合可以独立执行以下操作:

  1. 您可以将整个机械臂向上、向下、向左或向右移动一格。新的根坐标 (x,y) 必须满足 0 \leq x, y \leq N-1.
  2. 对于每个顶点 路径图的 u 除了根之外,您还可以独立旋转以 u 绕其父级逆时针或顺时针旋转 90 度 p.
  3. 对于每个指尖,你可以独立地将其所持有的章鱼烧放置在当前方格上,或者从当前方格中拿起章鱼烧。您不能将章鱼烧放在已经包含章鱼烧的方格上或在该方格之外。 N \times N 网格。每个指尖不能同时容纳多个章鱼烧。

操作示例2

➡ ➡

从左图开始,以顶点 1 为根的整个子树绕顶点 0 顺时针旋转 90 度,得到中图。
此外,将以顶点 3 为根的整个子树绕顶点 1 顺时针旋转 90 度会得到右图。

按照先1、2、后3的顺序执行操作。 在操作3中,指尖按照从最小顶点数到最大顶点数的顺序进行处理(1和2内的顺序不影响结果)。 允许机械臂的一部分伸出到范围之外 N \times N 一次操作后的网格,机械臂的多个顶点可以占据同一个方格。

您最多可以执行 10^5 转动。

评分

让 K 为圈数,并令 M' 是操作结束时目标位置处的章鱼烧数量。
然后,您将获得以下绝对分数。 绝对分数越低越好。

  • If M'=M, K
  • If M'<M, 10^5+1000\times (M-M')

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

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

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

测试用例数量

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

关于相关评价体系

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

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

关于执行时间

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


输入

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

N M V
s_{0,0}\cdots s_{0,N-1}
\vdots
s_{N-1,0}\cdots s_{N-1,N-1}
t_{0,0}\cdots t_{0,N-1}
\vdots
t_{N-1,0}\cdots t_{N-1,N-1}
  • 网格的大小 N 是满足以下条件的整数 15 \leq N \leq 30.
  • 章鱼烧数量 M 是满足以下条件的整数 N^2/10 \leq M \leq N^2/2.
  • 顶点数 V 可用于机械臂的是满足以下条件的整数 5 \leq V \leq 15.
  • s_{i,0} \cdots s_{i,N-1} 是一个长度为的字符串 N 组成 01。如果 j- 第一个字符是 1,表示章鱼烧最初放置在正方形上 (i,j)。章鱼烧的方格总数正好是 M.
  • t_{i,0} \cdots t_{i,N-1} 是一个长度为的字符串 N 组成 01。如果 j- 第一个字符是 1,表示正方形 (i,j) 是目标位置。目标方格的总数正好是 M.

输出

让 V' 是设计的机械臂中的顶点数,其中 1 \leq V' \leq V.
机械臂的顶点编号为 0 to V'-1 使得顶点 0 是根,也是顶点的父级 u 是一个数字小于的顶点 u.
让 p_u (0 \leq p_u \leq u-1) 是顶点的父级 u (1 \leq u \leq V'-1),并让边缘的长度 (p_u, u) be L(p_u, u),其中 1 \leq L(p_u, u) \leq N-1.
设初始状态下根的坐标为 (x, y),其中 0 \leq x, y \leq N-1。 然后,按以下格式输出到标准输出。

V'
p_1 L(p_1, 1)
\vdots
p_{V'-1} L(p_{V'-1}, V'-1)
x y

接下来,输出操作序列。
每回合的操作由一个字符串表示 S 长度 2V' 如下:

  • 的 0- 第一个字符代表整个机械臂向上移动一格(U),向下(D),左(L),右(R),或者没有移动(.).
  • 的 i- 第一个字符 (1 \leq i \leq V'-1) 表示以顶点为根的整个子树的旋转 i 周围 p_i:逆时针旋转90度表示为 L,顺时针旋转 90 度表示为 R,并且没有旋转表示为 ..
  • 的 (V' + i)- 第一个字符 (0 \leq i \leq V'-1) 表示顶点的动作 i。如果顶点不是指尖(叶子)或者没有采取任何动作,则用 .。如果指尖抓住或释放章鱼烧,则表示为 P.

让 T 为圈数,并令 S_t 代表字符串 t第回合。 按以下格式输出到标准输出。

S_0
\vdots
S_{T-1}

显示示例

示例解决方案(Python)

这是一个 Python 示例解决方案。 在这个程序中,创建了一棵边长为1的二顶点树,通过随机移动100圈将章鱼烧运送到目的地。
import random

random.seed(42)
DX = [0, 1, 0, -1]
DY = [1, 0, -1, 0]
DIR = ['R', 'D', 'L', 'U']

# read input
N, M, V = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(N)]
t = [list(map(int, list(input()))) for _ in range(N)]

# design the tree
tree = [[0, 1]]
print(len(tree) + 1)
for p, L in tree:
    print(p, L)

# decide the initial position
rx, ry = 0, 0
print(rx, ry)

dir1 = 0 # direction of edge (0, 1)
holding = False # whether holding a takoyaki

for turn in range(100):
    S = []
    # random move
    dir = random.randint(0, 3)
    dx, dy = DX[dir], DY[dir]
    if 0 <= rx + dx < N and 0 <= ry + dy < N:
        rx += dx
        ry += dy
        S.append(DIR[dir])
    else:
        S.append('.')
    # random rotate
    rot = random.randint(0, 2)
    if rot == 0:
        S.append('.')
    elif rot == 1:
        S.append('L')
        dir1 = (dir1 + 3) % 4
    else:
        S.append('R')
        dir1 = (dir1 + 1) % 4
    # grab or release takoyaki
    x, y = rx + DX[dir1], ry + DY[dir1]
    change = False
    if 0 <= x and x < N and 0 <= y and y < N:
        if s[x][y] == 1 and t[x][y] == 0 and not holding:
            change = True
            s[x][y] = 0
            holding = True
        elif s[x][y] == 0 and t[x][y] == 1 and holding:
            change = True
            s[x][y] = 1
            holding = False
    S.append('.') # vertex 0 (root) is not a leaf
    if change:
        S.append('P')
    else:
        S.append('.')
    # output the command
    print(''.join(S))

输入生成

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

的值 作为输入给出的 N, M,和 V 统一生成为指定范围内的随机整数。
章鱼烧的初始位置生成如下:

首先初始化权重数组 w 尺寸 N \times N 带零。
重复以下过程 \mathrm{rand}(1, 5) 次:

  • 生成中心 (cx, cy) 其中 cx = \mathrm{rand\_double}(-1, N) 和 cy = \mathrm{rand\_double}(-1, N).
  • 生成系数 a 其中 a = \mathrm{rand\_double}(0, 1).
  • 生成 \sigma 其中 \sigma = \mathrm{rand\_double}(2, 5).
  • 对于每个方格 (i, j),添加 a \exp(-((i - cx)^2 + (j - cy)^2) / (2 \sigma^2)) to w_{i,j}.

然后,使用与所获得的权重成比例的概率 w_{i,j},摘录 M 无需放回的方块来确定章鱼烧的初始位置。

章鱼烧的目标位置以相同的方式生成。
如果包含在初始位置但不包含在目标位置(反之亦然)的方格数小于 M,重做初始位置和目标位置的生成。

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

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


示例输入 1

4 3 4
0000
1010
0000
0100
0100
0001
1000
0000

示例输出 1

4
0 1
1 1
1 2
0 0
RRL...PP
R..R..P.
DRR...P.
D.....PP

这是输入和输出的示例,在问题陈述的开头进行可视化。 该示例不满足输入约束。