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 人。

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

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

那最后,校赛见了!今年校赛我们 16 级会给大家准备一套更有意思的题目,期待大家的参与了!