← 返回题目列表

AtCoder · hokudai_hitachi2019_1_b

B. 问题B

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

问题设置

概述

  • 概念: 在本次编程竞赛中,您将运行送货服务。客户将向您的商店下订单。每个订单都有一个独特的 \text{ID} 并应交付给相应的客户。您的送货服务拥有一辆车。汽车将从商店取出订购的商品并将其交付给顾客。
  • 分数: 您的目标是在给定的时间内尽快交付尽可能多的物品 T_{\text{max}}。 (订单预计截止到 0.95 \times T_{\text{max}}).
  • 约束: 在本次比赛中,您可以放入车内的物品数量没有限制。然而,物品只能在下订单后从商店取货才能装载到车上。
  • 问题 A/B: 在问题 A 中,所有订单位置和时间都提前提供给参赛者,参赛者算法应优化汽车的动作,以尽可能快地完成尽可能多的交付。另一方面,在问题B中,订单出现在网上,即出现新订单,同时您移动汽车以尽可能快地交付尽可能多的货物。
overview

时间和空间规范:

  • 时间: 在本次比赛中,我们通过整数值对时间进度进行建模 0 \le t < T_{\text{max}}.
  • 地图: 在本次比赛中,我们通过简单、无向且连通的图对地图进行建模 G=(V, E),由一组顶点组成 V 和一组边 E
  • 商店和顾客地点: 顶点 u \in V 标记为 1 to |V| 和顶点 u=1 表示您的商店的位置,而顶点 u = 2,...,|V| 表示潜在客户的位置。在这里, |V| 表示集合的元素数量 V.
  • 街道: 每条边 \left\{ u, v \right\} \in E 表示连接顶点的街道 u, v \in V。相应的长度由整数边权重给出 d_{u, v} \ge 1.
  • 图表创建: 基于随机种子生成地图的算法在以下伪代码中指定。有关更多详细信息,请参阅下面的示例代码。
伪代码: 地图图形生成器
  • 输入:|V|, |E|, \mathrm{MaxDegree}=5
  • 2d 顶点网格:
    • 首先求最大整数 R>0 这样 |V| = R^{2} + r,与 r 是可能的最小非负整数。
    • 然后我们绘制点 (x, y) 在 2d 顶点网格上 (0 \leq x, y \lt R).
    • 对于每个点 (x, y) 添加统一随机偏移 dx, dy \in [0, 1] ,给出最终顶点位置 (x + dx, y + dy)\in [0,R] \times [0,R].
    • 最后,添加剩余的 r 顶点位于均匀随机位置 (x, y) 与 0 \leq x, y \leq R.
    • 顶点标签 u \in V 通过随机洗牌分配。店铺是顶点 u=1.
  • 我们如何创建高速公路:
    • 为了生成高速公路网络,我们创建一个完整的图 顶点集上的 G_{\text{comp}} 在顶点集上 u \in V,分配每个顶点对 u, v \in V \times V 欧几里德距离 W_{u, v} 作为边权重。
    • 接下来,我们构造一个 最小跨度 树 G_{\text{comp}}。的 |V|-1 最小生成树的边是图的高速公路网络 G。我们分配每条边 \left\{ u, v \right\} 边权重 d_{u,v} \leftarrow \lceil 2 \times W_{u, v} \rceil .
  • 我们如何添加支路:
    • 为了创建支路网络,我们相继添加 |E|-(|V|-1) 图形的边 G 如下:
      • 更新 \mathrm{cost}(u,v).
      • 顶点对之间 \left( u, v \right) \in V\times V,尚未通过边连接,选择具有最小的一对 \mathrm{cost}(u,v).
      • 分配边权重 d_{u,v} \leftarrow \lceil 4 \times W_{u, v} \rceil .
    • 在这里, \mathrm{cost}(u,v) 本质上基于顶点的欧几里德距离,优先连接附近度数较低的顶点。此外,优先考虑沿矩形网格的支路,以避免过多的桥梁。详细定义如下:
      • 定义 \mathrm{degree}(u),顶点的度数 u\in V 作为入射边的数量。
      • 定义 \mathrm{color}(u) 对于每个顶点 u\in V 按照原来的位置 (x,y) 在顶点网格上为:
        • If x+y 是偶数: \mathrm{color}(u) = 0
        • If x+y 是奇数: \mathrm{color}(u) = 1
        • 对于剩余的 r 顶点:分配颜色 \mathrm{color}(u) \in \left\{0,1\right\} 随机。
      • 定义一个因素 f(u,v) 如下:
        • If \mathrm{color}(u) 和 \mathrm{color}(v) 相同:设置 \mathrm{f}(u,v) = 5
        • If \mathrm{color}(u) 和 \mathrm{color}(v) 不同:设置 \mathrm{f}(u,v) = 1
      • 定义一个因素 g(u) 如下:
        • If \mathrm{degree}(u) \lt \mathrm{MaxDegree} :设置 g(u)=1
        • If \mathrm{degree}(u) \geq \mathrm{MaxDegree} :设置 g(u)=\infty
      • 最后,成本定义如下:
        • \mathrm{cost}(u,v) = W_{u,v}\times \mathrm{degree}(u) \times \mathrm{degree}(v) \times f(u,v) \times g(u) \times g(v).
  • 我们如何分配订单频率:
    • 分配每个顶点 u \in V 订单频率 f_u \in \left\{0,1,2\right\}.
    • 初始化商店顶点的订单频率: f_1 \leftarrow 0.
    • 初始化其他顶点的顺序频率: f_u \leftarrow 1
    • 现在确定阶次频率为 2 的顶点。为此绘制一个均匀的随机中心点 c=(c_x,c_y)\in [R/4,3R/4]\times[R/4,3R/4] 然后对于所有顶点 u=2,...,|V| 做:
      • If \mathrm{EuclideanDistance}(c,u)\le R/8 + \mathrm{uniformRandom}[0,R/8]: f_{u} \leftarrow 2

汽车位置和移动规范:

为了进行送货,您将操作一辆送货车,它可以按照以下指定的方式占据位置并进行移动。

  • Car position: 汽车通常可以采取两种类型的位置:

    • 在顶点上 u \in V.
    • 在边缘 \left\{ u, v \right\} \in E。更具体地说,它位于一个距离 x (0 \lt x \lt d_{u, v}) 来自 u to v .
  • 汽车移动: 每一步 0 \le t < T_{\text{max}} 您必须选择以下操作之一才能控制您的送货车。

    • stay:停留在当前位置。
    • move w:向顶点迈出一步 w \in V.

    如果选择 move w, w 必须遵守以下约束。不遵守这些限制会导致错误的答案 WA.

    • w 必须是一个顶点,即 w \in V.
    • 如果汽车位于顶点 u \in V,必须有一条边连接 u 和 v,即 \left\{ u, w \right\} \in E.
    • 如果汽车在边缘 \left\{ u, v \right\} \in E, w must either be w = u or w = v.

Car position and moves

订单、交货和限制:

  • 订单: 在整个比赛中,每个订单都具有三个数量的特征:唯一的订单 ID、顶点 v \in V 表示订单目的地和订单时间 t 订单出现的位置。详细格式见下文。
  • 订单生成: 每次 0 \le t \le T_{\text{last}} = 0.95 \times T_{\text{max}} 最多可出现 1 个新订单 p_{\text{order}}(t)。如果有订单,则订单目的地 i 从顶点集中选择 V 概率与订单频率成正比 f_i。有关详细信息,请参阅下面的伪代码或下面的示例代码。
伪代码: 订单生成
  • 输入: 最后下单时间 T_{\text{last}} 和平均订单概率 p_{\text{order}}(t).
  • 初始化: \mathrm{ID} \leftarrow 0.
  • 对于每个步骤 t = 0, ..., T_{\text{last}} 做:
    • 生成统一随机数 r \in [0,1] .
    • If r \le p_{\text{order}}(t) :
      • 选择顶点位置 u \in V 随机,概率与订单频率成正比 顶点的 f_{u} 。
      • \mathrm{ID} \leftarrow \mathrm{ID} + 1
      • 下单(新订单ID、下单时间 t,顶点位置 u \in V )
    • 其他: 未下订单
  • 注意: 平均订单概率定义如下:
  • p_{\text{order}}(t) = \begin{cases} t / T_{\text{peak}}, & \text{if } 0\le t \lt T_{\text{peak}}, \\ (T_{\text{last}} - t) / (T_{\text{last}}- T_{\text{peak}}), & \text{if } T_{\text{peak}} \le t \lt T_{\text{last}}, \\ 0, & \text{if } T_{\text{last}} \le t, \end{cases}
  • 其中 T_{\text{last}}:=0.95 \times T_{\max} 和 T_{\text{peak}} 是从区间中随机均匀抽取的 [0, T_{\text{last}}].
  • 注:值 T_{\text{peak}} 将不会作为输入给出。
  • 交货: 要交付订单,参赛者必须在下订单后执行以下步骤:
    • (1st) 将车移至商店: 注意:将汽车移入商店时,所有下单时间小于或等于当前时间的订单都会转移到汽车中。另一方面,尚未出现的订单则无法放入车内。
    • (2) 将车移至客户位置: 要完成交付,请将汽车移动到客户位置的顶点。注意:尚未转移到车上的订单,即使您到达了顾客位置,也不会被交付。
constraint image
  • 限制: 在整个比赛中,我们假设每个订单都有一个唯一的 \text{ID} 并应交付给相应的客户。进一步假设车内可以下无限数量的订单。

评分

  • 比赛期间,提交的总分是通过将 30 个输入案例的提交分数相加来确定的。
  • 比赛结束后将进行系统测试。为此,参赛者 最后提交 将通过对 100 个以前未见过的输入案例提交的分数求和来进行评分。
  • 对于每个输入案例,分数计算如下:

    \text{Score} = \sum_{i \in D} {(T_{\text{max}})}^{2} - {(\mathrm{waitingTime}_i)}^{2},

    这里我们使用以下定义:
    • D :交付的订单集直到 t=T_{\text{max}}
    • 的等待时间 i第订单: \mathrm{waitingTime}_i = \mathrm{deliveredTime}_i - \mathrm{orderedTime}_i.
    • 请注意,输入情况给出输出 WA 将收到 0 点。

问题B的详情:

问题 B 是 互动 竞赛,参赛者代码连续接收来自主机代码的新生成和交付订单的更新,同时通过在每一步中将汽车移动到相邻位置来为客户提供服务 t=0,...,T_{\max}-1。详细描述了参赛者和主机代码交互的精确流程如下所示。

参赛者代码 主机代码
生成并输出图表 G
+ 时间 t: 生成并输出新订单
+ 时间 t:如果在商店,输出装载到汽车中的订单
+ 时间 t: 确定并输出一步棋
+ 检查移动的可行性;如果移动不可行:输出 NG,如果可行:输出 OK
+ 时间 t+1:更新并输出已交付物品的信息(如果有)

注意:主机代码仅输出图形一次。表左侧用“+”标记的过程对于整数迭代重复 t in t = 0,..., T_{\max} - 1.


标准 IO 的输入/输出格式

首先,主机代码会输出一个图表 G,阶次频率 f_{i} 对于每个顶点 i,与订单出现在顶点的概率成正比 i,以及总步数 T_{\max}.

|V| |E|
u_1 v_1 d_{u_1, v_1}
u_2 v_2 d_{u_2, v_2}
\vdots
u_{|E|} v_{|E|} d_{u_{|E|}, v_{|E|}}
f_1 f_2 \ldots f_{|V|}
T_{\max}
  • 第一行: |V| 顶点数, |E| 边数
  • 下一个 |E| 线:图形的边缘。特别是, i第行表示顶点 u_i 和 v_i 形成一条边,以及相应的边权重 d_{u_i, v_i}.
  • 下一行:订单频率 f_i 确定顶点处订单的概率 i as p_{i}=\frac{f_{i}}{\sum_{i}f_{i}}.
  • 最后一行:汽车更新总数 T_{\max}.

时间 t 我们首先通过标准输入获取以下信息。

N_{\text{new}}
\mathrm{new\_id}_1 \mathrm{dst}_1
\mathrm{new\_id}_2 \mathrm{dst}_2
\vdots
\mathrm{new\_id}_{N_{\text{new}}} \mathrm{dst}_{N_{\text{new}}}
N_{\text{put}}
\mathrm{put\_id}_1
\mathrm{put\_id}_2
\mathrm{put\_id}_{N_{\text{put}}}
  • N_{\text{new}} 代表该时间出现的新订单数 t.
  • 下一个 N_{\text{new}} 行给出了新生成的订单信息。的 i第订单信息表示订单ID 新订单的 \mathrm{new_{id}}_i ,同时 \mathrm{dst}_i 表示客户希望将订单交付到的顶点。
  • N_{\text{put}} 代表当时转移到车上的物品数量 t.
    • 如果汽车不在商店的顶点 N_{\text{put}} 将为零。
  • 后续 N_{\text{put}} 行表示新加载项目的订单信息。特别是, i第行表示车上装载的产品对应的订单ID为 \mathrm{put_{id}}_i.

接下来,为了将送货车移动到相邻位置,参赛者代码每次都必须 t (0 \leq t \lt T_{\max})输出以下内容 \mathrm{command} 到标准输出。

\mathrm{command}

在这里, \mathrm{command} 必须采用以下形式

  • 如果您想让汽车 stay 在当前位置,发送 -1 到标准输出
  • 如果你想让汽车向邻近的顶点移动一步 move w,发送 w 到标准输出

注意:如果您选择 move w, w 必须满足以下所有条件。如果违反以下任一条件,主机代码将输出 NG 并且参赛者应终止该计划,最终导致 WA (不正确)。

  • w 是一个顶点索引 w \in \left\{1, ... , |V|\right\}
  • 如果汽车位于顶点 u,边缘 \left\{ u, w \right\} \in E 必须存在
  • 如果汽车处于边缘 \left\{ u, v \right\}, w must either be w = u or w = v

在您执行操作后的时间 t 发送到标准输出,主机代码将发送以下有关时间的信息 t + 1 到标准输入。

\mathrm{verdict}
N_{\text{achieve}}
\mathrm{achieve\_id}_1
\mathrm{achieve\_id}_2
\vdots
\mathrm{achieve\_id}_{N_{\text{achieve}}}
  • \mathrm{verdict} 是一个字符串,指示您当时的操作是否 t 有效。它可以是以下两个选项之一。
    • OK:表明你的行动是可行的
    • NG:表示您的操作不可行。如果您收到此输入, 您必须立即终止该程序。 如果立即终止,则保证为 WA(不正确)。如果不立即终止,则行为未定义。
  • N_{\text{achieve}} 代表该时刻已发货的订单数量 t.
    • 如果汽车不在交付顶点,则没有订单已交付并且 N_{\text{achieve}}=0.
  • 后续 N_{\text{achieve}} 行表示已交付的订单。特别是, i第行表示订单ID \mathrm{achieve\_{id}}_i.

最后,在最后一步之后接收到主机代码的标准输入后 T_{\max} 您必须立即终止该程序。

约束

I/O 限制

  • 通过标准输入给出的所有数字都是整数。
  • 所有输出必须是整数
  • T_{\text{max}} = 10000
  • 200 \leq |V| \leq 400
  • 1.5 |V| \leq |E| \leq 2|V|
  • 1 \leq u_{i}, v_{i} \leq |V| (1 \leq i \leq |E|)
  • 1 \leq d_{u_i, v_i} \leq \lceil 4\sqrt{2|V|} \rceil (1 \leq i \leq |E|)
  • 给定的图没有自环,没有重边,并且保证是连通的。
  • f_1 = 0
  • f_i \in \left\{ 1, 2 \right\} (2 \leq i \leq |V|)
  • \mathrm{verdict} \in \left\{ \text{"OK"}, \text{"NG"} \right\}
  • 0 \leq N_{\text{new}} \leq 1
  • 1 \leq \mathrm{new\_id}_{i} \leq T_{\text{last}}+1 (1 \leq i \leq N_{\text{new}})。注:如果所有订单均按上述订单生成规则生成,则订单总数最多为 T_{\text{last}}+1。因此,可能的范围为 \mathrm{new\_id}_{i} 应该来自 1 to T_{\text{last}}+1.
  • 订单 ID \mathrm{new\_{id}}_i 是独一无二的。
  • 2 \leq \mathrm{dst}_i \leq |V| (1 \leq i \leq N_{\text{new}})
  • 参赛者在某个时刻输出到标准输出的整数 t must either be -1 or 1 \leq w \leq |V|

输入/输出示例

时间 参赛者 主机代码 说明
5 7
1 2 5
5 3 4
2 4 8
1 5 1
2 3 3
4 5 3
4 3 9
0 1 1 5 5
500
首先,主机代码通过标准输入提供图形数据。在这个例子中,图表有 |V| = 5 顶点和 | E | = 7 边缘。接下来,在一行中给出每个顶点的阶频率。最后, 给出了 T_{\max} 。
0 \rightarrow 1
1
1 5
1
1
时间 t=0 我们收到一份订单。该订单有ID= 1 并且应该传递到顶点 5。由于您的汽车当前位于顶点一,因此订单将自动转移到您的汽车中。这样,当您的汽车到达商店时,当前和之前下的所有订单都会自动加载到您的汽车中。
2
你决定向顶点移动一步。
OK
0
第一行表明你的举动是可行的。第二行显示没有订单已交付。
1 \rightarrow 2
1
2 2
0
1 个新订单(ID =2,交付顶点 =2)已发生。你的车在顶点之间的边缘 1 和 2,因此零订单已转移到您的汽车上。
-1
您决定将您的车保持在同一位置。
OK
0
你的举动是有效的。不会交付任何订单,因为您不在交付项目位置。
2 \rightarrow 3
1
3 4
0
一个新订单(ID =3,交付顶点 =4)已出现。
1
你决定向顶点后退一步 1。这样您就可以掉头了。
OK
0
尚未交付任何订单。
3 \rightarrow 4
0
2
2
3
由于汽车已返回商店,因此订单 ID 2 和 3 对应的产品已装载到汽车上。
5
参赛者决定向顶点 5 移动一步。
OK
1
1
自从您到达顶点 5 以来,带有 ID 的订单 1 已交付。
4 \rightarrow 5
0
0
没有新订单。
5
参赛者决定向顶点移动一步 5.
NG
输入无效,您应该终止程序。

使用标准输出

将移动指令返回到标准输出时,请使用flush命令。作为示例,考虑您要输出的情况 -1。这是在一些主要编程语言中执行此操作的方法。

C++

std::cout << "-1" << std::endl;

Java

System.out.println("-1");

Python 3.4

print("-1", flush=True)

示例代码 B

用于生成输入样本、在本地参赛者环境中评分和测试的软件工具包以及适合初学者的示例代码 通过以下方式提供 链接。此外我们还提供 可视化软件 参赛者成绩。

可视化器

步骤
FPS
命令
Δ
分数