如何评价 2022 ICPC 杭州站？

如何评价 2022 ICPC 杭州站？

期权匿名回答 · 2023-2-14 00:29:11

最喜欢的一集，被队友 @Snakes @Nanasemaru 带飞啦！

题出的好！难度适中，覆盖知识点广，题面十分易懂。给出题人点赞！
可能是换队名之后有了 Buff，这场出线题都不需要数理基础，再也不用被欺负了（x

队友真的很给力，开局蛇老师光速秒了 K，喜提第一个正式赛一血（21 ec 热身赛有个一血，是因为服务器时间问题，拼登陆手速了）。
前五题都比较顺，G 没想好调了一会才过，然后蛇又上来秒了 I （Orz）。
M 有点难产，一开始思考方向错了，好在 tyb 及时抬回去了，在封榜前过了。
最后 B 好像复杂度不太对，卡了卡常就过了。
还剩 17min，打卡下班。最后 E 交了一发 Strategy submission。

总之，有生之年摸到了自己打的杯子，很感动（21 Macau 不能算，因为主办方根本没发杯也没颁奖……）
感谢队友，感谢集训队的前辈和队员们，希望 BUAAACM 能再接再厉！
再随便扯几句。今天能凑齐三人打比赛真的很不容易。我所在的寝室楼周三和周五都封过，校内这几天也都是每天爆十几管阳。本来已经做好了单打/双打的准备，还好周末两天是有惊无险。校内也有好多队伍只能双打，很惨。学校两周前就通知可以回家了，为了打比赛留了下来，也是时刻担惊受怕的，还好最后结果不错。
打完这场比赛，就回家过年！

期权匿名回答 · 2023-2-14 00:29:54

感谢zju的好兄弟提供了验题机会，提前品尝了一套好题。
感觉这场比赛完全符合我内心优质比赛的定义。验题就做的酣畅淋漓，做完感觉很爽。其中IBM都算是我非常喜欢的题目，I更是感觉是难得的好题，非常的巧夺天工，让我一个从来不做交互的人都觉得妙不可言。唯一美中不足的是我个人可能不太喜欢这个G，倒不是树hash的问题，只是感觉这个corner case容易把人卡住。
可惜今天我校队伍发挥不太好，在场外看的是真的挺急的，有时候恨不得我冲上去帮评测机一起跑。希望他们下站能继续加油捏^_^

期权匿名回答 · 2023-2-14 00:30:35

不用hash判树同构就不会被卡hash。

期权匿名回答 · 2023-2-14 00:31:25

12.21更新
感谢私信指出的证明漏洞
G题的3.2证明“p1不在环上不可能”的case2：“p1背对p2的子树包含1”，会有这样的漏洞：如果p1是在1的子树里的话，p1背对p2的子树没有包含全部的1子树，有可能加上环上其他点，大小正好等于1子树。
这种p1在原本1子树的情况意味着size[1]>=size[2]+...+size[k]+1，说明这棵树的重心G（如果重心有两个，视作重心是那条边）在1的子树内部。然后在同构的映射中，重心对应重心；如果G不在环上，那么无论切哪条边，G点（或者边）一定是新的树的重心（因为重心的唯一性）。然后再观察重心到所有叶子的距离之和，切的边在对面的时候最小，切的边有端点在1上时最大，比较系数可以发现严格不一样，这说明p1不能在原本1的子树内。
---------------先前回答的分割线------------------------------------------------------
给题解补充一点证明。顺带一提， @oscar 的BSGS和我的极大似然估计拼在了一起出成了这个I题。我特别喜欢这道题，多角度思考得到最后解法挺好的。
复杂度确实是，但真的往这边硬想得出最终解法我觉得不太可行。

期权匿名回答 · 2023-2-14 00:31:34

占个坑，赛后可能会更新更多东西（如果出锅就连夜跑路了）写一下热身赛的来源，A是去年浙工大校赛的某题，B是听说pta支持交互了热身赛出一个玩一玩，顺便给大家复习一下Useful Algorithm。C是去年香港省赛的DP，正解做法就是将所有有用的状态拿出来，复杂度是，当然可以发现转移是个卷积用任意模数FFT做到更大的范围。D是ZJOI2022的题目，听说有很多中学生来打星于是就放进来了，出题人认为还是比较不错的一道题目，大家感兴趣可以上网搜索一下题解。
祝大家比赛顺利！
比赛圆满结束了！除了A题题面忘记说可以输出任意解，题目基本没有出锅，暂时不用跑路了。感谢出题组所有同学的努力，主办方为举办比赛做出的努力，和所有验题队伍提出的宝贵意见！
按照题目难度从低到高来点评一下题目：
F: dgg的大米老师喜欢的题。签到字符串小模拟。背景大概是群友转发一些很变态的东西的时候都会说是大米老师爱看的，并且群友经常会催大米老师入坑原神。现在大米老师真的入坑原神了，望周知。
D: 我的小清新签到题。结论很好猜，但是证明可能有亿点点麻烦的签到。对着样例手玩、直接解方程、打表都能看出的规律，try a try， AC is OK。
A: osc的数论题。原来的版本是不取模，而是让绝对值最小，没有输出方案。但是这样和第四个题的难度就有一个gap，于是修改成了带取模的版本。既可以直接用exgcd解两个方程来得到解，也可以观察到加一个等差数列等于加上个中间的数来只需要解一个方程。同时因为不大，也可以通过枚举对取模减了几个来避免exgcd，可能是一道略有细节的签到。
K: 我的小清新字符串题。当时缺一个铜牌题，一拍脑袋就想到了这个题，检查了一下不是很原就出出来了。思路整体来看比较自然，而且数据范围应该有很强的提示作用。其实可以在的时间完成每组询问，但是因为会提升难度并且与原来的题目比较割裂，所以就没有修改，有兴趣的选手可以思考一下。样例揭示了Putata和Budada到底是什么，引人深思。
C: Cls的背包题，据说有着真实的背景，把装备穿穿脱脱攻击力就变高了。本来的版本是的，但是考虑到整体难度就把数据范围调小来放过跟简单的做法了，这样难度可能就更偏向思维。可能有一些corner case，需要选手更加细心。
G: osc的图论题。又是一道结论相对好猜，但是证明可能有亿点点麻烦的题目，可能是本场的图论担当。需要注意的点可能有要使用正确的树哈希和注意到的case。可以通过用来给树标号和把环当成字符串来判断循环、翻转同构来避免踩坑。
M: 我的大骗题。题面有一点点长的题目，希望大家没有都错题。读完题转化之后如果想到枚举一个点来计算答案，那么应该很容易发现是一个区间加，维护所有数的问题，这个问题有一个比较经典的线段树做法，就是维护差分。如果再想到换根，那么就会发现操作实际上只有合并两个集合和一个集合一起加，只需要对每个集合维护两个数即可，代码会简单不少。可能是一道每一步都非常经典的题目，训练有素的选手应该能够很快解决。
E: 我的构造题。题目名致敬了去年CCPC桂林的“Assumption is all you need”，赞扬了oscar作为构造高手高超的解题能力，秒杀所有构造题，只需要一个oscar。难点可能在于要先想好用什么排序，再搞出相应的基本操作。验题的时候有些选手先想出了三步交换两个数之类的基本操作就使得做起来比较困难。另外一个需要注意的点就是对于的情况要么上机打表，要么发现操作只有种，于是可以手玩一下，比较考验选手对机时的利用。
I: osc的交互题。听说pta支持交互了，于是出了一道交互题。本来是步的签到题，但是有些无聊了，后面发现如果编号是个固定排列是有性质的，于是就变成了现在的样子。步应该是个迷惑性非常强的限制，但是解法的两步又非常自然，可能一位选手单独想到所有方面需要对这种题比较熟练，如果有两个选手交流可能做起来就轻松一些。这题可能是本场若干比较妙的题中的一个，希望大家比赛中玩的开心。
B: 我的数据结构题。题面有亿点点长的题目，但是其实想说明的东西非常简单。一道数据结构题，思路很多，关键就是枚举进位是第几位然后发现要把值域翻过来维护。代码难度和思维难度都适中。但是因为比慢非常多，所以最后TL开了6s，是std的四倍左右，分块做法的两倍左右，应该不会有队伍被卡常。
J: Cls的几何题。在纸上画画写写应该不难发现是一棵树，难点在于实现。题目要求输出分数，避免了选手产生精度误差，非常良心，给Cls点赞！但是因为坐标范围开不了太大，导致凸包点数不能卡到很大，所以暴力再树上跳跑的有些快，于是时限只设置了std的两倍，可能存在一些不需要发现是一棵树的性质，直接用维护凸包需要非常细心实现或者不使用stl，直接手写平衡树才能通过。
H: Cls的厉害贪心题。难点可能在于建图、Hall定理的运用、发现是拟阵和具体维护怎么贪心，可谓是处处都是难点，但是每一步都比较妙。如果是熟悉Hall定理的运用和模拟费用流的选手可能会很懂，但是还是会有一定的思维量。实现上可能略有一些细节，但是如果思路清晰相信也不会对选手带来很大困扰。
L: Cls的厉害字符串DP题。验题时唯一没有选手通过的题目。需要选手思考发现结论之后DP，从而避免需要搜索的问题。DP的转移又依赖于贪心，需要快速求解两个字符串某两个后缀的的LCP，是一道知识点考察全面，综合难度比较高的题目，给出题人点赞。
上面这些都是我赛前写下的，实际比赛中貌似KC的难度翻过来了，虽然本来就比较接近，然后I过的比预料中多，E、G比预料中少。G考前紧急加强了一下数据可能是原因之一。E题在验题时一些队伍很用力地去做，最后也通过了，可能是比较需要用力的题目，实际难度比榜上看起来要低。最后结果B题还是有队伍因为使用了过多的操作被卡常了，非常遗憾。I在验题时通过的队伍很少，正式赛中可能因为看起来就很有趣（实际上也真的很有趣！），于是大家都来做了。这次的I和绵阳的J都是近几年第一次出现在XCPC区域赛中的交互题，也都是很巧妙的题，希望大家可以多多探索这种题型在XCPC命题中的可能性。
热身赛的题目中有一个需要处理分数的交互，并且有两道题的题目名和正赛一样，不知道有没有细心的选手发现，又着切合实际的背景！
然后再碰瓷一下绵阳，赛前很看好&支持的triple_dogs，在前中期取得了巨大优势，然后在题号为B的数据结构题上写出了复杂度比std大的做法，一直到比赛最后也未能通过，痛失好局，简直就是我们队在CCPC绵阳表现的复刻，只不过绵阳是NJU出题，杭州反过来了，完全不敢想。祝他们在接下来的南京站发挥实力，取得好成绩！
最后的奖牌线是654，其实是比预计中低的，可能这场比赛有着corner case多，有一些题目存在一些正确但通过比正解困难的做法等等会让选手感到“坐牢”的体验，但是出题组仍然认为这套题是一套不错的题目。在我看来，命题者和选手之间的关系，不仅仅在于命题人需要给选手命制一套题目来达到区分、选拔选手的目的，很多时候命题人也希望借此机会和选手分享自己认为还不错的idea，或者认为某个做法很有用，但是好像知道的人不是很多，出一道educational problem来普及这个做法，这往往是出一套好题最难平衡的一点：如果将好的idea出到无关紧要的比赛中，未免有些浪费；而越新颖的题目难度就越难以估计，如果出到区域赛中的题目估计难度与实际难度偏差很大，对于参赛机会不多的选手来讲未免有些残酷。希望选手们都能体验到解出题目的乐趣与成就感，如果有下次命题的机会，我们也会尽全力做到更好。期待与大家再见！

如何评价 2022 ICPC 杭州站？

5 个回复