← 返回题目列表

AtCoder · ahc016_a

A. 图形

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

故事

天才发明家高桥发明了名为“Graphorean”(Graph + DeLorean)的时间机器,可以发送 图 过去了。 有了这台机器,他计划通过玩赌场轮盘赌并将中奖号码信息发送到玩之前的时间来致富。 如果他成功了,他将移动到他成功选择中奖号码的世界线并变得非常富有。

因为机器无法直接发送中奖号码,所以他需要先将号码转换为图形(编码),然后发送,最后将图形转换回数字(解码)。 机器发送图会丢失顶点数信息并引入噪声,因此他必须开发编码/解码方法,以便正确恢复该数。 为了收到一个图表 N 顶点,他必须设置一个整数 N 到机器。 因此,必须提前确定要发送的图的顶点数。

时间机器一旦使用就会坏掉,所以不能容忍失败。 因此,他决定提前进行模拟,预估成功概率,准备一个成功概率尽可能高的编解码方法。 此外,由于发送大图需要大量能量,因此希望图的大小尽可能小。 请帮助他。

问题陈述

给定一个整数 M 和错误率 \epsilon,确定一个整数 N 满意 4\leq N\leq 100 和输出 N- 顶点无向图 G_0,G_1,\cdots,G_{M-1}。 图表可能会断开。 然后处理以下查询 100 次。

在 k-第一个查询,您将得到一个 N- 顶点无向图 H_k. H_k 是根据一些生成的图表 G_{s_k} 如下。

  1. 初始化 H_k=G_{s_k}.
  2. 对于每个 (i,j) 与 0\leq i<j\leq N-1, 是否翻转 H_k 包含边缘 (i,j) 有概率 \epsilon.
  3. 随机打乱顶点的顺序 H_k.

收到后 H_k,从哪个图预测 G_{s_k} 生成,并输出预测值 t_k of s_k.

评分

让 E 是失败预测的数量。 那么测试用例的分数是

\[ \mathrm{round}\left(10^9\times \frac{0.9^E}{N}\right) \]

测试用例数量

  • 临时测试:50
  • 系统测试:2000年。我们将发布 种子.txt (sha256=4093b6cb740beea16eb0ecf55120ca6ca6fbef18015ea4a863e64d0bea3de91d) 比赛结束后。
  • 系统测试每对最多包含一个测试用例 (M,\epsilon).

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

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

关于相关评价体系

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

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

关于执行时间

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

输入和输出

首先,有关问题设置的信息从标准输入以以下格式给出。

M \epsilon
  • M 是表示图数量的整数,满足 10\leq M\leq 100.
  • \epsilon 是代表错误率的实数,它是 0.01 并满足 0.00\leq \epsilon\leq 0.4.

读取输入后,输出 M 图表 G_0,G_1,\cdots,G_{M-1} 按以下格式转换为标准输出。

N
g_0
\vdots
g_{M-1}
  • N 是一个整数,表示每个图中的顶点数,它必须满足 4\leq N\leq 100.
  • 每个 g_k 是一个长度为的字符串 N(N-1)/2,代表 k第一张图 G_k 如下。对于每个 (i,j) 满意 0\leq i<j\leq N-1,表示边的存在 (i,j) as 1 if G_k 包含边缘 (i,j) 和 0 如果没有,则使用一个字符,然后按照字典顺序排列 (i,j)。例如,当 N=4,字符串 100101 表示一个图表 4 顶点连接在一条直线上。

输出后,您必须刷新标准输出。 否则,提交的内容可能会被判定为 TLE。 输出后 M 图表,重复以下过程 100 次。

在 k-th 进程,您将获得一个 N- 顶点图 H_k 表示为字符串 N(N-1)/2 01 字符的格式与上述相同,位于标准输入的单行中。 收到后 生成 H_k,从哪个图预测 G_{s_k} H_k 并输出预测 t_k (0\leq t_k\leq M-1) of s_k 到标准输出。 输出后面必须有一个新行,并且您必须刷新标准输出。 在输出以下内容之前,不会给出 请注意 H_{k+1} 在你输出之前不会给出 t_k.

示例解决方案

这是 Python 中的示例解决方案。 在这个程序中,我们设置 N=20,以及每个图 G_k 包含 k 边缘。 对于每个 H_k,我们计算边的数量 m 和输出 \min(m, M-1).

M, eps = input().split()
M = int(M)
eps = float(eps)
print(20)
for k in range(M):
    print("1" * k + "0" * (190 - k))

for q in range(100):
    H = input()
    t = min(H.count('1'), M - 1)
    print(t)

输入生成

让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。 M 是由生成的 \mathrm{rand}(10,100). \epsilon 是由生成的 0.01\times \mathrm{rand}(0,40)。 每个 s_k 是由生成的 \mathrm{rand}(0,M-1).

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

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

工具使用的输入/输出文件规范

提供给本地测试器的输入文件具有以下格式。

M \epsilon
s_0
\vdots
s_{99}
\mathrm{seed}

最后 \mathrm{seed} 是用于生成噪声的随机种子值。 由于每个图 H_0,\cdots,H_{99} 取决于输出图 G_0,\cdots,G_{M-1},输入文件仅包含随机种子值。

本地测试器将程序的输出直接写入输出文件。 您的程序可能会输出以以下内容开头的注释行 #。 可视化工具的 Web 版本显示带有相应查询的注释行,这对于调试和分析可能很有用。 由于判断程序会忽略所有注释行,因此您可以提交按原样输出注释行的程序。

以下开头的注释行在可视化工具中具有特殊含义。

  • #v:您可以告诉可视化工具您已经预测了该顶点 i in H_k 对应于顶点 p_i in G_{t_k} ,按以下格式输出。
#v p_0 \cdots p_{N-1}
  • #h:如果您不使用提供的本地测试仪,您可以更换 H_k 由可视化工具通过以表单输出的方式显示 #h 100101 001101。左边是添加噪声后的图 G_{s_k},右边是打乱顶点排序后的图。