← 返回题目列表

AtCoder · ahc031_a

A. 活动大厅

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

故事

高桥管理着一个活动大厅。 这个活动大厅可以通过安装隔断分成几个矩形区域,每个区域出租给不同的团体。

您将获得几天的预订状态。 每次预订都会指定所需的路段面积,如果指定的路段面积小于指定面积,则会产生费用。 另外,安装和拆除隔板以改变部分的划分会产生基于隔板长度的成本。 请尽量减少总成本来运营活动厅。

问题陈述

有一个以网格表示的活动大厅,其垂直和水平长度均为 W。 让 (0,0) 是左上角网格点的坐标,并且 (i,j) 为网格点的坐标 i 向下平方并 从那里向右走 j 方块。 右下网格点的坐标为 (W, W).

您将获得以下预订状态 D 天。 每天预约人数均为 N,以及 k=0,1,\cdots,N-1当天第 次预订 d=0,1,\cdots,D-1 希望租用至少面积的矩形部分 a_{d,k}。 租用的矩形的形状和位置是灵活的,但它们必须与轴平行,并且每个顶点必须是一个网格点。 此外,同一天两个不同预订的矩形不得具有共同的正面积。 存在一些未出租的空置空间是可以接受的。

让 R_{d,k} 是矩形 k当天第 次预订 d 和 b_{d,k} 为其面积。 如果 a_{d,k}>b_{d,k},成本为 产生了 100\times (a_{d,k}-b_{d,k}) 。 如果 a_{d,k}\leq b_{d,k},不产生任何费用。

隔断必须沿着每个矩形的周边部分安装 R_{d,k} 不位于网格的周边,相反,分区不得存在于其他任何地方。 当天 d,您必须在 day 的配置中安装和删除分区 d-1 满足这个条件。 如果当天安装和拆除的分区总长度 产生了 d is L_d,成本为 产生了 L_d 。 不过,作为一个特例, 我们假设 L_0=0 第一天。

更准确地说, L_d 计算如下。 对于每个 d=0,\cdots,D-1 和每个水平线段 (i,j)-(i,j+1) (1\leq i\leq W-1, 0\leq j\leq W-1)在内部,不包括网格的周长,我们定义 H_{d,i,j}=1 如果它位于任何 R_{d,k},否则我们定义 H_{d,i,j}=0。 然后加1 L_d 对于每个 (i,j) 这样 H_{d-1,i,j}\neq H_{d,i,j}。 类似地,对于每个垂直线段 (i,j)-(i+1,j) (0\leq i\leq W-1, 1\leq j\leq W-1)位于任何 R_{d,k}, 我们定义 V_{d,i,j}=1,否则 V_{d,i,j}=0。 然后加1 L_d 对于每个 (i,j) 这样 V_{d-1,i,j}\neq V_{d,i,j}.

您的任务是确定要出租的矩形部分,以使总成本尽可能小。

评分

当总成本为 D 天是 C,您获得的绝对分数为 C+1. 绝对分数越低越好。

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

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

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

测试用例数量

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

关于相关评价体系

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

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

关于执行时间

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


输入

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

W D N
a_{0,0} \cdots a_{0,N-1}
\vdots
a_{D-1,0} \cdots a_{D-1,N-1}
  • 网格的水平和垂直长度 W 固定为 W=1000.
  • 天数 D 满足 5\leq D\leq 50.
  • 预约数量 N 每天满足 5\leq N\leq 50.
  • 所需区域 a_{d,k} 的 k当天第 次预订 d 是满足以下条件的整数值 1\leq a_{d,0}\leq \cdots\leq a_{d,N-1} 其总和满足 a_{d,0}+\cdots+a_{d,N-1}\leq W^2.

输出

出租左上角顶点有坐标的矩形时 (i_{d,k},j_{d,k}) 且其右下顶点有坐标 (i_{d,k}',j_{d,k}') 为 k当天第 次预订 d,按以下格式输出到标准输出。

i_{0,0} j_{0,0} i_{0,0}' j_{0,0}'
\vdots
i_{0,N-1} j_{0,N-1} i_{0,N-1}' j_{0,N-1}'
\vdots
i_{D-1,0} j_{D-1,0} i_{D-1,0}' j_{D-1,0}'
\vdots
i_{D-1,N-1} j_{D-1,N-1} i_{D-1,N-1}' j_{D-1,N-1}'

每个矩形必须满足 0\leq i_{d,k}\lt i_{d,k}'\leq W 和 0\leq j_{d,k}\lt j_{d,k}'\leq W。 如果不满足此条件,提交将被判定为 WA.

显示示例

示例解决方案

这是 Python 中的示例解决方案。 该程序输出 k左上角的第一个矩形 (k,0) 和右下角 (k+1,W).

# read input
W, D, N = map(int, input().split())
a = []
for d in range(D):
    a.append(list(map(int, input().split())))

# determine rectangles
rect = [[] for _ in range(D)]
for d in range(D):
    for k in range(N):
        rect[d].append((k, 0, k + 1, W))

# output
for d in range(D):
    for k in range(N):
        i0, j0, i1, j1 = rect[d][k]
        print(i0, j0, i1, j1)

输入生成

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

我们生成天数 D by D=\mathrm{rand}(5,50)。 我们生成预订数量 N 每天由 N=\mathrm{rand}(5,50)。 一个参数 e 是由生成的 e=\mathrm{rand}(500,5000)/10000 我们设置平均可用区域 E to E=\mathrm{round}(W^2 e^2)。 对于每个 d=0,\cdots,D-1,我们生成 a_{d,0},\cdots,a_{d,N-1} 如下

首先,我们生成 T_d=\mathrm{rand}(W^2-\mathrm{floor}(\frac{3E}{2}),W^2-\mathrm{floor}(\frac{E}{2}))。 接下来从集合开始 S=\{0,T_d\},生成 \mathrm{rand}(1,T_d-1) 并将其添加到 S 直到元素数量 S 变为 分别为 N+1。 让 s_0(=0),s_1,\cdots,s_{N-1},s_N(=T_d) 是结果的元素 S,按升序排列。 然后我们设置 a_{d,k}=s_{k+1}-s_k。 最后,排序 a_{d,0},\cdots,a_{d,N-1} 按升序排列。

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

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


示例输入 1

1000 5 10
6508 11666 12167 16717 46095 55928 56542 127260 200961 202211
11754 15667 26620 31851 48890 50181 52520 53150 263650 280526
7171 7218 14268 26231 37133 47199 93385 131356 174634 189807
10290 15811 16235 39805 45168 75830 76161 137648 148368 152504
6553 22994 44284 45120 67646 68899 98726 129109 138615 247097

示例输出 1

0 43 23 326
747 654 824 843
863 2 1000 469
824 621 892 869
892 469 983 977
23 19 676 105
58 917 742 1000
494 398 747 917
85 105 863 398
6 398 403 911
166 917 329 1000
6 848 266 911
403 803 588 1000
863 633 983 977
361 19 494 398
361 398 494 803
494 105 588 767
863 0 1000 633
588 0 863 1000
0 19 361 848
10 740 81 841
949 196 1000 425
538 396 588 764
883 425 988 748
0 0 189 268
0 268 189 540
588 396 883 764
515 76 949 396
81 767 873 1000
189 0 515 583
363 460 538 767
363 767 600 923
762 767 873 923
288 923 807 1000
0 0 1000 76
188 397 363 832
10 376 188 841
0 76 462 376
515 76 949 425
538 425 988 764
10 376 86 736
288 452 330 1000
1 76 243 265
349 283 604 460
86 397 288 736
0 736 288 1000
243 8 604 283
330 520 600 1000
600 638 1000 1000
604 0 1000 638