记一次有趣的 2017 ACM 山东省省赛经历

这是第一次也应该是我的最后一次 ACM 经历, 作为一名非 ACM 集训队队员, 有幸参加了今年的山东省赛, 最后 A 了5题, 拿到了一块银牌, 也算是一次神奇的旅程了。回想起当初准备组队参赛的过程, 简直有点好笑, 先是听集训队的大佬们说今年省赛学校可以多报名几支队伍, 当时有点心动, 觉得身为一名 CS 专业的学生有机会去长长见识也是蛮好的。接着就被一个工作室的同学拉去了, 又找了另一个工作室的同学, 就这样组了队。不过, 3个人, 两个是搞 Web 和 Android 开发的, 另一个是搞信息安全的, 你敢信….这样的配置估计全国也找不出几个了吧。。。
好了, 不说废话了….

备赛

正式组完队已经离省赛只有一个月的时间了, 按理说我们应该赶紧多刷几道题, 多学几个算法才是最重要的事情。然而…想法总是美好的, 那个搞安全的同学一直在忙着做 CTF 竞赛, 我那段时间被华为 CodeCraft 软件精英挑战赛忙的焦头烂额, 根本无暇顾及省赛的事情, 就这样, 3个人只剩下一个在默默的学习算法(尴尬….)

跟着集训队每周参加训练赛, 第一周只有我和那位一直坚持学习算法的同学, 另一个没来, 结果全场我们卡在了一道贪心的题上, 看着对面的大佬们在不停的A题, 当时简直是越做越绝望, 只是单纯想着好歹出个题吧, 爆 0 就尴尬了, 毕竟业余选手。最后幸好队友在结束前半小时用暴力水了一道题。

第二周训练赛, 我去了南京参加 CodeCraft 复赛, 就剩下了他们两个, 回来后听说做的还不错, 出了两个还是三个(起码比第一周有点进步….)

第三周训练赛, 本来想着终于能凑齐三个人好好做一做, 然而没想到的是有一个队友睡过了头, 一直到比赛结束前两个小时才赶了过来, 当时我们两个已经出了几道题了, 觉得做的还凑合, 还有几道暴力水了一发, 都 TLE 了, 不过转折点在最后半个小时, 先是后来的那个同学成功 A 了一道转原码、反码、补码二进制的题, 接着我们连续把之前 WA 的两道给改对了, 当时还是非常激动的, 不过看着集训队的大佬早早地 AK 离场了…..

省赛

热身赛

就这样, 总共三人只凑齐过一次打训练赛的队伍, 来到了省赛的现场。
第一天热身赛, 还是比较轻松的, 三道题全出了。当时我们想着第二天正赛能拿个铜就不虚此行了。。。

正式赛

开始比赛后, 先发现了两道比较水的题, 一个是 G, n 次幂的累加和, 另一个是 I, 关于斐波那契数列的题, 很快我们成功AC了, 期间被 long long 坑了一次。

接着做F, 看似一道非常简单的判断一元二次方程的解是否为整数的题, 没想到陷入了坑里。。我至今觉得这个题目的描述相当有问题….原题描述如下

you are asked to judge whether the following statement is true: “For any $x$, if $ax^2 + bx + c = 0$, then $x$ is an integer.”

我们当时的理解是若这个方程的解都是整数就是 YES, 否则 NO, 结果一直 WA, 最后这道题卡了我们将近四个小时, 才发现原来无解的情况需要输出 YES, 当时我的内心是崩溃的…

还有一道 J 题, 被队友用贪心成功 A 掉了, 期间因为没有用 lld 而 WA 了一次。

这里, 值得一提的是, 我们队那位搞安全的同学全场 5 个小时, 有 4 个小时都在写 python….是的, 你没听错, 在写 python, 因为 python 的大数很好用。他一直在尝试用暴力来破解 B 题, 当时我看了一眼他写的程序, 顿时吐血….三重循环, 按那台机器的速度估计跑一辈子也跑不完。。。快放弃的时候另一个队友无意间提了一嘴, 你要不要把结果打出来看看, 感觉有戏, 之后一看…卧槽有规律! 还是很简单的那种, 当时我们简直是喜极而泣, 一阵狂敲键盘, 兴冲冲地提交后 WA 了, 三个人都懵逼了, (难道那个暴力的程序写错了??), 当时队友已经绝望了, 想放弃这题了, 我还不死心, 问了一下数据范围有多大, 结果才发现超 int 了, 汗….改成 long long 就正确了。

这时距离比赛结束还有 53 分钟, 也就是封榜已经有 7 分钟了, 有意思的是在封榜前我们看了一眼榜单, 默默地往下滑, 发现我们躺在铜牌区, 另外这时候B题还没有一个队出的….(我也不知道那个队友当时是怎么想的, 会去搞一道还没有人出的题), 比赛结束后我们才知道这叫 FB, 长见识。

这时我们已经出了 5 个题了, 当时估算了下, 应该能到银牌区了。最后我们三个决定全力攻 C 题, 很快发现了规律, 是关于杨辉三角的, 感觉还挺好写, 不过没有兴奋多久, 写着写着就懵逼了, 我们三个都不知道怎么对组合数取模….当时那个默默刷题的队友灵光一现, 想起曾经听大佬讲过要用逆元, 然而我俩根本不知道这么个东西, 最后一直奋斗到了最后一刻, 也没能 A 掉这题。

不过还是挺开心的了, 毕竟能A掉5题, 感觉也对得起这次青科之行了。