← 返回题目列表

AtCoder · intro_heuristics_b

B. 评分

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

(请先阅读A题,解决B题最高得分为1,对排名几乎没有影响。)

初学者指南

让我们首先编写一个程序来计算一对输入和输出的分数。您可以通过提交解决方案来了解总分,或者像本次比赛一样,通常会提供官方计算分数的程序以供本地评估。尽管如此,自己编写一个分数计算器仍然有助于检查您对问题规范的理解。此外,分数计算器的源代码通常可以重用来解决问题或调试您的解决方案。所以写一个分数计算器是值得的,除非它非常复杂。

问题陈述

您将收到一份比赛时间表 D 天。 对于每个 d=1,2,\ldots,D,计算一天结束时的满意度 d.


输入

输入是从标准输入以问题 A 的输入和问题 A 的输出的形式给出的。

D
c_1 c_2 \cdots c_{26}
s_{1,1} s_{1,2} \cdots s_{1,26}
\vdots
s_{D,1} s_{D,2} \cdots s_{D,26}
t_1
t_2
\vdots
t_D
  • 输入部分的约束和生成方法与问题A相同。
  • 对于每个 d, t_d 是满足以下条件的整数 1\leq t_d \leq 26,并且您的程序预计对于满足约束的任何值都能正常工作。

输出

让 v_d 一天结束时感到满意 d。 打印 D 整数 v_d 按以下格式转换为标准输出:

v_1
v_2
\vdots
v_D

示例输入 1

5
86 90 69 51 2 96 71 47 88 34 45 46 89 34 31 38 97 84 41 80 14 4 50 83 7 82
19771 12979 18912 10432 10544 12928 13403 3047 10527 9740 8100 92 2856 14730 1396 15905 6534 4650 11469 3628 8433 2994 10899 16396 18355 11424
6674 17707 13855 16407 12232 2886 11908 1705 5000 1537 10440 10711 4917 10770 17272 15364 19277 18094 3929 3705 7169 6159 18683 15410 9092 4570
6878 4239 19925 1799 375 9563 3445 5658 19857 11401 6997 6498 19933 3848 2426 2146 19745 16880 17773 18359 3921 14172 16730 11157 5439 256
8633 15862 15303 10749 18499 7792 10317 5901 9395 11433 3514 3959 5202 19850 19469 9790 5653 784 18500 10552 17975 16615 7852 197 8471 7452
19855 17918 7990 10572 4333 438 9140 9104 12622 4985 12319 4028 19922 12132 16259 17476 2976 547 19195 19830 16285 4806 4471 9457 2864 2192
1
17
13
14
13

示例输出 1

18398
35037
51140
65837
79325

请注意,此示例是一个用于检查问题规范的小示例。不满足约束条件 D=365 并且实际上从未作为测试用例给出。

下一步

我们可以按照第一天、第二天等的顺序为此问题构建一个解决方案(时间表)。对于我们构建的每个部分解决方案,我们可以使用上面的分数计算器来计算其优度(满意度)。所以我们可以构建以下算法:对于每个 d=1,2,\ldots,D,我们选择一天结束时满意度最大化的比赛类型 d。你可能在ABC等算法竞赛中已经遇到过这种“贪心算法”。贪心算法可以保证几个问题的最优性,但不幸的是,它不能保证这个问题的最优性。然而,即使不能保证最优性,在很多情况下我们仍然可以获得合理的解。让我们回到问题 A,利用刚刚实现的分数计算器来实现贪心算法!

贪婪方法可以应用于各种问题,易于实现,并且与其他方法相比通常运行速度相对较快。当我们需要处理巨大的输入时,贪婪通常是最强大的方法。 我们可以通过改变贪婪选择标准(评估函数)、保留多个候选而不是专注于一个最佳部分解决方案(集束搜索)或使用贪婪算法的输出作为其他方法的初始解决方案来进一步提高分数。 欲了解更多信息,请参阅比赛结束后发布的社论。