THUWC 2024 游记

· · 生活·游记

我要被取消成绩了

啥时候想写了再写

day1: 100 + 100 + 75 + 36

day2: 100 + 70 + 60 + 60 + 40

upd. 预言成功了，因为去年有约今年直接不给我发证书了，我是高贵的无奖选手。

不过感觉这次比赛打的还是可以的，起码是有大众水平的了吧。

真游记：

Day -1

第一次坐飞机。

然后 5k 把包忘安检那里了，跑回去然后忘了在哪个安检口了，然后丢了包又往登机处跑，然后成功在关舱门前一分钟上了飞机。

5k 和 jijidawang 研究了半个飞机的如何不用数字做到 24 点。

jijidawang：\lceil\mathrm{e} ^ \pi\rceil = 24

下飞机的时候 ltx 才想起来她电脑忘安检处了。

下午没啥事干，颓了。

Day 0

上午还是颓了。下午试机，我们步行去了巴蜀中学，然后感受到了山城的道路，爬坡爬楼梯快爬死我了。（而且我得背着我电脑，我电脑很沉）

（然后后来才知道有不用爬这么多楼梯的路，导航有点太好了）

试机没干啥事情，就研究了半天怎么联网，最后发现是我电脑不知道为啥不自动从 dhcp 获取 dns，需要我把 dns 改成手动再改回自动才获取 dns。

然后我交了个 a+b 就离场了。

然后我们又从同样的路走回了宾馆，回到宾馆我感觉我快被累死了。

晚上去了八一小吃街，吃了若干东西。我其实有很多图片但是友善一些我就不放了。（我懒得把图片上传图床也）

Day 1

8:00 开考开考。

T1 看到数据范围，这不是弱智枚举题吗，直接开写。写完发现 n, m 看反了。

想了一会就想到 O(mn 2^n) 的状压了，感觉不是很能过但是感觉想不到什么好做法了，然后直接开写。调出来后喜提 TLE。

然后我开始卡常了。额省流一下，把枚举集合内 0 的位置改成 lowvbit 找，然后还是卡不过去，然后把转移改成 FWT 的转移方式，跑的飞快，0.7s 过了。

其实好像想了子集卷积一些东西，但是没想明白然后就弃了，不过反正过了无所谓。

然后 8:50 的时候开了 T2，看到 2 的幂还有 998244353，不会是多项式题吧，但是 T2 应该不太可能。然后手模半天找转移系数的性质，看了半天感觉好像没啥性质。

看眼转移矩阵吧，等等这好像是个循环矩阵？草循环矩阵乘法可以看作多项式循环卷积，难怪 2 的幂和 998244353，不是真就 T2 考 ntt 是吧。然后光速把 T2 写完了，9:30 左右交一发过了。

一个半小时已经超过去年的得分了，感觉比较良好，开 T3 吧。是个诡异交互，十分钟把前两个子任务写了，然后想最后的包。看数据范围感觉没有什么头绪，先读了下 T4 的题，感觉是个 ds，看起来部分分并不多，然后又回来想 T3 了。还是想一些类似二分的东西。比较自然想到进行一个四分之类的东西，然后每次先查询右下角有没有，有就往右下角走。但是意识到左下角和右上角也有可能存在最优解，所以好像并不能直接整。不过这样我们还是只用走三部分就行了，还是有些优的？然后就写了个递归式解一下，发现次数小于 n！写了一下发现明显不对，然后意识到我把递归式写成 F\left(\frac{n}{4}\right) 了，应该是 F\left(\frac{n}{2}\right)。不过还是比平方优秀一些的！但是 C_1 仍然没有每次二分优秀。

不过发现这个算法 C_2 很小啊！感觉这个做法还是有些前途的。然后就考虑怎么优化。意识到如果右下角有，那么我们只需要找比右下角大的就行了，而且如果一个矩形内没有就不用找了，然后把询问记忆化了一下，反正加了若干优化后 10:50 的时候跑到了 75 分。看起来好像 C_1 和 C_2 都距离满分只差一半左右，不过感觉砍一个 2 的常数似乎不是很容易，瞪了一会感觉确实没啥前途就直接看 T4 去了。

想着争取上个三百（属于是打模拟赛的阴影了，名次 gap 最大的地方永远是 300 分的位置），然后看 T4 暴力加不带修的版本有 36 分，感觉很好啊！然后仔细看题，肯定给每一行做个并，然后考虑一段到另一段 c 的上界是多少，那么建图出来就只需要求一个最小瓶颈路就好了，直接 Kruskal 重构树就做完了。注意开头结尾的限制。然后就好了吧，然后就开始写了。

中途上了两次厕所，12:10 的时候写完了。然后开始吃东西等待考试结束了。

最后 100 + 100 + 75 + 36 = 311，感觉还是比较满意了吧

出门碰到了石二人，fzj 310，他 T3 97 分，T1 卡常没卡过去，T4 36 分没调出来。然后吃完饭了他突然说 T3 假了，草。他直接右下角有就往右下角走的。

《pretest 过了就是过了》

下午合影，合影完石二他们直接回宾馆了，我们去了开幕式和听讲座。唉 thu 真喜欢讲 ai。然后下午提问环节：“明天工程题是否要手搓 GPT”“AI 在其它运动上有什么应用吗”

晚上没干啥事。不过晚上突然想起来自己没传视频，紧急把 jijidawang 叫过来借他百度网盘号把视频传了上去。

Day 2

《四子棋对抗搜索》

好家伙昨天提问的全押中了是吧。

反复阅读了题面和 FAQ 等信息，一共只让交 10 次，每次提交仅有单次下子的时间限制，而且是 3s，总时间不限？？？？这评测机真跑的动？？？想到不可能在洛谷上做出工程题复现赛了还是有点乐的（

反正阅读学习资料，之前并没学过 min-max 搜索和 alpha-beta 剪枝啥的，不过好像也不算太难理解。后面有些什么蒙特卡洛算法（咋又是你），蒙特卡洛搜索树，信心上限树啥的。然后后面就开始神经网络了，后面的东西肯定是写不了的了，仔细想了想感觉信心上限树不是特别难写，打算现写这个然后再看后面。（一开始我确实以为我还有时间看后面的内容）

然后就开写了。可以加自己的 .h .cpp 文件？像真工程题了。然后决定把 UCT 单独开了个 .h 文件，第一次明白库里面的 #ifndef XXX_H_ 是啥意思，自己也写了个。

写了很久，疯狂 re。研究了半天怎么 debug 这个东西，Makeflie 里面加上了 fsanitize，但是 address 加不上去，因为没有链接 asan 库，我不知道咋链接就摆了。usan 还是能用的。靠这个调试了半天。

反正后来感觉这玩意调也太傻逼了，好多东西也报不出来，然后意识到好像也是可以 gdb 的，然后把参数加了 -g 开 gdb 试了试，发现果然是能行的。然后顺利调出来了一些东西，找了很久的 bug，把一些问题修好了。（其中有若干 n,m 写反，角色看反等问题）

但是我的 AI 还是人工智障啊？？发现大部分情况走出第一步之后它就再也不走其它步了（我写的是随机挂一个叶子），然后想了想，我拓展的时候是不是应该把所有叶子全扩展出来，然后尝试写了一下，发现我的 AI 突然不智障了。直接拿它和 8 对战一下观战了一下，卧槽我好感动它终于会下棋了！！！此时大概 12:03，我本机测了下发现大部分 AI 胜率都还有一些，于是就开始狂往上交了，决定直接交所有点了。但是有提交一分钟间隔，有点恶心了，反正一分钟一分钟的交了半天。我挺紧张的，因为我怕半小时测不出来，这样我就不知道我到底多少分了。不过评测机还是给力的，大概 12:20 就都测完了，100 + 70 + 60 + 60 + 40，感觉比我预期好很多！！ 然后就等结束了。

正解好像就是 UCT，可能我实现并不是很优秀，不过四小时写完大作业已经挺逆天了。

其实这个过程还真的是挺有趣的，比如中间看我的弱智 AI 下，每次叠成 3 个之后就是不往上叠最后一个，还有与弱智 AI 对阵都对不过，还是有点意思的。最后看自己写出来的 AI 对局不得不说还是很有趣的，虽然最后好像还是有若干 RE，不过无所谓了。

然后下午闭幕式，听一些讲座，可能比较有趣的就是“我们深度学习第一节课讲怎么 fq”

然后得知去年有奖的今年不发。妈的他们有获奖证书呃呃呃，我只有一张去年的 A4 纸呃呃呃呃，我想要证书呃呃呃呃。

算了反正证书都不给我了传个寄吧的录屏，不传了。

晚上去吃火锅，出现了教练提前买了餐但是没有预定，去了得知前面要排队一个小时，还有 5k 没预定就进去狂借充电宝。

然后去了另一家，然后继续有 5k 狂借充电宝。

然后去十八梯逛了下，有家店全是娃娃机我还挺想抓的我还挺想抓的我还挺想抓的我还挺想抓的我还挺想抓的但是忍住没抓。

唉想要玩偶是不是也是种心理疾病呢。

放个我的 ai 的 token：90789904ad15437c9751546a4ef647c4