THUWC2024游记

· · 生活·游记

第一次参加清华的活动。

既然你在上一次手搓了CPU，那么今天要你四个小时硬造 Alpha Go 不过分吧？

day 0

报道，感觉北大营搞得很宏伟，清华营啥都没有，很..低调:)

不过第一次参加这么接近清华的活动，还是非常激动。

试机，A+B problem 秒了，T2 普及组构造，秒了，T3 还没看就被同学叫走了。

day 1

也是 7:40 准时到了，T1 看起来是状压 dp，但老是不知道怎么设计状态，所以没开，搁了。T2 上来就是《随机》《随机》《求期望》，跳了。T3 是交互，慌了。T4 是看起来很睿智的大数据结构，怕了。

好恐怖，没一道题有头绪，直接先把交互开了。

前两个 sub 还是一眼秒的，然后模仿 sub2 扩展了一个每一行二分求答案的做法，40 pts。

然后 T1 发现 最多选 n 个人，O(C_n^m) 可以拿到前两个 sub 的分，再拼个状压的特殊性质，58 pts。

T4 最低档暴力打了，15pts，理解错了sub3 的意思，白打了一会。

T3 想到了二分答案，check 是 C_1=O(n),C_2=O(n^2)，再乘一个 O(\log n)，有 37 pts。然后考虑优化 C_2。考虑先查中间的，然后递归剩下的，check 的 C_2=O(2n)，有 65pts。

T2 开始思考后发现 m=1 时选择一个区间相当于区间加，分超级多，写了就有 37pts。

然后考虑 n=2，发现是在算交换位置的概率，手模了就知道单次 \frac{1}{4} 的概率会换位，\frac{3}{4} 的概率不会换，矩阵乘法即可，45 pts

然后就继续往矩阵想，发现单次一个数跳固定的距离的概率是固定的，然后只用求 a_0 的期望就够了，O(n^3\log n)，写完了就是 70 pts。

58+70+65+15=208，烂了，T1 是要钦定某个人完成某个任务，没想到，全世界都过了，只能祈祷 day2 了。

下午的讲座没听，回家玩了会儿电脑（周日不放假是*&%##%@）。

day 2

哇潮，四子棋？

哇潮，AI？

哇潮，100+ 页的 ppt？

完了，看了一会儿什么都没懂，什么 α-贝塔剪枝，什么 Alpha go 强化学习，啥都看不懂。

烂了，决定放弃看 ppt，开始自己研究。

第一种策略，考虑找填完后能使得相同的颜色长度最长的点填数，40pts。

下棋只看一步是绝对笨蛋的，所以考虑估价函数。

不可能连四个的不加入估价。

如果已经连四个直接返回极大极小值。

否则判断已经连成的长度 len，需要填的那一列离那个点差的棋子数 dis，然后就没了。

调了超级多的细节和参数。

发现打 2.so 100% 获胜，打 4.so 60% 获胜，交了第一组，直接全过？！？！？！？！？！？！？

哇潮，直接解锁第二组，一交，60 pts。

哇潮，直接解锁第三组，一交，50 pts。

哇潮，直接交第四组和第五组。

哇潮，第四组 50 pts。

哇潮，第五组 0 pts（终于正常了）。

调了参之后交了一遍第三组。

反正前前后后交得只剩 一次机会提交了

哇潮，我还没判被 ban 掉的格子，加上特判之后打 12.so 有 0.78~0.85 的概率获胜，判之前 11.so 拿 0 分，直接交 第二组，哇潮还是 60 pts，甚至 11.so 全败:(。结束了！

翻！

100+60+50+50+0=260,208+260=468。

看了姚班的老师的分享，讲了一些 AI 的知识和他的经历，讲得很好。

颁奖了，一等约。

润了。

晚上 ABC 在学校打，AK 了。