(请先阅读A题,解决C题最高得分为1,对排名几乎没有影响。)
初学者指南
“本地搜索”是寻找高质量解决方案的强大方法。 在这种方法中,我们不是从头开始构建解决方案,而是尝试通过稍微修改已经找到的解决方案来找到更好的解决方案。 如果解决方案变得更好,则更新它,如果变得更糟,则恢复它。 通过重复这个过程,解决方案的质量会随着时间的推移而逐渐提高。 伪代码如下。
solution = compute an initial solution (by random generation, or by applying other methods such as greedy)
while the remaining time > 0:
slightly modify the solution (randomly)
if the solution gets worse:
restore the solution
例如,在这个问题中,我们可以使用以下修改:选择日期 d 和比赛类型 q 随机并更改当天举行的比赛类型 d to q。 伪代码如下。
t[1..D] = compute an initial solution (by random generation, or by applying other methods such as greedy)
while the remaining time > 0:
pick d and q at random
old = t[d] # Remember the original value so that we can restore it later
t[d] = q
if the solution gets worse:
t[d] = old
使用本地搜索方法时最重要的是如何修改解决方案的设计。
- 如果修改量太小,我们很快就会陷入死胡同(局部最优),反之,如果修改量太大,找到改进着法的概率就变得极小。
- 为了增加迭代次数,希望能够在应用修改后快速计算分数。
在这个C题中,我们重点关注第二点。 修改后的分数当然可以通过从头计算分数来得到。 然而,通过仅关注已修改的部分,可以快速计算修改之前和之后的分数之间的差异。 从另一个角度来看,如此快速的增量计算的不可能意味着对解决方案的微小修改会影响大部分分数计算。 在这种情况下,我们可能需要重新设计如何修改解决方案,或者很有可能该问题不适合本地搜索。 让我们实现快速增量分数计算。 是时候展示您在 ABC 和 ARC 中开发的算法和数据结构的技能了!
在这种竞赛中,目标是找到更好的解决方案而不是最佳解决方案,程序中的错误不会导致错误的答案,这可能会延迟错误的发现。 为了及早发现错误,最好对您实现的复杂例程的函数进行单元测试。 例如,如果您实现快速增量分数计算,最好测试快速实现计算的分数是否与从头开始计算的分数相匹配,就像我们在问题 C 中所做的那样。
问题陈述
您将收到一份比赛时间表 D 天和 M 日程修改查询。 在 i-th 查询,给定整数 d_i 和 q_i,更改当天举行的比赛类型 d_i to q_i,然后在一天结束时输出最终的满意度 D 更新的时间表。 请注意,我们不会恢复每个查询。也就是说, i-第一个查询应用于由 (i-1)第一个查询。
输入
输入是从标准输入以问题 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
M
d_1 q_1
d_2 q_2
\vdots
d_M q_M
- 输入部分的约束和生成方法与问题A相同。
- 对于每个 d=1,\ldots,D, t_d 是独立且均匀随机生成的整数 {1,2,\ldots,26}.
- 查询次数 M 是满足以下条件的整数 1\leq M\leq 10^5.
- 对于每个 i=1,\ldots,M, d_i 是独立且均匀随机生成的整数 {1,2,\ldots,D}.
- 对于每个 i=1,\ldots,26, q_i 是满足以下条件的整数 1\leq q_i\leq 26 均匀随机生成 25 与当天比赛类型不同的值 d_i.
输出
让 v_i 成为一天结束时的最终满意 D 申请后的时间表 i- 第一个查询。 打印 M 整数 v_i 到标准输出,格式如下:
v_1 v_2 \vdots v_M
示例输入 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 5 1 7 4 11 3 4 5 24 4 19
示例输出 1
72882 56634 38425 27930 42884
请注意,此示例是一个用于检查问题规范的小示例。不满足约束条件 D=365 并且实际上从未作为测试用例给出。
下一步
让我们回到问题 A,利用您刚刚实现的增量分数计算器来实现本地搜索算法! 针对这个问题,目前修改“选择日期 d 和比赛类型 q 随机并更改当天举行的比赛类型 d to q”其实不太好。通过考虑为什么不好,我们来改进修改操作。 局部搜索方法最强大且使用最广泛的变体之一是“模拟退火(SA)”,它可以通过随机接受恶化的移动来更容易地达到更好的解决方案。 有关 SA 和其他本地搜索技术的更多信息,请参阅竞赛结束后发布的社论。