如何评价2023“钉耙编程”中国大学生算法设计超级联赛第二场

        第二场赛后，出题人DDOSvoid一直在搜索“如何评价...”的话题，他去年每次打完吃完饭的时候就在看评价，今年一直刷不到，因此我作为自己人来评价一下。

        4月底教练问我能不能组织三个队伍一起出一套多校，我当时觉得9个人出12题肯定不难，便组织了这一场比赛的命题。这是我们唯一一次负责大型比赛的命题，要为全国的选手提供一套有训练价值的题目，对我们来说是非常有难度的，因为我们一年前参加多校的时候也是罚坐，要让我们出很难的题，那是根本憋不出来。不过在我看来，一次次地罚坐并不能起到良好的训练效果，反而浪费了不少时间和精力，当年多次5小时里只有一个多小时有效输出时间，那简直就算坐牢。如果题目难度能够刚好让大部分人持续思考5小时，就能对不同水平的选手都有训练价值。

1001 Alice Game（出题人：starry）

        我们当初没有人有实力出防AK题，钻研博弈已久的starry主席说可以出得难一点，然后我们把防AK的任务交给了他。这题预定的难度是hard+防AK，但是在校内测试赛被当成第三签给签掉了（当时的String Problem还不是签到）。出题人开始怀疑人生，不过也不错，就当是找规律签到题。这题题目描述可能不够清楚，有很多人来提问，随着问题越来越多，我们多位出题人也多次反复检查了题意，都觉得不难理解，也不知道怎么修改，只能对因无法理解题意而耽误时间的队伍表示抱歉。

1002 Binary Number （出题人：Markyyz）

        按教练要求，需要来一道非常简单的题目，可以从校ACM新生赛里面挑一道简单的，我选择了自己出的easy题，这题是我去年上“中国建筑赏析”（T0级水课）课时想的，当时想出个二进制数操作恰好k次的签到题，突然来了idea，想出了这道题，并花了一分钟想清楚了所有情况，后来越想越觉得这题坑爹，出给新生赛岂不是要坑得新生怀疑人生，于是设置了良心样例，当时的校ACM新生赛的样例是这样的：

        但是既然要出给暑假多校集训，签到题也应该有其训练价值。为了起到良好的训练效果，我把良心样例换成了“凉心样例”，最终收获了937/5719的超高WA率，希望大家能养成签到题考虑极端情况的好习惯。有个别选手在反复WA之后开始质疑数据范围是否正确，这里分享一个经验，如果AC率是0/137，确实值得质疑，如果AC率是2/234，建议暂时放弃这题，如果AC率是200/1000，就很明显可以看出是有坑的签到题。

1003 Counter Strike（出题人：Markyyz）

        当时想出个圆方树题，5月分想出的idea，出这道题加起来花了将近100小时间。本来题意是多次询问，每次给定一个询问点集，求有多少个点满足删掉它可以让剩余询问点两两不联通，有五名验题人验过，但是校内测试赛有学弟发现这题和【SDOI2018】战略游戏（https://www.luogu.com.cn/problem/P4606）很像，我搜索后直接震惊，这也能原？（其实我还出了一道题，也原了，直接废弃）不能说是过于相似，只能说是完全一样，询问描述、数据格式、数据范围都是一样的，只是它那题求的是存在两点不连通，我是任意两点不连通。于是在赛前一周开始紧急修题，好在灵机一动，略微修改后变成了现在的样子，样例的图片再稍微P一下接着用，500行generator也顺利重构。。最后改generator和validator时，validator有一处漏考虑了，出了一个锅，感谢某支队伍assert发现错误后，私聊了教练而不是在clarification里指责。但是对题目影响较小，赛时发了个公告补充说明，没有改数据/重测，现在题库里的数据是正确的。我的做法确实不是最优的，但是复杂度也可以接受，受实力限制，最后一周改题没有时间细想了。

1004 Card Game（出题人：SPY）

        这题是他几个月前想的，当时在去华为软件精英挑战赛复赛现场，做活动的时候，他就和我说了这道题，本来想出给Debug杯计算机学院院赛，但是后来没出出来，正好用于多校。有一天晚上我和他讨论这题，我想很久也想不通怎么做，但是他很快就会了，还给我讲了半天，我直呼妙啊，然后给另一位出题人Pedestrian1验题，他直接秒杀。这题本被加强成medium，但校内测试赛发现加强后的做法假了，于是重新削弱回easy题，还给了一组大（臭）样例，便于大家猜结论，想必有超过一半的AC是瞎猜的（不可能，我做不来的题不可能大家都秒得掉doge）。

1005 Or（出题人：DDOSvoid）

        因为杜老师水平比较高，我们当时请他出一道hard，他搬出了本想出给普及组比赛的题...（这题是个有难度的数据结构题，其实我还没想过咋做，就不多评价了，感觉不是什么很好做的题，而且需要求的异或求和式比较奇怪，我根本不想看），出题人和验题人都觉得难度不高，实际上有人认为不难，有人认为很难。

1006 Fencing the cows（出题人：小手冰凉）

        我认为是非常好的一题，看似是计算几何凸包难题，实则叉积判方向后Floyd求最小环，这是一个算法思路很灵活的题，考察选手综合运用能力。虽然用到的是两个非常简单的知识，但是实际通过只有30多个队伍（部分学校用单账号重复提交的不算），只有最强的强者才能在这道题上灵活运用简单算法。如果陷入凸包死胡同，则会无法自拔。但是由于出题人能力有限，而且这题数据比较难出，没有考虑充分，有一些凸包+暴力DP的做法能过通过。

1007 foreverlasting and fried-chicken（出题人：Pedestrian1）

        一个图论计数签到题，枚举两个点是容易想到的，然后求中间几个点的个数时，也不难想到bitset优化（如果已经掌握bitset的话）。这题题意不太清楚，当时觉得有点问题，但是测试赛的时候没人问，后来忘记修了。赛时clarification里出现了大量提问，我们回复的比较慢，我一直想帮他修改，但是怕改错，因为我没做过这个题，想先联系出题人，而出题人下午1：30才睡醒，和他确认后也是我帮忙修的题面，其实集合的顺序也没讲清楚，好在没有人接着提问。给大家造成了误解，非常抱歉。

1008 Hello World 3 Pro Max（出题人：SPY）

        当时计划出一个线段树优化DP，然后决定要不线段树维护矩阵乘法吧，同时我们都很喜欢helloworld，于是有了这个题。这题复杂度是11^3nlogn，矩阵复杂度较大，出题人为了卡暴力测试了好久的数据，结果在测试赛被一个队14960ms（当时时限还是15s）暴力通过了，然后SPY继续造数据。比赛前一天我才开始读题，然后一眼秒了，当时SPY的std时间还是5000ms，比校内测试赛大部分代码都要慢，我一发AC就是1700ms，然后我们觉得std有大问题，优化了一下午，最后std被优化成了546ms，但是那一份过于离谱，最终使用了800多ms的std，时限也被压缩到3s。要求大家在做矩阵乘法时不要取模满n^3次，最内层循环枚举k的a[i][k]*b[k][j]不应该每次取模，如果模数1e9级别，那么使用long long可以9次一取模，unsigned long long可以18次一取模，观察到矩阵均为的上三角/下三角的性质，也是能够大大降低矩阵乘法复杂度的常系数，虽然理论上都是常数优化，但是多个细节合并起来，可能就是10多倍的运行时间差，毕竟取模运算的开销是比较大的。希望大家能够关注到代码的细节，养成减小常数的好习惯。万一正式赛场上，很多人能恰好AC，而你莫名其妙TLE了，那时你将没有任何理由去责怪出题人。

1009 String Problem（出题人：void_f）

        本来出题人说是一道字符串medium题，本意是不用PAM，是一个有一定思维难度的字符串题，但是测试赛时没几个人想得到如何不用PAM做，又有很多人用PAM最小回文分割的板子轻松通过，我们觉得这题难度不太合理，当时又觉得中档题难度整体比预估得要高，于是削弱成了超级大签到（我看到改完的题目直接笑死，真有这么简单）。

1010 Klee likes making friends（出题人：suimu）

        这是一个思路比较明显的DP题，只要状态设置正确应该不会有太大的问题，但是需要进行一个空间复杂度的优化，并且DP转移也有一些细节需要注意，比较容易WA/TLE。（我的评价是，这题就是一个毒瘤题，时间限制实在是太紧了，卡常非常严重。其实这题被卡常了可能是HDOJ的原因而不是选手代码的原因。我多次要问他需不需要放宽时限到1500/2000，但他心意已决，必须是这个时间，而且已经超过std2倍了，也不是不合理。）

1011 SPY finding NPY（出题人：Markyyz）

        这题是后来加的easy-medium题，灵感来源于一天晚上b站上刷到的“秘书问题”。其实我小时候就听说过“最大麦穗问题”，后来也看过毕导的这个视频（单身狗速进！如何科学有效地脱单？）。本意是想送个简单的，原以为很多人都听说过，应该一搜就有答案，就算没听说过，应该稍微计数一下就能得出答案。结果赛时好像知道这个的人不是很多，实际上这个计数也没有那么简单。本打算2e5组询问，n不超过3e7，但是意识到精度有问题，用python高精度浮点数测试后发现n=290000多时炸精度，干脆n小一点吧，反正难度没有本质区别。

1012 Coins（出题人：void_f）

        当时出题人说有一个签到一个medium（旧版本的String Problem），我问他签到准备好了吗，他说准备好了，一个网络流签到。我直接震惊：网络流《签到》？网络流和签到这两个词也许很难放一起吧？放一起的话应该是很简单的网络流。当时忙着整别的题，我就没细看，直到校内测试赛，我们发现这个“网络流签到”根本没人做，我点开一看，发现自己根本不会，于是问出题人要题解，看了题解恍然大悟，是一个不错的最大流题，但难度也被重新评估。

1013 Turrent（出题人：6B8B4567）

        这是一个比较有难度的计算几何题，乍一看没有什么思路，仔细一想可以枚举出两两直线交点，但是然后呢？似乎要使用一些科技，不过暴力也可能通过。据说这题std精度炸了？这个我也不太清楚，毕竟我也不会做，有2个验题队伍AC了。题目本身确实是不错的hard题。

        最后的AC数量和预估的不太一样，1008和1011实际难度比预估高很多，其他还是符合预期的，区分度还可以，大家有不同的题可以做，有几个AK。问了几个网友，都说是能做满5小时不罚坐。有一点遗憾就是我想出的数论和SAM都没出出来，只能说实力有限出题实在是太难了，我再也不想出题了。总的来说我们对本场比赛还是比较满意的，期待接下来几场的出题人和做题人优秀表现。