2019 ICPC 上海游记

  • 队伍:Wheatfield with Crows
  • 队员:邓浩然(HbFS-)、林思仪(LIN452)、陈昱文(Pepcy_Ch)
  • 题数:6/13(B,D,E,F,H,K)
  • 罚时:617
  • 排名:21/300(不含打星队)

Day 0

三支队伍打车到了上大的三个校门。。。

报道居然要每人签字。。。

食堂居然不比浙大好吃。。。

去报道时正好看到朝鲜理科的六个人在照相,见到了传闻中的整齐的西装。

热身赛被校内队伍暴打,到最后连 vim 配置都没敲完。。。

晚上在宾馆对面的商场里吃了西贝(牛大腿好好吃!)和 DQ 的奥利奥熔岩。三人做出了「从过个马路就是的商场出来后需要导航才能回去」和「回去后又跑过去买早餐」的窒息操作。

回宾馆后打 cc98 雀魂赛,很开心地拿了一位,目前积分 +20,还差一场,正分出线的话稳了。

Day 1

一如继往地去配了 vim(自动登录 DOM Judge 好评)。

lsy K1y14 后我去签 B,在写代码时不知怎地删了初始化的代码,于是 B2y29

之后尝试去构造 D,lsy 可以写 F。我通过顶点度数感受了一下觉得可以分成 $\lfloor n / 2 \rfloor$ 条链,但 WA 了三次后发现写的还是有问题,甚至时间上也开始有问题了。。。

期间 dhr 出了 H,给我说了做法后 H1y83;我给 dhr 说了 E 的题意后被指出是最大生成树,而且计数排序就好了,于是 E1y96。(自己当时可能在想构造,读完题就没想过做法的样子。)

之后 dhr 接手 D,重新想了个做法,于是 D4y152

lsy 的 F 被三道题打断多次后终于写完,过了样例后 F1y163

lsy 读了 M 并说了费用流,但没人提交过。我在等机位的时候看到 RNS 和高大爷他们各自出现了一个红色,觉得自己也会是 TLE,果不其然。之后 dhr 指出不用堆优化的话,Dij 费用流就是 $O(n^3)$ 的(但第一次要用 spfa 跑),改了一发后依然 TLE。同时 lsy 这边似乎出了 J。

我去看了红板,尝试理解 KM,但发现自己不是真正理解 KM 的人。dhr 在大概剩 90min 时提出可以优化简图到 $O(n)$ 条边,我花了一段时间理解后上机,期间 dhr 帮着找出了我找不到的错,改了两次才改对后终于过了样例(我只大概扫了一眼,应该是过了),提交 WA。我想了想觉得这个费用流的最后跑出的流量可能不是 $m$,我输出的中间答案会错,凭感觉改了一发依然 WA。最后时刻提交了一发 lsy 的 J 结束。

赛后看群发现被评价做「做 M 上头了」,看知乎发现我们的 M 就是出题人的正解,一模一样的 $4n$ 点 $10n$ 边,但不知写挂了什么。。。赛后 dhr 表示 lsy 某次下机后 J 的算法已经假了。。。更可做的 A 好像没人读过。。。

这个 M,如果出题人的 std 是跑的 Dij,那事估摸就没现在这么多了呢。。。顺便,想知道什么是真正理解 KM。

晚上在车站附近的绿茶吃了晚饭,之后又吃了 DQ 的奥利奥熔岩。

在回去的高铁上打了最后一轮雀魂赛的小组赛,虽然是一位,但回头看时发现有几次立直都是几乎听绝张,有点惊险。最后 +57 分 8 位出线了。

总结

只有我有罚时。。。

这次居然出现了不初始化这种事情,感觉自己前期打得有点糟糕。最后 dhr 开出费用流时,我本以为是梦回厦门,结果等滚榜时愣是有种梦回去年南京的感觉。

不知怎的被教练组续命去 EC-Final,那就希望能好好打好最后一场吧。