THUWC 2024 游记
1.18 Week -1
老师说我清华营通过审核了，意料之中，下周训练。
1.20 - 1.24
练习清华的题，主要是 THUPC2024 初赛，本质上好像跟清华营关系不大，主要是熟悉出题风格。
清华营的题只有 THUSC2022，T1 一眼了，T2 挺有意思但不会满分，T3 通信题（害怕），T4 SAM 过于复杂，预估大概两百分左右，以此为目标。
工程题是我比较擅长的，也就是大模拟！做了一下 THUSC2022 的，关于网页的诸多算法，比较简单 400/500，给我带来了极大的信心，我的码力一直不差。
临走晚上 Myee 学长教了一下 Linux 系统，差点考场上不会用。
1.25 Day 1
早上坐飞机，下午试机。
下午在巴蜀中学拍了一些纪念照，在校园里走了一圈，据说这是重庆最好的学校，是小学、初中和高中一体的，校园非常大，各种店铺丛生。
清华精心准备了一些纪念品，有签名人工智能漫画书（作者签名版），logo 鼠标和笔。相比 CCF，良心很多。试机三道题，交互题是暑假学长讲课的原题，1h 都做完了，顺便熟悉了一下系统操作，还剩 1h。老师说电脑不能关机，我就想今天的文件说不定可以留到明天，于是苦写了 1h 各种板，当然结果就是第二天来了啥也没有。
晚饭吃的有点辣，八点回酒店背板。
1.26 Day 2
8:00～13:00 长达 5h 的测试共 4 题，顺序开题。
T1 看了觉得不是很一眼，推了一会发现一个结论，但是时间复杂度有点超，40min 77pts，优化了一下变成一个乱搞，1h 40min，居然过了。实际上应该还差一步优化才是正解，不知道 Systest 有没有被卡。
T2 期望数学题，暴力推，打表程序有个地方写错了，导致我一度以为推错了。因为我是朝着正解的方向写的，所以写的比较麻烦，最后变成了轮换式求递推。神奇的将 n3 写成了 n2，2h 获得了 90 分。还有 10 分，n 比较大，再加上 n=2^17，一眼 NTT，懒得写了。
T3 构造题，3 个 Subtask，Subtask1 n=2 很有提示性，但是没仔细想，没想出来怎么构造，导致 Subtask3 不会构造，只拿到 36 分。一直在想 Subtask3，其实应该逐步递进的，先想 Subtask1 更好，浪费了很多时间。
T4 Hard 题，根本不会，甚至暴力一开始没想出来，最后 15min rush 一个暴力失败。
赛后才知道分 PreTest 和 Systest，Pretest=100+90+36+0=226，Systest 预计 200 左右。
Day1 在 T3 上出现了一些失误，只要在 Subtask3 中运用 Subtask1 的结论，大概能有 70 分，但现在只有 200 分，偏低了。赛时对自己的预期大概是 275～300，只能靠 Day2 工程题翻盘了。但这是符合赛前我的预期的。
在食堂吃了午饭，下午先拍了大合照，这样来看大概有 500 个学生参加，但这个照片我一直都没见到。其他相关照片在 https://y.camera360.com/photoliveh5/home?orderId=202401261145428396&channel=pc&origin=qrcode。
下午听讲座，开始前有巴蜀中学的表演，一个歌舞团一个舞团，充分展示了学校的人力资源与豪华设备，难以想象礼堂有如此眩目的灯光、烟雾特效，甚至舞台地板都是 LED。后来才发现全国大部分地区都已经放寒假了，而我比完赛还要去期末考，悲。
先是清华副计算机主任、巴蜀中学校长、清华学长先后致辞、发言。巴蜀校长发言脱稿，并且主持人很专业，好评。后是清华的马少平教授做 AI 人工智能的讲座，生动地讲解了人工智能的发展史和应用，溢趣横生。他讲了的重点有汉字识别、大语言翻译、AlphaGoZero、ChatGPT，提问环节已经有 人在猜测明天的工程题是这些了，那真的是有些恐怖，我想。我本来也想提问，关于前面看到有个新闻说 ChatGPT 算力逐步下降，变得“愈发懒惰”，这个现象的原因。后来去百度上搜了一下，发现马少平教授正好发过一篇关于这个的微博，真是太巧了。
晚饭吃了一家经过半个小时选定的地道重庆菜，味道着实很好，也不是很辣，回酒店继续练习码力。
1.27 Day2
8:30～12:30 4h 一道工程题，感觉时间有点紧。暑假叶开学长讲课分享经验说他多次在比赛中考 Day2 逆风翻盘，加上工程题我还是挺强的，又有些信心，总之心情忐忑。进考场后，比赛还未开始，我左顾右盼，考场后面有个 OI 知识网络，里面的算法我大概会一半，但有几个我甚至听都没听过，例如 alpha&beta 剪枝、min-max 搜索。
这次的题目是“四子棋”，写一个程序跟评测程序对抗，我都懵了，这不就是人工智能吗？比昨天我们设想的更加抽象。我怎么可能写的出来？工程题不就是应该在课件里写点公式伪代码啥的让我抄抄调调吗？这再次刷新了我的认知。我慌张的打开了学习资料，只有一个几十页的清华大学的课件，里面介绍了四个算法，分别是 alpha&beta 剪枝、min-max 搜索、信心上限+蒙特卡洛搜索树，深度学习神经网络。前两个写的很模糊，应该只有学过那两个算法的能看懂，我顿时就慌了。第三个只看懂思想，蒙特卡洛搜索树就是随机下一个决策点，并且随机之后的策略，知道胜利或失败，以此计算每个节点的权值，以此搜索-回溯的过程建一棵搜索树，但是蒙特卡洛搜索树的节点访问概率不应该是纯随机的，而是随着随机次数增加通过信心上限计算得到，可是信息上限计算公式中的参数 c 它没给。这就没办法了，深度网络更是别想。
这个题的评测也很麻烦，我以前在本地从来没运行过 SPJ，而且在 Linux 系统，搞懂这些加上看学习资料，用时 50min。这个评测规则是：随机生成四子棋棋盘与“不能放置的格子”，与机器对抗，总提交次数不超过 10 次，如果档 i 得分小于 60，档 i+1 最多提交一次，每档记最高分，也就是说提交需要非常谨慎。
题目保证评测程序一依次增强，分为 5 档。我写了个类似有必胜的决策就走必胜策略的程序，本地测试档 1 结果胜率大概达到了 0.7，提交后 10min 返回了 90pts 的结果，在我意料之外，此时已经 10:00 了。
但是我的程序被档 2 本地测试程序暴杀了，于是我只能写我能看得懂一点的蒙德卡洛搜索树，但是我不会建树。没关系，我直接随机，不建树，思想差不多就行。调了一会跟档 2 干，胜率也大概是 0.7，但是已经可以干掉档 1 了，于是我开始调节参数。一般而言，胜利的奖励值是 1，失败的惩罚值是 1，经过我若干轮测试，这个比率为 1/3 反而是胜利率最高的。于是提交，10min 后得到 70 分，这时已经 10:40 了。
后来我就发现我判断胜利局面直接就少了一种情况，本来四条直线我只判断了三条，于是这里修改了一下。增加了随机化搜索的次数，10000->30000，时间不多，本地测试发现 28 号测试尤其的强，卡了一会还是选择了 1/1 的比率。此时我发现我的程序有时会犯一些低级的错误，究其原因是没有防止一些两步到达的必胜态，于是新增一个几十行的 anticipate 函数，档 3 的胜率大概达到了 0.6，符合预期提交，10min 后 11:20 获得了预估的 60 分。
还剩约 1h，我在想新的优化。前面的程序中忽略了一点：测试程序是智能的，它也会选择最优的走。也就是说我在随机中应该按最差情况计算权值，这个写起来很麻烦，12:00 写好，这样我得到了每一步权值和最差权值。关于两个如何取舍，我拿不定主意。一般来说应该是按权值相加，于是我开始测试 这个权值。我发现只采用最差权值能在档 4 中有 0.4 的胜率，但是我预计的 1:1 只有 0.2 的胜率。我已经没时间调权值了，虽然我觉得调一调可以获得不错的分数。神奇的是 1:1 碾过了 50 号测试点，于是我决定拿这个作为最终版本，整理好压缩包还有 10 分钟。档 4 我把两个都交了，别的档各交一遍最终版。两次提交至少间隔一分钟，我惊险的提交成功。
后面 6 次提交都没评测出来，题目时限是每一步三秒，我的最终版的时间复杂度达到了 1200^3，居然不会超时。前面 90+70+60=220，预计最终版得分高于 300。
两天得分超过 500，完成翻盘！
后来了解得知这个四子棋和蒙特卡洛搜索树都挺有名的，但这个工程题人均分一百多一点，我三百多应该有 rank50。
吃过午饭听嘉宾报告，又是一个教授讲座，吴翼教授（助教）分享了自己学习、工作和比赛的经历，他先后任职于 Facebook、字节跳动、OpenAI和清华教授，可以说完全赶上了时代的浪潮。接着是提问出题人环节，原来工程题来自于清华大学大一寒假作业，还有一个网站：www.saiblo.net 可以在上面测试。
随后便是激动的颁奖环节，由于评测很慢，还迟了 15min，这段时间大家都在那个网站里跟 AI 下四子棋。颁奖按学校发，学军就我一个人。我想想清华约门槛较低，应该是稳的，当拿的时候还是有点紧张。激动的心，颤抖的手——一等奖，最优约。
那么清华营就算是圆满结束了。晚上吃了一个地道的重庆火锅，飞回杭州。到家接近十二点，突然发现明天还要上学。