WrongAnswer的博客好久没刷UOJ了，结果回来随便做一题就被卡死了。
0分程序：http://uoj.ac/submission/312569
100分程序：
http://uoj.ac/submission/312567
http://uoj.ac/submission/312568
http://uoj.ac/submission/312571
http://uoj.ac/submission/312572
http://uoj.ac/submission/312573
完全不知道0分程序错在哪，本机测小数据也没问题，把0分程序瞎改成各种等价的程序都能100分，就是这个程序会0分，而且交几次都是0分。
UPD：
别看那么多了，我写了个20分暴力都挂了：
http://uoj.ac/submission/312608
就看下这个程序哪里挂了就行了。
这个Hack是不合法的，因为 $p=5$ 不满足题目条件“不存在两个正整数，使得他们倒数的和等于 ${3\over p}$”：${1\over 2}+{1\over 10}={3\over 5}$。可见这题的Validator是有误的。
正确的Validator：
def check(p):
for x in xrange(p/3+1,p*2/3+1):
if p*x%(3*x-p)==0:
return False
return True看alphaGem的blog才发现有这个坑。。。我考场上也没发现，还好数据良心放我过了。。。
这题强制在线，$\mathrm{ans}$ 的范围是 $(n-1)l=1.99999\times 10^9$，而 $p_0$ 的范围是 $10^9$，于是 $p_0+\mathrm{ans}$ 超出了 int 的范围。
有趣的是std也有这个问题，于是我尝试hack其他人的代码失败了。
作为无实力退役选手参加Astar玩玩，居然卡进决赛了。综合NOI排名（约47）和Astar线上赛的平均排名（约45），估计我的最终排名在40-50之间，拿奖是没希望了，就当一次旅游吧。
报道等一系列行为。
对欢迎仪式的认识环节感到严重不习惯。
来到考场，发完密码条，诶怎么用户名是奇怪的名字？试了下，登不进去。然后通知说登录名是前面那个数字。
登进去一看，傻眼了，这个决赛居然是要我们写AI？exm？一直以为决赛和前面几轮一样传统。原来更像Codechef的Challenge啊。（后来想了想，Astar是个启发式搜索的算法，看这个名字也应该想到要考你写AI啊）然而我就打过少得可怜的几场Codechef，根本不会AI的那套理论啊，好尴尬。
仔细看题目，写的是一个类似多人贪食蛇的AI。贪食蛇在二维平面上进行，但可以沿任何方向移动，不仅仅是上下左右，以及蛇可以自交（非常赞啊）。局面会随机生成食物和障碍，吃食物会加长、减速，出界或者碰障碍或者和别人的蛇撞，蛇会死。还有加速道具啥的不过我没用过。当时觉得我滚粗稳了（最后确实是这样）。
前三四个小时是练习赛，不计入总分。于是我就开始胡搞，想想不管怎么样也得搞出个能活一段时间的AI。怎样避开障碍呢？脑补了一会儿物理常识，如果把障碍想象成电荷，利用斥力似乎就能避开障碍了？于是yy了个引力场，设当前蛇头 $H$ 的速度为 $v$，对每个障碍 $O$，给 $v$ 加上一个与 $OH$ 同向，大小反比于 $OH^2$ 的速度 $v'_O$，相当于施加一个“力”，最后输出合速度 $v+\sum_Ov'_O$ 方向。
问题是 $v'_O={k\over OH^2}$ 不会弄，就想，如果就地转弯的半径是 $r$，那么在 $OH=2r$ 的时候令 $v'_O=v$ 应该就稳了吧。这么想，推了会儿就写，写完交上去。
结果第一轮测出来发现我蛇一开始就死了！撞到下方的墙了，怎么萎事？不是很懂，就打了个100*100的表输出蛇在每个方向受到的“力”，发现好像都是同一个东西。接着看代码发现我把一个距离和速度搞混了，改。改完以后又发现这个力大得有些夸张，在场地中间这个力还是那么大，很不符合常识啊。
思索了一会儿发现，我的程序假设四周设满了障碍，每个障碍对蛇一个力，合力就巨大无比了，就调了参数。
吃食物还没写，赶紧写。大概是，如果附近最近的食物周围没有对方的蛇或者障碍，就往食物方向走。写完交上去测第二轮。
第二轮又GG了，莫名其妙往角落里面撞了。又用输出100*100的表观察，感觉速度还是有点奇怪。怀疑式子炸了，一看果然式子完全意识流了，啥都对不上，很无语。赶紧重新推，感觉没有什么问题：
$$v=\omega r\Rightarrow r={v\over\omega}$$
$$v={k\over(2r)^2}\Rightarrow k={4v^3\over\omega}$$
然而突然我发现最后一步 $x,y$ 分量算错了，赶紧改：
$${v_x\over d_x}=-{v\over d}\Rightarrow v_x=-{4v^3\over \omega d^3}d_x$$
改完以后感觉和谐了不少。三四两轮，都拿了几百分，似乎还行？然而一看别人的分数，动辄上千，就觉得很绝望。于是冷静地观察了一下自己为啥会低分。
看着屏幕，我的蛇一开始非常正常地吃食物躲别的蛇，不过躲得有点保守（离别的蛇还很远就扭头就跑）。之后，障碍生成得越来越多，然后我发现，我的蛇开始不停地绕环了！原来我的蛇在一个以三个障碍为顶点的三角形内，受到引力场作用，就一直在中间转，等了好久才出来！
想fix这个问题。
第一阶段测试结束，第二阶段开始正式计分了。
一共三次测试，每两次隔半小时，每次测两轮，一共六轮。
思考了一会儿，觉得障碍不会动，只要靠近时绕过就行了，改成了距离太大就不算作用力，脸滚键盘弄了几个参数限制。然后局面边缘的障碍也只提取靠近的几个。
然而有的人的蛇靠别人的蛇撞上就得了1000+分，感觉这规则真是玄，正常地吃食物每局难以破1000分，别人撞一次就加1000分。想试试能否卡别人赚1000分，发现根本不会弄。
然后第一次测试的两轮，都中规中矩地拿了400+的大众分。观察我的蛇，发现似乎并没有什么变化，还是非常容易受障碍影响。
打完大概17名左右，觉得翻盘困难。
又yy了一会儿怎么卡别人，无果。
似乎还是要优化吃食物的效率？感觉参数还能继续调？又思索了一小会儿，发现障碍只要距离超过 ${2v\over\omega}$ 就不计算作用力，效果应该最好（差不多是和引力场没关系了）。
第二次测试。第三局300+，没进步，还是经常在没食物有障碍或者别的蛇的地方绕。
第四局，卧槽为什么显示效果这么鬼畜？盯着一个以为是自己的蛇看，发现几秒就撞上别人的蛇死了，卧槽不会是我哪里写挂了吧？不可能啊，我的AI这么保守怎么会犯这个错？结果出分，傻眼了，居然只有10分！也就是啥都没吃到。
然而看视频明明那条蛇吃东西了啊？后来通知这组显示效果挂了，蛇头和蛇身不同色，要以蛇身为准。嗯我看到的是蛇头是我的颜色蛇身不是我的颜色的蛇……可是我的蛇呢？找不到？！看到一共三个人10分，视频里看到没吃东西的蛇，策略都不像是我的啊？又数了下发现一组10个人但一开始只有9条蛇？
日哦！不会遇到灵异事件了吧。
至今不知道第四局怎么爆10的。
这时候只有20+名了，翻盘无望。
又yy了一会儿怎么卡别人，无果。
似乎我的蛇太怕别人的蛇了？嗯，对别人的蛇的参数还没调。可惜缺乏经验，对动的东西不是很会把握，于是继续保守向……
最后突然发现自己犯了个傻逼错误！我误把 $\omega=0.05\pi$ 算成了 $\omega=0.05$，怪不得会那么怕障碍！于是开始大幅度改参数，打出100*100速度表，发现只有靠边界两三行的地方会掉头，玛雅这不是太危险了？又调了一会儿调到一个看起来比较适中的参数。
测了五六轮发现，虽然靠障碍近了些但还是浪费一大把。果然还是自己感觉太差，$v=0.1$，$\omega=0.05\pi$ 时，$r$ 大概是 $0.6$ 到 $0.7$ 之间，离边界距离为 $2$ 不是很稳吗？
说到底还是自己被自己输出的调试语句欺骗了，以为一行就是很紧，却没意识到极限掉头不需要一行的距离。
这时候大概19名？
第三阶段测四轮，不能改代码，想想肯定要打铁滚粗了很不爽，就不看战况了。
最后把判定距离调成了预期的理论值，不知道是否有用。
只知道最后看的结果，4100+分，第15名。意料之中地打铁了。
何柱第一名。SkyDec、Stilwell、xllend3、小火车、AKF等IOI/候选队大佬都获奖了。而我呢，就这么空手回家了。
尽管我Astar就这么滚粗了，不过也是第一次体验AI大战，看到了自己和别人的差距，也算是有不少收获了。
旅游、颁奖。
颁奖前和OI大佬们一起在墙上拼了“ysy AK IOI2018”，其实我只拼了一点却莫名被采访QAQ
啥奖都没拿到太遗憾了。
技不如人，甘拜下风，加油努力，来年再战！
退役前的最后一战。
挺紧张的，毕竟我NOI只有#40+，就算把Day2挂掉的66分加上还是只有#20+。不止一题脑抽差一点想出来还是相当不爽的啊。
毕竟还是运气选手唉= =
以及我现在考场心态还是太糟糕。
不过作为国家队的最后一名，我也没有什么太多的梦想吧。保Ag争Au吧。
orz matthew99,xumingkuan,cy。
入住酒店。
刷了CEOI2016D2T1。想了一个比较复杂的做法不知道有没更简单的做法。
NOI同步赛成绩单出来了，作为Day2挂成114分的国家队垫底选手，看着被一大堆人虐感觉也是很奇葩的。(然而同步赛FJ Day2最高分居然也就114?大家都考跪了?)
和xumingkuan住一间。
晚上宋老师带全队四人去McDonald吃了点零食，顺便和另外三人聊了些题目怎么做。深刻感觉我水平低得可怜。
IOI前的ACM模拟赛。
把自己名称改成了orz_immortalCO，暴力膜锟。
A题找了好久的规律，才看出exgcd的做法。
B题只会一种很暴力的DP，过不去。jiaqiyang当场AC了。
C题完全不会。
D题看n<=17以为是傻逼题，然后想了1h还是不会，GG。
E题就是个辣鸡题，研究了好久发现细节很难处理，结果暴力都WA，最后干脆交了个不考虑四点共线，A//B//C时会退化成平方log的程序上去，正确性和复杂度都不对，居然能过。xumingkuan现场写了FFT过了。
最后2题滚粗。我并不能跟上国家队的平均水平。
动员会。没什么好说的。
在飞机上坐了大概10h，意识模糊。
下午Exhibition，没什么好说的。
练习赛。
就是之前做过的题，不过只有2h，来不及AK。
T1用我论文里面的独立集搜索算法拿了70分。虽然说正解更好写但是懒得写了。
T2水题切了。
T3水题切了。
T4提答，暴搜搜出4个点，又搞了4，5两个特殊点，拿了60分。剩下的点没时间搞了。
70+100+100+60=330
明天就是day1了，为自己加油。
Day1。
开场看了三个题，T1是个提答，而且数据点很大不能暴搜，感觉是神奇的构造或者随机化算法，应该要留到最后去争取；T2好像很套路；T3好像一脸不可做。
然后就开T2了。一开始想到费用流，然后思考了好一会儿如何优化这个费用流，发现增广路可能好几段，不太能优化。思考无果就去看T3了。
T3看完题再看数据范围，n<=5000，m<=20000，突然又觉得这题可能才是送分题。然后开始推DP，一开始想记f(i)为从i出发会不会绕道一个有充电点的环上，然后转移有环，搞不出来。又想了想，如果A必胜，那么最优路径就会一直经过充电点，反之n步以后再也不会经过充电点。
想到这里打了一个nm的DP：f(i,j)表示当前在i，走j步将经过多少个点，如果f(i,n)=f(i,2n)则i是0，否则1。虽然不会证但感觉没什么问题的样子，就写。
调到考试开始1:20时过了子任务1,2,3,5，另外两个子任务TLE，38分。看起来这个做法是对的，只是被卡常数了。然后优化常数，在1:40时过了子任务4，49分。继续优化常数终于不TLE了，然而WA在了子任务5的第96个点。
怀疑哪里写挂了，眼调了很久。
把怀疑挂的地方改改，怎么改都过不去，始终49分，WA第96个点。然后就浪费了半个多小时（Ag flag
已经2:20了，没什么救，弃疗去搞T2。
一开始打了个7分暴力。感觉这个题性质奥妙重重，一定有规律。于是拿7分暴力打表找规律，看看发现每段都是一段R一段B，两段最多有一个交点。这样就可以转移了，然而这样仍然是n^2的，在3:13时写了暴力过了子任务3，一共17分。
然后有一种自己这题到手了的感觉，开始想优化转移。看着式子发现是个斜率优化，然而看起来很复杂的样子。随后想想裸上决策单调性好像可以（Ag flag*2
然后以为决策单调性很好写，实际花了半个多小时，调不出来。好不容易调出来发现做法有问题，想fix这个做法又花了一会儿，还是错，惨啊。
这时候T1还没打，很慌，赶紧回去每个点随机输出一个极大的树拿了60分。
最后30min终于决定打T2的靠谱的斜率优化了，打了大概20min。
然而，没调出来（Ag flag*3
最后就悲惨得滚粗了。
60+30+49=139
考完第一个问xmk，他说他拿了274。我一听整个人都要吓软掉了，完了，真的没救了。lzz也拿了接近200分。myy和yjq好像也考跪了。
出来看榜，我#40，Ag分数，xmk#3，就要虐场。唉，这就是实力的差距。
听说T3只有4个人A，xmk就是其中一个。想想我这个做法自己都不会证是不是对的居然能拿49，却不知道骗分应该及时收手，导致浪费大量时间最后没时间做T2，70分没了，活该Ag。
下午回去，非常不甘心地继续调T2的斜率优化，花了大概半小时调出来了。早知道那个不靠谱的决策单调性就不要写了，省出这个时间完全足够A掉T2，70分没了，活该Ag。
在车上和myy，xmk讨论T2，他们说T2不用斜率优化，前缀最值就行。我说式子里不是有一个x吗，然后盯着式子又看了两眼，发现这个x是连续段的开头，是固定的！而不是x[i]会变。要是多思考下，前缀最值比斜率优化好写不知道多少倍。
调T3错误算法，搞T2决策单调性，写T2斜率优化，这三个错只要我任何一个不犯就是209分，但结局是139分。我连续这么多场比赛就没有正常发挥过，IOI又因为自己作死花大量时间在错误算法上而丢掉70分，丢掉Au，成千古罪人。想想真是太后悔了。
晚上去Exhibition到很迟才回宾馆。
Exhibition。
本来很好看的，一想到D1T2就没心情了。
如果是实力Ag也不觉得遗憾，然而明明会做的题却因自己作死浪费时间最后来不及调出来导致Ag，就十分遗憾了。
Day2。
还是花半小时看了三个题，T1、T2都是交互题，目测应该一道简单一道难，T3是传统题，看起来很可做。
然后猜了个T3贪心的结论，答案等于每个环的长度和加上s左边非自环最右和s右边非自换最左距离的2倍，交上去，爆0了。
发现写挂了，改了改交上去，又爆0了。
想了一会儿发现套在一起的环可以一起走，就fix了一下，交上去，50。
不错，起码s=0的对了。
60min过去了，我得了50分。（Ag flag
回去看T1。T1感觉i的个数大于i-1的个数的平方这个约束很奥妙重重，意味着可以用分治暴力搞出所有小于v的位置？然后随手打了个分治，交上去爆20。
然后发现递归到[l,r]时询问mid询问的不是[l,mid)而是[0,mid)，接着想前缀和减减，发现mid和l，r不一定都是v类型。
接着想法就是先随便询问500个位置取个最大的，然后就能判断是不是v了，不是v的只有不到500个，暴力扔掉。
写完交上去，拿了97，把500调参调到480，并没有什么卵用。
100min过去了，我得了147分。（Ag flag*2
感觉为了剩下2分多折腾太浪费时间，就去看T2。
第一感觉是高斯消元解线性方程组，接着想想发现一点也不靠谱。既然是生成树，就一定有什么性质，无环？
随后我的想法是，每个环至少有一条边不属于生成树，这样就可以对每个环询问L（L为环长）次确定环上是边是否属于要求的生成树，这样就能m次询问搞定了。然而只有暴力分。
优化了一会儿拿到51分，继续想，怎么想都只会m次询问的做法。
180min过去了，我得了198分。（Ag flag*3
之后继续搞T3，想想我的做法s不等于0为什么会错，原来s和左右端点夹住s的环不能套在一起。然后加了个贪心，先走到最近的环。
交上去还是50。然后发现5,4,3,2,1,0这种情况没有两个环是嵌套的。接着推出从环A能进环B的条件是A的最左和最右点之间存在B中的点。
看样子是求一个最短的包含s的区间使其能到所有环？写了个bitset+floyd+two pointers，只有12。
和s=0的拍了一会儿拍出WA，手算了一下才意识到在任何位置加边使s能到所有环就行了。
接着写了个复杂度不满的n^2 DP：f(l,r)表示从区间[l,r]出发至少加多少边能到所有环，用hash表存状态，过了70，最后一个Subtask TLE在第66个点。
继续推发现是个最小树形图，然而这东西我只会n^2暴力，想试图观察出什么性质也没观察出来，一定是我太弱了。
T2也没什么好的思路，连完全图都不会做。
最后延长了半小时，然而T2、T3都做不出来，很绝望。
97+51+70=218
两天加起来139+218=357，Ag稳，Au不太行，好虚啊。
出来问了下，xmk 250，lzz 267，myy 219，都比我高分啊。要是我Day1没丢70分就稳Au了。要是大家都会T2，T3……
出来看到中间榜我貌似#23？然后不少人发祝贺？然而还不是最终榜，好虚啊。
最终榜出来了，我#25，好像又卡了一次Au线啊。xmk#2，lzz#3。然而myy还是挂了，惨啊，myy在我心目中一直是最稳的，可是……为什么会这样呢？
仔细想想，我现在的成就有：CTSC 0AC得到Au，NOI 0AC得到Au，IOI 0AC得到Au，感觉没有谁同时拿过这三个成就了。
上午去water park，以为自己退役了无所畏惧了，还是被某大型水滑梯吓怕了。后来玩了几个小型的。
下午Exhibition。
闭幕式。
颁奖按排名从后往前的，然后我是Au上去的第二个。
又开始后悔D1T2了。
考挂滚粗回家。
退役了。
CJK猫，CJK强，CJK是FZYZ的红太阳
尽管immortalCO就要上大学了，但immortalCO永远是FZYZ的红太阳。
鄂公网安备 42010202000505 号Server time: 2024-11-21 13:11:38