← 返回题目列表

AtCoder · ahc019_a

A. 剪影块拼图创建

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

问题陈述

AtCoder 正在开发一种教育玩具,它可以组合块来创建具有指定轮廓的三维对象。 该玩具由一组多边形块组成,其中包括 1\times 1\times 1 立方体面对面连接,并有一对两个 2D 单色剪影图像。 如果您可以通过组合块来构建单个 3D 对象,并且所创建对象的两个轮廓(从正面和右侧观看)与给定的轮廓图像完全匹配,您将赢得游戏。

为了让孩子们能够长时间玩耍,我们想为一组积木准备多对剪影。 例如,左图所示的 6 个块组可用于创建两对剪影,如右图所示。

作为一名玩具设计师,您会得到两对前/右轮廓,您的任务是找到一组块,您可以从中构建两个具有给定轮廓对的对象,以及构建它们的方法。 由于儿童可能会意外吞下小块,因此最好只由少量大块组成。

详细的拼图规则

  • 你不必使用所有的块(但如果你这样做你会得到更好的分数)。
  • 每个块可以绕 x 轴、y 轴和 z 轴旋转 90 度,但不能翻转。
  • 块的排列必须使每个顶点都有整数坐标,并且不同的块不得具有正的公共体积。
  • 构造的对象不必连接。为了简单起见,我们假设浮动排列也是可能的(您可以将其解释为存在大量额外的透明块,这些透明块可用于支撑块)。

关于剪影

从左到右取 x 轴,从前到后取 y 轴,从上到下取 z 轴。 我们假设所有块都在一个立方区域内,该区域具有 (0,0,0) 和 (D,D,D) 作为对角。 我们定义一个三维01数组 b(x,y,z) as b(x,y,z)=1 如果某个块占据了具有 (x,y,z) 和 (x+1,y+1,z+1) 作为对角,并且 b(x,y,z)=0 否则。 那么,从正面看的剪影就是一个二维的01数组 f(z,x) 定义如下。

\[ f(z,x)=\begin{情况} 1&(\sum_{y=0}^{D-1}b(x,y,z)\geq 1)\\ 0&(\sum_{y=0}^{D-1}b(x,y,z)=0) \结束{案例} \]

同样,从右侧看到的剪影是一个二维01数组 r(z,y),定义如下

\[ r(z,y)=\begin{情况} 1&(\sum_{x=0}^{D-1}b(x,y,z)\geq 1)\\ 0&(\sum_{x=0}^{D-1}b(x,y,z)=0) \结束{案例} \]

评分

让 v_1,\cdots,v_n 是所创建的玩具组中每个块的体积。 这里,块的体积等于块的数量 1\times 1\times 1 它包含立方体。 每个块必须是连接的,即它所包含的每个立方体都必须可以通过移动共享面来到达。 如果存在断开的块,则判断为 WA。 请注意,通过组合块创建的 3D 对象可以断开连接。

对于 i第一对剪影 (i=1,2),让 r_i 是输出 3D 对象中未使用的块的体积总和。 让 S 是两个对象中使用的块集。 然后就可以得到如下的评价值。 评价值越低越好。

\[ \mathrm{round}\left(10^9\times \left(r_1+r_2+\sum_{i\in S} \frac{1}{v_i}\right)\right) \]

例如,如果该组块由体积为 5 的块 A、体积为 3 的块 B 和体积为 2 的块 C 组成,并且如果第一组轮廓由可使用 A 和 B 创建的 3D 对象实现,第二组轮廓由可使用 A 和 C 创建的 3D 对象实现,则所得评估值为 \mathrm{round}\left(10^9\times \left(2+3+1/5\right)\right).

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

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

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

测试用例数量

  • 临时测试:50
  • 系统测试:2000年。我们将发布 种子.txt (sha256=08db725cbdc37734a2e8fbe5bc0cbc1e95d7a68933b7f43dcdd0ffc3d2a95e34) 比赛结束后。
  • 系统测试包含 200 每个的输入 D=5,6,\cdots,14,其中 D 是每个轮廓的尺寸。
  • 种子 = 0 的输入是手动创建的,不包含在临时或系统测试中。

关于相关评价体系

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

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

关于执行时间

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


输入

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

D
f_1(0,0) \cdots f_1(0,D-1)
\vdots
f_1(D-1,0) \cdots f_1(D-1,D-1)
r_1(0,0) \cdots r_1(0,D-1)
\vdots
r_1(D-1,0) \cdots r_1(D-1,D-1)
f_2(0,0) \cdots f_2(0,D-1)
\vdots
f_2(D-1,0) \cdots f_2(D-1,D-1)
r_2(0,0) \cdots r_2(0,D-1)
\vdots
r_2(D-1,0) \cdots r_2(D-1,D-1)
  • D 是剪影图像的尺寸并且满足 5\leq D\leq 14.
  • f_i,r_i 是 i-第对轮廓图像,其中 f_i 是从正面看的剪影, r_i 是从右侧看到的剪影。每个都是01大小的矩阵 D\times D 给出为 D 01 字符串长度 D。这些值的含义请参见上一节“关于轮廓”。
  • 对于每个轮廓,所有 1 个元素形成一个连通分量。
  • 对于 z=0,\cdots,D-1,它认为 f_i(z,0)+\cdots+f_i(z,D-1)\geq 1 和 r_i(z,0)+\cdots+r_i(z,D-1)\geq 1。此条件保证始终存在与指定的轮廓对匹配的 3D 对象。

输出

让 n 是块的总数。 对应的块排列 i第对剪影使用三维数组表示如下 b_i(x,y,z) 尺寸 D\times D\times D.

b_i(x,y,z)=k 如果 k (1\leq k\leq n)-th 块占据具有 (x,y,z) 和 (x+1,y+1,z+1) 作为对角,并且 b(x,y,z)=0 如果没有任何块占据该区域。

由于块无法重新整形,因此两个块中都会出现相同编号的块 i=1,2 必须具有相同的形状,即它们必须能够通过旋转和平移完美匹配。

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

n
b_1(0,0,0) b_1(0,0,1) \cdots b_1(D-1,D-1,D-1)
b_2(0,0,0) b_2(0,0,1) \cdots b_2(D-1,D-1,D-1)

在这里, (x\times D^2+y\times D+z)- 第一个输出 b_i is b_i(x,y,z)。 对于每个 i=1,\cdots,n, i-th 块必须至少用于以下之一: b_1 or b_2。如果有一个块没有被使用,则判断为 WA.

显示示例

示例解决方案

这是 Python 中的示例解决方案。 在这个程序中,目标轮廓是通过放置一个大小为 1\times 1\times 1 对于所有人 (x,y,z) 这样 f(z,x)=1 和 r(z,y)=1.

D = int(input())
f = [[] for i in range(2)]
r = [[] for i in range(2)]
for i in range(2):
    for k in range(D):
        f[i].append(input())
    for k in range(D):
        r[i].append(input())

b = [[0 for j in range(D * D * D)] for i in range(2)]
n = 0
for i in range(2):
    for x in range(D):
        for y in range(D):
            for z in range(D):
                if f[i][z][x] == '1' and r[i][z][y] == '1':
                    n += 1
                    b[i][x * D * D + y * D + z] = n

print(n)
print(' '.join(map(str, b[0])))
print(' '.join(map(str, b[1])))

输入生成

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

的一代 D

我们生成 D by D=\mathrm{randint}(5,14).

的一代 f,r

首先,我们生成以下值,这些值确定要生成的轮廓的特征。

  • p(0)=0
  • p(1)=D^{\mathrm{randdouble}(-1,1)}
  • p(2)=D^{\mathrm{randdouble}(-1,1)}
  • p(3)=D^{\mathrm{randdouble}(-0.5,1.5)}
  • p(4)=D^{\mathrm{randdouble}(-0.5,1.5)}

接下来,我们生成每个 f_1,r_1,f_2,r_2 如下。

让 g 是要生成的轮廓数组并用以下命令对其进行初始化 g(z,x)=0 对于所有人 (z,x)。 生成一个值 m=\mathrm{randint}(2D,\lfloor D^2/2\rfloor) 代表数量 1。 生成 z=\mathrm{randint}(0,D-1) 和 x=\mathrm{randint}(0,D-1),然后设置 g(z,x)=1。 重复以下过程,直到达到 1 变为 m.

对于每个 (z,x),让 d(z,x) 是相邻的数量 1 在四个方向。 选择 (z,x) 这样 g(z,x)=0 概率与 p(d(z,x)) 并更新 g(z,x)=1.

当数量 1 变为 m,检查是否 \sum_{x=0}^{D-1}g(z,x)\geq 1 对于所有人 z=0,\cdots,D-1,如果没有,则重新初始化 g to 0 并重试生成过程 m.

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

比赛期间,您可以在 Twitter 上分享提供的 Seed=0 可视化工具的输出图像 (PNG)。 您必须使用指定的标签和公共帐户。您只能共享seed=0 的可视化结果和分数。请勿分享视频、输出本身、其他种子的分数或提及解决方案或讨论。

共享图像列表


示例输入 1

5
10001
11011
11111
10101
10001
01110
11011
10000
11011
01110
11110
00011
01110
11000
11111
11110
00011
01110
00011
11110

示例输出 1

19
0 1 2 3 0 4 5 0 3 3 6 0 0 0 3 7 7 0 3 3 0 7 0 8 0 0 5 9 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 9 10 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 12 12 0 13 0 0 12 14 0 0 0 0 14 0 0 0 14 14 0 0 0 14 0
15 0 0 0 3 14 0 0 0 3 0 0 0 0 9 16 0 0 9 9 0 0 0 17 0 0 0 0 0 0 14 0 10 0 3 14 0 10 0 9 0 0 0 18 0 0 0 0 0 0 0 0 0 0 3 0 0 12 0 3 14 0 12 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 12 0 0 14 0 7 0 0 0 7 7 0 5 0 19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 7 0 0 5 0 0 0 0 0