IOI 2020 - 游记

DAY 0

MIT 集训结束了，乘飞机飞往新加坡。在组委会的各种安排下，我神奇的和美国队队长 Benjianmin Pi 和俄罗斯队队长 lldar Ganullin 坐在了一起。

从波士顿飞往新加坡需要 20 个小时的时间，飞机上太无聊，准备看电影。我们这一排只有我面前的电视是好的，而且只有意大利语电影。

我觉得挺有趣，但他们俩都说看不懂。于是花 5 分钟出了十道联赛难度的试题给他们做。

我看了三部电影之后问他们做完没有。 400iq 说他没有任何思路; Benp 稍微强一点，拿出了 50 页打满的草稿纸说他推了 5 个小时终于会了第一题 5 分的暴力，现在已经写了 1000+ 行代码了，还没调出来。

亏他们还是大国国家队的队长，连联赛难度的试题都做不出。第一题不就是一个裸的可持久化动态仙人掌维护最小费用无源汇有上下界可行流再套上拓展 9 模数广义分治 FFT 吗？连这都做不出 IOI 他们不是要爆零了。

本来准备看第 4 部电影的，可是他们俩坚持让我讲题。我没有办法准备 3 分钟结束，可是才说两句话 Benp 就说他掉线了。

之后，有一道题讲了四五遍 400iq 都说听不懂，我用俄语再给他讲了两遍，他还是不懂，最后发现他不会「轨道稳定化子」的俄语单词，害我讲了半天。

讲了 10 个小时终于讲完了前两题，他们还是半懂不懂的状态。

下飞机后 Benp 说他在飞机上想好了，打完这场 IOI 就当场退役，彻底淡出竞赛圈。但这完全不是我的问题，我也没有想到他们俩会这么菜，早知道就给他们做入门题了。

这次下飞机是走的楼梯，我一出舱门就看到 IOI 主席跪在下面迎接我，新加坡总统和第一夫人坐在超长林肯里跟我挥手示意。

我别过两位菜鸡，反手进了车门，并在总统府中享用晚餐。

感觉总统花园里的游泳池太小了，只有 1km×1km ，游 1s 就游完了对角线，完全不够我施展身手。总统也感到很是抱歉，并表示马上会开发太平洋游泳池供我使用。

DAY 1

清晨常规晨练，绕着新加坡跑了 3 圈欧拉回路，感觉这城市还是太小了。

看完三个题发现好像都比较可做的样子，第二题一眼以为是转化为 68 连通之后搞搞，结果发现答案只有 452 种可能。

感受一下感觉第二题比较恶心，于是就决定先做第一题再做第三题再做第二题。

第一题做到一半发现暴力居然有 5pts ，瞬间感觉自己写正解是在做无谓的努力，然后随便搞了 9 分钟，感觉非常稳，过了样例就 A 了。

第三题猜想只要使用狄利克雷非主特征随便容斥下，结果写了个暴力发现大样例跑出来了，然后开始加两句优化跑两下，就拿到了 99.5pts。

然而这是不行的，居然只有 99.5pts 。

于是愉快地开始瞎做，做到一半发现我的方法好像有点吊，随便上个树状数组优化的 min25 筛套杜教筛就可以了，顿时感觉我走上了 AK 之路。思考了两秒发现没什么问题，就开始码 min26 筛了。

接着到了下午两点半宣布考试过了一半了。我开始刚 T2 。

结果发现果然 T2 才是最难刚的，一开始觉得只要维护一个可持久化动态仙人掌的想法是不行了，不改成仙人掌链剖分套圆方树感觉会超时。

然后开始想别的做法，发现好像可以枚举一个点判断周围 68 维空间的情况，然后正要开始写的时候发现不会判不连通。然后发现前面那个仙人掌链剖分的方法好像也不太好做了。

于是开始写写写，发现各种对，过了样例发现判 68 维空间好像比较容易，想象了一下 68 维空间长什么样子，然后瞎几把猜了个结论就 A 了。

好像AK了，非常感动。

最后说下我对题目的看法吧，我觉得这次 IOI 的题目还算比较科学，只不过难度较低，随便就 AK 了。

DAY 1.5

和美国队的选手交流了一下，他们 4 个都是华裔，所以交流起来也没什么困难。

我问 Benp:

“您哪里挂了？”

Benp:

“没挂，就是不会。”

这时旁边的 400iq 用俄文和队友交流：

&%@&@IOI￥%*&，@!#%*I_AK_IOI&!,&（￥……

(“我觉得这一届 IOI 好难，可是 I_AK_IOI 一直说简单，我也不知道为什么。。。”)

DAY 2

本来还以为第二天会难一点，可是 IOI 科学委员会又让我失望了。

一看 T1 ，这不是我徒弟 mathew98 出的水题吗？当时我头都气炸了，之前他自信满满的把这题出给我看，我当场就把他的电脑摔地上。你出这么水的题是在侮辱我的智商吗？到时候被全场切可别说你是我的徒弟！

现在倒好，他被我逐出师门之后有开始给 IOI 出题了。

但好歹还是比赛，我花了 2 秒钟切掉了它，准备比赛结束后再去跟他算账。

再看 T2 ，这不是我在飞机上给他们出的第 10 题吗？

我当时是故意把最水的题留在最后的，估计那两个人又切了，唉。

再看 T3 ，好像是 Tarjan 老爷子 2019 年的最新论文，只是一个快速动态图。只写了 2000 行就写完了，完全不过瘾哪 作为一场世界级大赛的压轴题，实现难度这么低实在是太没有区分度了。

现在比赛才开始 10 分钟，实在是不想提前离场，于是就自己搭了一个LOL玩了四个小时五十分钟。

比赛结束了，我装作十分遗憾的样子。

只见 400iq 一脸自信的向我走来，看来也是 AK 了。我上前询问情况，他说自己推了 4 个小时性质终于找到了 T1 的关键性质，拿到的 50 分，基本上 Au 是稳了。

不是， mathew98 这么水的题你没有 1s 看出结论是怎么当上俄罗斯队长的？

出来一看榜，只有我一个人得分大于 100 ， Benp 状态不佳，虽然他也看过 Tarjan 的论文，但是他好像只会暴力，只拿到 49 分的部分分，屈居第三。

DAY n

终于结束了