2018 新生杯纪实

Ramen 收录于个人记录

2018-12-30 约 3985 字预计阅读 8 分钟

2018 年的哈尔滨工业大学（威海）ACM 新生程序设计竞赛上周结束了～

作为这次的主命题人，这一次也是搞了一个多月才选好题造好数据写好 Checker，最终呈现给所有的新生。

题目的材料在：https://github.com/lxdlam/hitwh-2018-newbie，有什么问题欢迎给我提 Issue。

这篇文章就记录一下整个过程吧。

命题准备

确定命题的准备是大概从青岛站结束的时候开始的。

去年宁神出题非常牛逼，冠军亚军 3 题，然后就是 2 题的 1 题的，情况非常惨烈。所以今年命题的时候准备就是有一点层次感，每个题大家都能动一动手，但是到底能不能做还是得看个人的本事。

一开始命题的时候的方案是，保证使用 C 语言可以写出每个题目，然后准备 2 题防 AK，8 题算法题，难度还略有上升。后面通知发出去发现是 8 题，所以砍了一个防 AK，砍了一个数学题。

方案出来了以后就征集了一波题目，由于当时 LFhase 他们的队还要准备焦作站，所以主要的出题方案是我们队和 SRC 他们队一起进行的。选题过程比较复杂，中间有几个拆换，最后总算是凑齐了 Idea，然后就开始了命题过程。

今年的命题过程全程使用 Polygon，这个平台真的就如它的 Slogan 一样，非常的专业。

各题命题过程

A. Arcaea

这题是我在把分数输进 Arcaea ptt 计算器的时候突然想到的，那个时候我才 ptt 10.8，刚好遇到瓶颈，想写一个简单的打什么推荐工具，所以看了一下午 Wiki，正好就想出一个相关的题目。然而官方的计算方式需要队列而且很绕（大概是个堆），大部分新生肯定处理不了，所以我简化了一下计算方法。

题目出起来还是比较简单的，因为毕竟就是一个简单的数据处理题，所以数据生成也是分段随机的。第一轮验题结束之后 blaction 发现有个问题：由于存在相同的 ptt，如果用的是不稳定的排序（比如 C++ 的 sort，有可能会用快排），有可能会破坏 ptt 的时序。想了想还是不给新生挖坑了，就连夜重写了 Validator，然后手上的数据全都报废了_(:зゝ∠)_，又连夜重新生成了数据，做成了现在这个样子。

验题的时候也很有趣，由于第一版题面写的有一些问题，包括这个题目也很细节，大家都是 -1 之后先问我是不是数据或者标程有问题（。

但是直到比赛结束之后我都不明白为什么把大家安排的不明不白的。

对了，这个题的样例是比赛前一周才出来的，在这之前验题都是对着空气验题，Rua。

~~现在我已经 ptt 11.30 了。~~

B. Battlestations Pacific

这个题原来是一个大模拟，但是 SRC 出的两版题目都太复杂了，然后 blaction 说道这套题目没有一个搜索题，所以我就出了一个搜索题。~~（所以 SRC 咕了我~~

这个题原本的思路 Google Kickstart 和百度之星都出过，我也就是拿出来改造改造就出了。一开始的想法就是先观察规律，然后直接 $\mathcal{O}(\log K)$ 分治 DFS 下去就可以了。

验题的时候 SRC 被爆 long long 卡了个 TLE，疯狂质疑自己，结果发现爆了 long long 然后就跑路吃饭去了。

这个题最终过得人数比预想得多，大家找规律的能力还是挺强的嘛。

C. Cities: Skylines

原本这个题是留给 SRC 的大模拟的，后面把 B 题占了之后就调整到这里了。

这个题就是青岛最后一题，给大家的签到奖励。题面就一晚上就写出来了，我打开 Steam 直接搜索 C 蹦出来第一个就是《城市：天际线》，我就随便编了个故事出来。

这题居然还有人 WA 出 12 发，我也想不通。

D. Dragon Quest

题目的想法来自今年暑假牛客多校的一道题目。当时我在大连摸鱼，离下课还有一会儿这场比赛开打了，我读了读题目就迅速切了这个题。然后出题的时候就想起来直接出，经典算法题之一。

和原题比起来，砍了两个难度。

原题要求的是 $[L,R]$ 区间内的方案和，需要做一个前缀和处理一下，这个东西新生很少有人能懂怎么预处理，就自然砍掉了。
原题的模数是 $10^9+7$，然而有几个有希望的新生之前问到我的时候都对一步一模不熟悉，所以出成 $2^{64}$。

最后出完题目有个想不到的地方：比起手动取模，直接溢出居然速度能这么快，时限上就收紧了。

验题的时候，codeyh 大佬给我说组合做法能不能做，我感觉行，但是不是很确定。他交了一发 WA 之后我越看越感觉真，连夜写了个 $10^9+7$ 版本的测了一下，发现是可以的，当时就和验题组讨论了一下，最后的决定是不改了，新生没几个能想到组合做法。但是比赛的时候真的有新生想到了，这一届好苗子真的多。

比赛的时候榜被带歪了，最后封榜之后大家的攻的方向就错了。

E. Ever17 -the out of infinity-

这个题找游戏是最难找的，找了一大圈实在是找不到，只能硬套神作 E17 了。

题目几乎就是 Facebook Hackercup 2018 Qualification Round B 原题，由于这个题系数没用，我把系数加强了一圈。同时，由于本题的答案很明显，所以我在输出部分认真写了很多骗人的输出。~~（这个坏习惯是来自于 EOJ，他们的题面也经常骗人~~

这个题验题的时候两位大佬都被演了，第一版代码都包含 INF 这个输出。我还给 codeyh 大哥发了个错的 Clarification _(:зゝ∠)_，~~被批为算协裁判~~

其实认真在纸上推一下就能很简单发现系数的无关性，那么判一下 $n$ 再读掉所有系数这个题就做完了。结果比赛的时候只有一位大佬做了，可能题面写的很吓人和没人过就导致大家都不敢开，其实这个题是一个很水的题。以后出题还是要考虑骗的力度小一点。~~不骗人？那是不可能的。~~

插句题外话，我当时打比赛的时候不敢交，因为 FBH 是 OI 赛制还是只允许交一次那种，我犹豫了将近半个小时才敢交。

F. Fire Emblem

我唯一留下的防 AK 题。这个题是改编自 JAG 2013 Spring 的题目，最早我知道这道题目来自叉姐的 FFT Slider。

这个题当时给我留下了很深的印象。首先的话，这个题直接做是想不到居然是 FFT 的，题目的 Idea 非常巧妙。然后，这个题让我了解了一系列日本的题目，我也参照了往年的榜单，东大、早稻田等名校在 World Finals 排行榜上名次也非常稳定，而且，日本选手主要使用 Java，在性能上和 C++ 有着不可逾越的鸿沟，这就导致日本的出题方向更接近于国际主流 ACM 出题方向：主要是思路和算法，模板和数据结构都当工具使用。今年的训练计划也会加上这一条。

说回本题，本题的题面应该是最早写完的。出的时候特别注意了一下 $N$ 的范围，由于原题给了 8s，所以很在意这个时间是不是因为 Java 而给了很多缩放。算了下大概的复杂度是 $\mathcal{O}(N^2 \log N)$，常数也比较大，如果令 $N=10000$ 本地也跑了很久，而 $N=1024$ 情况下最终不优化的 FFT 本地和 Polygon 上大概是 3.5s，评测机上是 5s。按照两倍时限原则，给了 8s。

题面完善了两次，加了很多东西。数据参照原题加强了两次，所以这个题的数据应该也是这 8 题里面最强的。

没人过，意料之内。有人交暴力，也是意料之内。

G. Grand Theft Auto

最早的 G 不是这个题，是一个打印蛇形矩阵。想了想，好像有点安排，而且大家做起来也会很难受。正好之前做了这么类似的构造题，所以就这么出了个题。

$N$ 的形式非常像今年沈阳现场赛的一题，而题目的原型来自于一场 EOJ Monthly。

这个题验题出了三个做法：

出题人分奇偶构造：奇数 $0,N,N,1$，偶数 $0,N,0,N$。
blaction 直接构造如下形式：$1,1+N,1,1+N$。
codeyh 在听完我的做法后没有被我带跑，直接一发 $0,0,0,N$ 就 A 掉了.

结果 codeyh 验完题一下子就把这题难度拉低了一个档次。然后验题组讨论了一圈，提示上给出了两个很关键的运算律。

预计上这个题过的人应该比 H 多，结果反过来了。可能还是构造或者异或不熟？

H. Hacknet

Idea 来自于某场牛客小白赛。这个题之前是在我题库里面出好的，直接拿过来就用了，也没有什么复杂的。

写题解的时候两度把自己绕进去了，写着写着自己都蒙了。

真的有人直接复制代码就交啊，出题人真的会在题目里面写答案的？

最后调整

给 F 写了 C 标程。

在 CF 上给 F 开了 16s 然后交了一发 Java 暴力，得到一个 TLE，于是安心给 Java 开了两倍时限。

在 domjudge 上测了所有代码，确定都获得了预期结果。根据评测机结果调整了所有题目的时空限制。

写了题解，最终调整了题面的某些描述和生成题面。

花了两晚上出了热身赛，还把热身赛 B 的 Checker 写错了，十分丢人。

比赛现场发生的事（裁判视角）

可能有的记得不是很清，也有些时间线有问题，就当一个乐子看吧。

C 题被首 A，而且是两位大佬同时提交，达到了出题人心理预期。
即使 Clarification 说了，还是有人往 Clarification 交代码。
D 被一瞬间干掉~~（然后榜歪了~~，接下来大家都在交 C。
A 题 Rk 1 吃了一个 WA 之后，插了眼的老哥看了看说大佬在搞 B。
A、B 和 H 很短时间间隔之内被三位同学分别一血，感叹这一届真的好苗子很多。
然后大家开始卡题，主要进攻方向是 B 和 H。
Rk 1 大佬搞出 B 之后去搞 G。
裁判组都蒙了，G 这种大水题怎么没人做。
有人一血 G，某位裁判直接榜锁定这个人，几乎是明示。
Rk 1 大佬还没出 H，插眼大哥很急。
有人 D 交了组合做法，我很惊喜，但是还是很抱歉，这是过不去的。
榜单逐渐平稳，Rk 1 大佬做出来了 G，开始搞 H，这个时候有不少 3 题的同学。
大家也开始攻 G。
Rk 1 大佬终于写出 H，裁判组看了看 G 和 H 的代码都蒙了，怎么会这么长。
忙里偷闲讨论了一下训练和选拔方案。
Rk 1 出了 A，突破了 6 题线，此时距封榜没有多久了。4、5、6 题都有人，这一届水平值得期待。
封榜了。
封榜之后没多久终于有大佬一血了 E，但是也没想到这也是唯一一个 AC，甚至是唯一一个提交。
怎么所有人都在做 D 而不是 E？？？？D 显然不能做而 E 可以啊？
还有人在疯狂交 F。
OI 大佬们终于在了一个稳定的位置，可能是 ACM 赛制还不熟导致比赛节奏掌握的不好。
封榜之后大家从各个方向追上来，有 4 题逆到 6 题的，也有 5 题平稳上 6 题的，4 题 5 题的也有不少。
比赛结束。

比赛结束之后

首先是讲了一下题，请各位一血大佬上来分享了一下，然后我细讲了一下，气氛还挺不错。

然后题目放到校 OJ 上，目前只有原版题目，几个加强版还在咕，应该会尽快。

榜的导出花了一番功夫。首先是 domjudge 6.0 版本引入了一个新 Bug，unfreeze 榜单之后榜单还是冻结状态，看了看 issue 直接 finalize 才获取的终榜。然后是保存到 HTML 居然有几个元素 Chrome 下丢了。最后还是选择 Chrome 打印到 PDF，这样版式更好。

获奖名单和老师争取了一下，确定是 50 人。

来自校队和老师的评价：这套题目很有含金量，出的很好。我觉得这就是我最高兴的事了。

希望大家新生杯参赛愉快！

目录