← 返回题目列表

AtCoder · future_contest_2022_qual_a

A. 项目负责人

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

故事

你被聘为F公司的项目负责人。您的工作是将任务适当地分配给团队成员。 当前的项目由多项任务组成。 团队成员完成任务的预期天数取决于团队成员的技能水平和任务所需的技能水平。 你经验丰富,能够准确估计每项任务所需的技能水平,但由于你刚刚加入团队,你根本不知道每个团队成员的技能水平。 请合理分配任务,同时逐步评估团队成员的技能水平。

问题陈述

您想要分配 N 任务 M 团队成员。 您最多可以将每个任务分配给一名团队成员,并且一旦您将任务分配给团队成员,您就无法再为其分配其他任务,直到他/她完成该任务。 有 K 技能类型。 每个团队成员 j 有一个非负整数向量 \bm{s_j} = (s_{j,1},\cdots,s_{j,K}) 代表技能级别,以及每个任务 i 有一个非负整数向量 \bm{d_i} = (d_{i,1},\cdots,d_{i,K}) 代表所需的技能水平。 其中,技能等级 \bm{s_1},\cdots,\bm{s_M} 未作为输入给出。

我们定义 w_{i,j}:=\sum_{k=1}^K \max(0,d_{i,k}-s_{j,k})。 那么,需要 t_{i,j} 团队成员的天数 j 完成任务 i,其中 t_{i,j} 定义如下。

  1. If w_{i,j}=0, t_{i,j}=1.
  2. If w_{i,j}>0, t_{i,j}=\max(1,w_{i,j}+r_i),其中 r_i 是一个均匀随机整数 -3 和 3,包括在内。

当任务执行时 t 天从当天开始 d,任务将在当天结束时完成 d+t-1。 任务之间存在依赖关系,在开始任务之前,其所有依赖任务必须在前一天结束时完成。 请尽可能在几天内完成所有任务。

输入和输出

有关每个输入值的范围,请参阅输入生成。

执行开始时,任务数 N,团队成员数量 M, 技能数量 K,依赖项数量 R,每项任务所需的技能级别 \bm{d_1},\cdots,\bm{d_N},以及依赖任务对的列表 (u_1,v_1),\cdots,(u_R,v_R) 由标准输入以以下格式给出。

N M K R
d_{1,1} \cdots d_{1,K}
\vdots
d_{N,1} \cdots d_{N,K}
u_1 v_1
\vdots
u_R v_R

(u_i,v_i) 表示该任务 v_i (1\leq v_i\leq N)取决于任务 u_i (1\leq u_i\leq N)并且 u_i 必须在开始前完成 v_i。 它满足 u_i<v_i,并且相同 (u_i,v_i) 对在输入中最多出现一次。

然后,从第一天开始,每天执行以下两个过程。

首先,将成对的列表输出到标准输出 (a_1,b_1),\cdots,(a_m,b_m) 使得团队成员 a_i (1\leq a_i\leq M) 启动任务 b_i (1\leq b_i\leq N)当天按以下格式一行。

m a_1 b_1 \cdots a_m b_m

输出后,您必须刷新标准输出。 否则,提交的内容可能会被判定为 TLE .

接下来是当天结束时完成任务的团队成员列表 f_1,\cdots,f_n (1\leq f_1<\cdots<f_n\leq M) 在标准输入的一行中以以下格式给出。

n f_1 \cdots f_n

如果所有任务都完成或当天 2000 结束,一行仅包含 将给出 -1 作为输入,而不是上述输入,并且您应该退出程序。

示例

日 输出 输入
先前信息
3 2 2 1
0 1
2 0
1 1
2 3
第一天
2 1 1 2 2
1 1
第 2 天
0
1 2
第 3 天
1 1 3
0
第 4 天
0
0
第 5 天
0
-1

评分

如果您在一天结束时完成所有任务 D (1\leq D\leq 2000),您将获得分数 N+2000-D。 如果您未能完成期限内的所有任务 2000 天,您将获得分数 T,其中 T(<N) 是已完成任务的总数。

测试用例数量

  • 临时测试:50
  • 系统测试:3000。我们将发布 种子.txt (md5=a90d2e3883a546dfb66a4215b8d7a995) 比赛结束后。

提交的分数是每个测试用例的总分。 在临时测试中,如果您的提交产生非法输出或某些测试用例超出时间限制,则提交本身将被判定为 WA or TLE ,提交的分数将为零。 在系统测试中,如果您提交的测试用例产生非法输出或超出时间限制,则只有这些测试用例的分数为零。 注意,如果你的程序异常终止,可能会被判断为 WA 而不是 RE.

关于执行时间

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

输入生成

让 \mathrm{randint}(L, U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。 让 \mathrm{randdouble}(L,U) 是一个生成均匀随机浮点数的函数 L 和 U。 让 \mathrm{randnormal}() 是一个生成随机值的函数 标准正态分布.

的一代 N, M, K,和 R

  • N=1000 (针对所有测试用例已修复)
  • M=20 (针对所有测试用例已修复)
  • K=\mathrm{randint}(10, 20)
  • R=\mathrm{randint}(1000, 3000)

的一代 d_{i,j}

对于每个 i=1,\cdots,N,我们生成 \bm{d_i} = (d_{i,1},\cdots,d_{i,K}) 如下。

我们生成 K维向量 (d_{i,1}',\cdots,d_{i,K}') 通过生成 d_{i,j}'=|\mathrm{randnormal}()|。 让 p_i=\frac{\mathrm{randdouble}(10,40)}{\sqrt{\sum_{j=1}^K d_{i,j}'^2}}。 然后,我们设置 d_{i,j}=\mathrm{round}(p_i d'_{i,j}).

的一代 s_{i,j}

对于每个 i=1,\cdots,M,我们生成 \bm{s_i} = (s_{i,1},\cdots,s_{i,K}) 如下。

我们生成 K维向量 (s_{i,1}',\cdots,s_{i,K}') 通过生成 s_{i,j}'=|\mathrm{randnormal}()|。 让 q_i=\frac{\mathrm{randdouble}(20,60)}{\sqrt{\sum_{j=1}^K s_{i,j}'^2}}。 然后,我们设置 s_{i,j}=\mathrm{round}(q_i s'_{i,j}).

的一代 (u_i,v_i)

从空集开始 E=\emptyset,我们生成一组依赖任务对 E=\{(u_1,v_1),\cdots,(u_R,v_R)\} 重复以下过程,直到 |E|=R.

生成 h=\mathrm{randint}(1,100) 和 v=\mathrm{randint}(h+1,N)。 让 u=v-h 并插入 (u,v) 进入 E.

工具

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

这些工具使用以下格式的输入文件,除了先验信息外,还包含隐藏信息:技能级别 \bm{s_i} 和天数 t_{i,j} 实际上需要团队成员 j 完成任务 i.

N M K R
d_{1,1} \cdots d_{1,K}
\vdots
d_{N,1} \cdots d_{N,K}
u_1 v_1
\vdots
u_R v_R
s_{1,1} \cdots s_{1,K}
\vdots
s_{M,1} \cdots s_{M,K}
t_{1,1} \cdots t_{1,M}
\vdots
t_{N,1} \cdots t_{N,M}

有了这些信息,您就可以实现与所提供的测试器等效的您自己的测试器,而不是使用所提供的测试器。

在程序的输出中,以以下开头的行 # 作为注释被忽略。 特别是,以 #s 被解释为以以下格式描述的技能水平的预测,并用于可视化。

#s i s_{i,1} \cdots s_{i,K}
预测可以输出任意多次,并且相同的预测 i 将被覆盖。 网络上的可视化工具提供了预测的动画。

例如,通过在示例所示的输出中插入注释行,您可以更新以下预测: s_1 to (0, 1) 第一天,预测 s_2 to (1, 0) 第 2 天。

2 1 1 2 2
#s 1 0 1
0
#s 2 1 0
1 1 3
0
0

判断时注释行也会被忽略,因此您可以提交相同的程序。

示例程序(Python)

# assign random tasks to team member 1.
import sys
import random
# Prior information
n, m, d, r = list(map(int, input().split()))
task_difficulty = []
for i in range(n):
    task_difficulty.append(list(map(int, input().split())))
task_dependency = [[] for _ in range(n)]
for i in range(r):
    temp = list(map(int, input().split()))
    task_dependency[temp[1] - 1].append(temp[0] - 1)
# -1: not started
#  0: started
#  1: completed
task_status = [-1] * n
# -1: not assigned
#  k: assigned task k (1 <= k <= N)
member_status = -1
day = 0
while True:
    day += 1
    output = [0]
    # random search for tasks
    if member_status < 0:
        tasklist = list(range(n))
        random.shuffle(tasklist)
        for task in tasklist:
            if task_status[task] != -1:
                continue
            ok = True
            for necessary in task_dependency[task]:
                if task_status[necessary] != 1:
                    # the dependent tasks have not been completed
                    ok = False
                    break
            if ok:
                # assign the task to team member 1
                task_status[task] = 0
                member_status = task
                output = [1, 1, task + 1]
                break
    str_output = map(str, output)
    print(" ".join(str_output))
    # After the output, you have to flush Standard Output
    sys.stdout.flush()
    temp = list(map(int, input().split()))
    if len(temp) == 1:
        if temp[0] == -1:
            # elapsed days == 2000, or all the tasks have been completed
            exit()
        else:
            # no change in state
            pass
    else:
        # one task has been completed
        task = member_status
        task_status[task] = 1
        member_status = -1