2019 ICPC World Finals

Replay

U:

• 上来先看 F，觉得是 DP 但是很难处理，跳；看了一眼 G，没什么思路，跳；期间有人爆交了 A，看了一眼 A 猜了一个假的不行的结论，交上去 WA 了。期间队友上机开始抢 J 的一血。
• UoW 过了 E，跟 Z 一起看 E。Z 觉得是边双，打开板子一看大吃一惊：边双的板子不知道为什么不见了。心态崩了。我接着想 A，Z 发现 E 不用边双准备上机。K 还在抢 J 的一血。
• 我上去把 A 敲了好在一遍过了。很快 J 有队伍过了，一血凉凉。遂开始写 E。
• E 题写了无数个 bug，期间还修正了题意。我 D 和 G 都有算法了，G 一看就不怎么能过，而 D 是稳的，决定先写 D。
• 这时我预言这场比赛四题才能有名次，一看现在才只有两题形势有点严峻。自我安慰说一个小时过一题就能有五题了。
• E 题过了以后，我 D WA 了。让队友写了 H 和 J，双（三）双（三）自闭。三人卡三题。同时我们三个小时没有过题，感觉要冰了，心想能把手上的都过掉就不错了。
• 三个半小时后，我 D 自救成功。K 的 H 经过对拍也爬出来了。只剩 Z 的 J 从 WA 变成了 T。本着『题数要紧，罚时没有』的心态开始大力优化。最后把一个 50 优化成了 log 50 卡着过了。
• 这时比赛还剩下一小时，我开始写那个看起来就不怎么能过的 G，复杂度是 $O(n \sqrt{n} \log n)$。K 说 F 能做，试图抢机。
• 我 G 很快就写完了，返回 WA。看了一会觉得没啥毛病，觉得可能是自然溢出哈希被卡了。试图改成模质数的哈希，返回 T 了。这时感觉已经没救了。
• 最后半小时就是不知所措看队友敲代码。然而 F 到最后都没写完，我最后五分钟上去表演了一下改哈希参数爆交，比赛就结束了。

Problem A

Solved by ultmaster. 01:07 (+1)

题意：给两排物品，每个物品分别有高度和价格两个属性。要求给两排物品分别做排列，使得同一列上后面的物品比前面的物品高；同一行上价格单增。

题解：盲人签到，上来就 WA。还得靠队友拯救。对价格排完序后，切成一段一段，然后从左往右加进去，少的那段在多的那段里面贪心找。代码倍增，没出锅已经很好了。

Problem B

看完口胡了一下觉得有点难写，就扔了。

Problem C

没看过。

Problem D

Solved by ultmaster. 03:36 (+3)

题意：有一个环，环上是很多种不同的颜色的左括号和右括号。要求一种切法使得有尽可能多的颜色满足是一个合法的括号序列。

题解：签到题 II，15 分钟写完，WA 了一年。对于每种颜色，使用 +1, -1 扫描，最低点就是合法的切割点。然后把合法的切割区间加进去汇总扫描线一下就好了。

无数个错误：

• 有可能这种颜色根本不可能合法（这个过不了样例）。
• 有可能没有颜色合法。
• 最终的最佳答案有可能不在扫描线的关键点上取到（不过按照 Z 说的那个方法写就不会有这个问题了，不知道为什么要执着地开两倍）。

Problem E

Solved by zerol. 01:49 (+1)

Problem F

Unsolved.

Problem G

Unsolved. (-10)

Problem H

Solved by kblack. 03:49 (+3)

Problem I

没看过。

Problem J

Solved by zerol. 04:09 (+8)

Problem K

Unsolved.