Codeforces 掉分日常(五):极客精神

谈谈极客精神;CF 1236E

写在前面

最近参加了两场 cf 比赛,分别是拖哥 tourist 出题的 Global Round 5 和一个常规场 Round #593。拖哥场的题质量很高,很有意思,不过大多数题都是突出一个思维性,基本上只要想到了代码就很简单。拖哥写的题解非常详细,参考代码也写的很漂亮,值得一看:Tutorial #1 (en)

没有对比就没有伤害。Round #593 同样是一位红名大佬独自出题的一场比赛,评价不高。其中 B/C/F 三题都是数学/结论题,纸上推出结论后就能很快出题;D 题却是一道非常麻烦的 implementation 题。题目本身没什么思维难度(模拟一下,唯一用到的算法是二分),但细节很多,很难用优雅简洁的代码解决这个问题。赛后看评论区,很多人说“rating是写这道题的唯一动机”、“知道怎么做,但不想实现”,对这道题表示了失望。事实上比赛时最终写出 D 题的人也不多,大约只有 C 题通过人数的 1/10。

这引发了我的一些思考。在 ICPC 风格的程序设计竞赛中,理论上只要是编程解决的问题都可以出现。尤其像 Codeforces 这样包容万象的平台上,题目的风格更是千变万化。比如有些人说中国场喜欢出数学题(其实参加多校发现朝鲜出数学题更厉害),毛子喜欢折腾数据结构,等等。但大家往往对问题有一些共性的期望。如果说算法题也有审美的话,有些问题往往被认为是优美的,而有些问题则不是。当你解决一个问题后,会不由自主地停顿几秒,回顾题目的设计、数据结构与算法间的巧妙配合,感叹其精妙和有趣,你就发现了其优美之处。而当一个程序中充满了特判、爆搜剪枝、冗长的逻辑时,即使AC了也会被称作是“瞎搞题”(当然这种称呼也并非总是贬义)。

都说程序员都有些“强迫症”。从编译环境到代码风格,cin/cout 还是 printf/scanf,for 循环中写 i++ 还是 ++i,每个人都有自己的一套习惯。很多时候,我写完代码、逻辑正确之后有时还会回头修改修改,合并一些变量,把一些循环拆开写到一起,去掉可以省略的一些代码,在语义不变的情况下让代码变得更加简洁优雅一些。写算法当然也是如此。从链表队列二叉树,到树状数组、后缀数组、AC自动机,图论中的dijkstra、spfa、dinic、scc,数论中的FFT、NTT..... 许许多多神奇的数据结构和算法,有着无比精妙复杂的原理和证明,却几乎都可以在 20 行代码以内实现出来。这 20 行代码,似乎有着神奇的魔力,吸引着一个又一个 ACM/OIer 以及所有编程爱好者不断的继续探索、创造。

最近读《经济学人》,提到 Google 的程序员总爱用 Geek(极客)一词。所谓“极客精神”,就是追求简洁、朴素、理性,崇尚巧妙的解决方案。纵观互联网,从开源精神到匿名精神,都表现出极客们希望把互联网打造成一个纯净的、纯理性的、没有世俗约束的乐土。这又是另一种层面的优雅了。Github 被微软收购时有人赶紧把项目备份到其他开源平台、Github 因美国法律的原因 ban 掉了所有伊朗程序员的项目引起轩然大波,这都表现出极客们希望网络世界远离政治的决心。

但是,这个世界是混沌而复杂的,实际生活中的绝大多数问题也并没有一个优雅的解法,甚至没有一个完全正确的解。 The world is not a programming task. 几个月前,我在某家大厂的后端岗位实习过一段时间。由于业务量大、时间紧凑,在现代的软件工程“敏捷开发”的方法下,软件的代码里充斥着业务逻辑的 if 判断、暴力的循环、一把梭的差错控制,而且代码每小时、每分钟都在被更新,快速的迭代引发了大量的冗余,代码让人不忍直视。吃饭时听组长和其他几位同学聊天,说工作几年来写过最复杂的算法也就是写个循环、调个排序。在这样的环境下,我却发现组里有一位同学,午休的时候经常在翻各业务线的代码。看他的提交记录,有时就是进行了一些细节上的优化,或是把重复的逻辑封装成模块,以便下次使用时代码能更加简洁。刚开始不明白,觉得这些事不涨kpi,也不能给他带来一分钱的收入,看着像在白忙活。但现在有一点懂了。也许这就是一位极客在被现实中利益、金钱和欲望的扭曲旋涡吞噬前,最后的倔强吧。

1236E - Alice and the Unfair Game

简单写一下这个题的思路,其实挺常规的。

题意简单复述一下:Alice 和 Marisa 在玩一个猜数游戏,一开始 Marisa 有一个 1 到 n 之间的整数 x。每次 Marisa 可以偷偷地把这个数 +1 或者 -1(或者不变也行),然后 Alice 猜一个数(由于 Marisa 作弊,每次都没有猜中),这样进行 m 轮。最后 Marisa 还可以把数变一次,然后两处最终的数 y。给定 Alice 猜的所有数 ,问合法的 (x,y) 有多少对。

数据范围:

这道题有两种思路。

首先考虑对每个 x 计算有多少合法的 y。注意到每个 x 能够达到的 y 都构成一个连续的区间。假如没有 Alice 猜的数的限制,那么每轮之后区间都向前向后增长 1 格( 轮过后是)。Alice 猜的数对答案的影响是:如果第 轮后区间是,那么只有第 i 个数为 a-1 或 b+1 时,才会阻碍区间的增长。

我们不妨分别计算每个 x 的结果区间的上界 r[x] 和下界 l[x]。现在的问题转化为,对于每个 x,它的上界 r[x] 一开始为 x,每一轮就+1,遇到a[i]==r[x] 时不加,问最后 r[x] 等于多少。

容易产生一种思路:将所有连续的相等的 a[i] 合并在一起,看作一条线段。从每个点出发,向上下各发射一条射线,找到与之相较的第一条线段,然后计算下一个交点,以此类推。对于每个 x 发射出的两条射线,最终的落点即为 l[x] 和 r[x]。使用二分+差分来寻找线段交点,可以在 的复杂度内解决问题。

上面这种做法的代码很不好写。我们进一步模拟一下这个射线行走的过程,可以发现,如果两个起点不同的 x 和 y 发出的射线交到了同一个线段上,那么他们接下来的行程都将相同。而且,由于每个时刻 Alice 只会给出一个数,因此每个时刻至多只会有一条线改变行程。利用这一点可以将所有点一起计算,利用并查集来将行程相同的点合并。这种算法的时间复杂度为

无论用上面哪种思路,最终的答案都是

如果上面的射线和线段说的有点抽象,对于样例一(3 3 2 2 2)我画了一个图,希望能帮助理解。

zuhe01