0%

Codeforces-172 出题感想

第一次参加 CF 的出题,感觉蛮好的……

虽然我打了一圈酱油啊!啥都没做啊!

solution

2A --- xiaodao

你还想要有多水?

2B --- roosephu

普通青年:枚举分母。

文艺青年:连分数展开。

二逼青年: Fraction(x,y).limit_denominator(n)

2C/1A --- xiaodao

普通青年:暴力半平面交

二逼青年:暴力推公式

文艺青年:跳掉不做

要我的话还是半平面交吧,虽然这样也要推一些公式 T_T

2D/1B --- roosephu

这个题是我从耀爷那里蒯来的,结果没想到成为最水的题了……

一个结论就是最大值/次大值对只有 O(n) 个,用单调队列处理出来就好了。

感谢大叔提供了几个好数据~

有谁看得出这题是我出的么……其实我还黑了人的,只不过黑得很不明显罢了,连某热衷于黑我的小朋友都没看出来。

2E/1C --- WJMZBMR

答案就是每个点的深度的倒数和。(根的深度为 1)

证明嘛,我还不会一个显然的证明,但是我找规律找出来是对的。

有一种理解是这样的:我们考虑每个点,这个点只有在选择某次其祖先的时候才可能被删,选中自己的可能性是 1/dep(i) ,也就是这个点对答案的贡献期望是 1/dep(i) ,又由于每个点对答案的贡献是独立的(这点怎么看?),所以直接加起来就好了。

1D --- fotile

来自 fanhq 的加强版。

对于一个序列,求 k-MSS ,我们可以用网络流来做:一条链,限制流量为 k ,跑最大费用最大流。

这不是比暴力还慢么!注意到每次增广的特殊性,一定是选择一个区间,取了其中的值,然后区间取反。线段树维护即可。当然由于维护的信息比较多。要支持取反于是要还要记录最小值,还要顺便记录答案,比较麻烦。

于是就 O(n k log n) 了……

这个题居然被水过去了,坑爹啊……算了算了还是那句话:暴力能水过去也是他的能耐嘛。

1E --- fotile

主席的加强版的弱化版。(一种蛋疼的忧桑?)

做过原题的话应该知道用折线来刻画 dp 值这方法。对原题来说令 f[i][j] 表示第 i 个数为 j 时的最小代价和,可以知道 f 是一条折线,且只包含 O(i) 条线段,于是我们维护 f[i] 所表示的折线,递推出 f[i+1] 的折线。事实上这个方法是可以推广的,不过在这个题上是用曲线来刻画。曲线不好表示是吧,于是考虑维护曲线的导数。

维护了导数,找最小值也好找了,直接求与 x 的交点即可,方程也可以维护了。由于 n 只有 6000,暴力维护即可。当然你要有能耐的话可以用平衡树维护,保证复杂度 O(n log n) ,不过略难写。

procedure

一开始是在 G+ 上,主席说要给 CF 出题赚外快,于是我就回了句 bg ,然后就被主席拉过来出题了。

YY 能力完全不够啊。幸亏最难的几个题主席都已搞好了,于是我和 xiaodao 专注水题三十年。小岛出的 2A & 1A ,我出的 2B & 1B

一开始出 2B 的想法是要给一道水题是吧,然后瞬间想到 Python.fractions.limit_denominator 。当然连分数展开是果断不可行的,于是暴力枚举分母即可。

1B 的来源是耀爷讲课时的某题,我就直接蒯了下来~Gerald 好像搞了个很复杂的方法的说,其实就是个水题嘛。

一开始 1B 想出最大值除以次大值,后来想把数据出强一点,于是写了个 cheater 发现全部骗过去了,后来才发现如果是除以的话,答案一定是相邻两个数的商……宇宙大水题啊……

出题是放在 Polygon 上。真心是个专业网站,自带版本控制,用起来非常方便。里面有 invocation 用来测试数据,gen 建议用命令行做初始化,可以用脚本来生成数据,validator 检验特严格,一个字符都不能多,checker 感觉很松的,package 可以下载这个题目的所有相关信息,题目支持部分 TeX 语法真是太好了。幸亏前一段时间用过 git ,对版本控制还是有点理解的,用起来不难。唯一需要吐槽的一点,就是你必须等网页缓冲完毕后再点击超链接,否则会直接回到首页,蛋碎的感觉……每次 commit 都会发一份邮件,所以这几天被轰炸了不少。

主席某天突然之间就住院了,一开始我也不知道是啥情况,但是似乎很严重的样子。于是他的题就被分了,我、xiaodao、Seter 一起搞。我写了 E 的 cpp 以及 java ,慢出翔了,后来还是用的 Seter 的 java 。不过我写的 D 的 java 倒是跑得蛮快的样子。时限要求为 java 的两倍还真是蛋疼。为了照顾 Java 我不得不优化常数,结果最后和 xiaodao 一商量决定把时限开为 5s ,于是就有人水过了 T_T 其实我觉得 n 开小 k 开大蛮好的嘛,CLJ 说限制 k 的和也是可以的,这样更好卡了。

在比赛的前几天,突然得到消息说 C 冲了,于是怒 YY 题目。刚好做了一个 Project Euler 的题,于是 YY 出一个题,但是被 CLJ 抢得先机用了他的题。没关系下次再用嘛。

于是这场比赛的 problem setter 真是多,xiaodao、我、CLJ、fotile、kissbuaa ,另外 Seter、7k+、pashka、Gerald 来验题,规模也算得上庞大了,于是有人怒吐一槽:

话说现在 WJMZBMR 与 Petr 正大战三百回合,有兴趣的同学可以去围观。

然后晚上本来不打算围观了的,因为没人做,但是跑回寝发现大叔在做,于是怒围观。Seter、xiaodao、CLJ 开了语音,我和 7k+ 俩人就只好打字了……好苦逼。

于是讨论组里面的人全部开了上帝视角,成了权限狗。期间由于 XLk 突然之间回话了所以和 XLk 聊了一下天,他好久不回我了 T_T

发现 div2 的题超水,3min 左右 400+ 人过了 2A ,太可怕了。然后继续有人过 2B 。我很想不通那些过了 2C 没过 2B 的人是啥心态……我更想不通居然没人用 limit_denominator 来做,我还想不同有人用 Fraction 构造分数的时候用了小数从而精度有 bug ,我最想不通一堆人说这题精度太紧了太紧了。明明 Gerald 说这题太水要把数据组数减小的……

居然有人 5min 内过了 1A ,真是太令人惊悚了。我还看到若干个纯代数流,太可怕了。由于 1A 题过难,导致 1B 被迅速秒,成为这次 CF div1 AC 人数最多的题。

wuzhengkai 和 watashi 俩人同时在 33min 过了 A ,死磕着 A 不放干啥嘛,A 明显是用来坑人的。(wzk 的人人头像越看越觉得萌 = =||)

比赛的时候一堆人问 excluding OR 是什么意思。我明明记得我原题写的是 XOR 啊,那个英文翻译改成了这个东西真是蛋疼……偏偏样例精心手构答案是 7 和 15 无论 or 还是 xor 都可以解释。不过明明题目是 XOR 样例解释是 XOR 你还有什么问题吗?

哇卡居然有人交了 E ?WA pretest 2 连样例都过不了囧爆了。讨论组里面没人认为有人可以 AK 。

然后在 1h5min 有人过了 E 的 pretest ?为了和谐 pretest 是直接上了极限数据的,人民群众喜闻乐见欢兴鼓舞拍手称好。然后 Seter 拿过去一测发现可以 A 。经仔细研究后发现这个算法是错的……于是 Seter 出数据开始卡发现稍微一卡就可以卡掉了……结果一场腥风血雨在 CLJ 和 Petr 展开……再一看这个人还只交了 E ?果 E 大神!他的 AB 是后来才写的,太强大了……

大叔 YY 了一个 1B 算法,于是交了一次发现是错的,然后再交一次,于是我求数据加入 tests ,然后又写了个 gen 来生成类似的数据,似乎卡掉了一些人的样子。

D 题居然有人写正解!UESTC_Nocturne 太强大了……不过这个题被 liouzhou_101 骗过去了还真就不甘心呢。但是时限放的太宽卡不掉真是蛋疼呢。

之后一堆人在吐槽说 div2 的题太难了太难了太难了,你想要我做什么表情?

这次 CF 成功把 tourist 拖下 3k ……只要拼了前三题的手速就不会太差,后两题基本上没人过的。

nonsense

好吧就是这样,感觉蛮好玩的呢。

骗钱向:以后有谁要出 CF 了我可以过来打酱油啊,专业酱油三十年。