Contest Summary: PKU Monthly 2007 - 12
December 30th, 2007 2 Comments »
虽然这次题目有点偏……但是也不应该做成这样。(今天写代码的时候真的是小错误不断啊-_- 而且这好像也不是第一次了...)
比较郁闷的是，这次理论上应该有足够时间推B的，但是当时我把时间都花在其他题上了。而且看了题目分析之后明显感觉……
主要问题应该还是做得不够细心。
ACM/ICPC 2007 Regional Summary: Dhaka Site, Dec 5 - Dec 9
December 12th, 2007 No Comments »
比赛确实做的比较郁闷，比如刚开始的6道题我真的觉得可以在1.5-2hrs过掉的（当然考虑到键盘很不好用……和uva online的情况对比, 我们出的还是比较快的），之后的C/H/J如果不是当时我们队心理压力比较大+前面卡了一下，应该也可以很快出掉。
具体题目分析LynnKaye已经写了, 也没什么多说的必要了。总体说来主要原因是最近个人coding状态有点不正常，导致当时几道题拍得都很卡，最后写J的时候还因为当时被BUET踩心态稍微有点不稳导致出了很多小问题……（我真的没想到我还会出这种问题……但是当时由于C卡住，以及某些众所周知的原因可能确实比较紧张。不过这种情况不可能再次出现。）
另外East West University比赛真的组织的超赞，我个人感觉比南京长春北京都好很多。从很多方面明显能看出来他们做事的细心。不过有一个缺点就是赛场上打印代码不太方便-_- 我觉得停下来找志愿者打印很容易打断思路……然后当时的处理方法好像就是尽可能少打印，这个直接影响到了后期调试，还是有点郁闷。
其他方面没什么心情写，暂时这样吧。
另外还是要感谢这次比赛。很多事情不亲身经历过真的很难体会。
The past does not equal the future unless you live there.
ACM/ICPC 2007 Regional Summary: Beijing Site, Nov 7 – Nov 12
November 24th, 2007 No Comments »
Amethyst: Contest Rank: 4th / ICPC Rank: N/A
开头部分向来与比赛具体内容无关，所以不care这些流水账的同学们请跳过这里~
从长春到达北京。当时最令我感动的一点就是宾馆附近某家包子铺的香菇素菜包真的非常好吃(可能和没吃早饭有关-_-)~然后就开始郁闷复旦附近怎么就找不到那样的包子铺呢……
中科院软件所也是很pp的~
最赞的是晚上wyy带我们去的妙厨天香那家店~ 虽然我很抵制仿荤食品(我还是坚持我的观点……发明这种东西的人一定早上没睡醒) 但那家店的食物感觉还是很不错的~ 最终结论就是清华同学们的生活真美好~~
之后在zayoo同学带领下去THU游览。虽说去年来过清华，但是今年的感觉真的是和去年截然不同……或许是夜幕下的清华给人的一种莫名感觉的缘故吧。另外一路上碰见了很多神奇的人物~（另外据同是夜游清华的LynnKaye同学说，那天晚上曾经发生过光线单向传播事件……呃，我错了T_T）
BUAA: 11/9~11/11
其实我唯一不明白的就是北航既然都把住宿安排到四星的亚奥了为什么 饮食却弄成这样……再怎么说早餐也不能只提供面包／牛奶吧（我能吃的显然只有面包。。。）
###
正式比赛。
在这里我首先道歉，因为那天如果不是我连续拍挂B/H两道题我们队很有可能就7题了……当时我曾经莫名其妙的把B题写成DFS(还好在提交前改掉了…),并在H这种题上耗掉近1小时机时… 结果就是最后我郁闷的发现只要当时我有一道题不犯低级错误，我们队就有充足的时间的过掉I题了… (听上去怎么这么像南京-_-bbbbb)
其他方面，由于南京长春存在的那个分工不当的问题被改掉了，我觉得我们队当时的整体配合还是很不错的~
大体就是这样。
###
具体比赛过程请参见LynnKaye同学的日志。我还是直接说一下题目吧～
A: 标程据说就是基于集合划分的天真而又纯洁的动态规划~~不过Coldor他们似乎用一个搜索瞬间过掉了那题……当时没时间做了
B: 比较麻烦的BFS
C: BFS打表+查表
D: 没看过题，据说是简单题。
E: 线性规划……不过因为只有3维，所以可以投影做。
F: 据说看上去复杂, 但实际只要考虑清楚还是比较好做的物理题，不过这题不是我做的~
G: 直接枚举。同样没时间做，不过当时我没想到在单元格中点也可能发出射线
H: 无源最小费用流。不过当时写的时候某个地方没处理好，一直没过样例……最后在比赛还剩40分钟时无奈之下直接把找路径的地方改成O(N^3)的暴力方法，然后就过了-_- 最后据说标程是随便消圈* 而且*代码只有6x行……其实我当时好像也意识到了那题即使是任意序最多也只会消500次-_-bbbbb
I: 不错的动态规划题，推荐。大体思路是记录当前0的首指针和1的首指针，然后通过指针的关系判重＋统计方案数。
J: 首先每次询问的价格一定是递减的……然后推公式做就可以了。
Contest Summary: ACM/ICPC NWERC Regional Contest semilive
November 19th, 2007 No Comments »
做了半天唯一的感觉是好多牛人啊～～虽然这次题目几乎都很简单～
比如我们下面的MSU CrazySEx13居然有时间写完F+提交6次-_- （那题我觉得为了让代码顺利在时限内出解还是有很多优化要做的……peter曾经估计这道题要写300+行）
而coldor他们居然做了三个小时然后扔下两道计算几何跑了-_-我觉得这次的计算几何题还是不错的啊~总算不是纯体力活了~ 虽然F的代码量似乎还很大……
不过我们今天做的似乎就很水-_- 比如A交了3次H传达题意失误导致拍到一半重写J细节未考虑周全之类错误……
另外写Summary其实还是很有意思的～～～
ACM/ICPC 2007 Regional Summary: Changchun Site, Nov 2 – Nov 6
November 18th, 2007 No Comments »
Amethyst: Contest Rank: 23rd / ICPC Rank: N/A
题外话：
下火车的第一感觉是长春明显没有想象的冷啊~
不过长春的轻轨建设方式还是有点那个的……某些路段和马路并行+共用红绿灯，总感觉很容易出问题。
然后是吉林大学~几十个亿建成的校园果然不一般~~ 华丽到我们都在YY这是校园还是公园~~~ 不过校园和我们的住宿处就形成了鲜明的对比-_-
转到比赛。
练习赛那天我们中午吃完午饭回住处拿东西，但是由于大家都错误估计了从宾馆到赛场的时间(单程耗时近30分钟)，我们赶到赛场已经是比赛开始十多分钟之后的事了-_- 自然而然就发生了某件我怀疑让全场都记住我们队的事件-_-bbbbbbbb 这里就不提了 (据说当时声音大到很多人都停止做题去看怎么回事-_-不过之后有个小插曲：我们进场后peter瞬间秒掉一道题，然后我们似乎就变成场上第一个过题的队了……)
正式赛。整场比赛做的很郁闷，大体就是刚开始peter看到A可做，但是由于出了一点xxoo的交流问题，导致我自己冲上去拍……交上去RE, 和peter合作改掉两个bug后TLE. 这个时候我们还是O(2^N*NlogN)的暴力枚举，稍微考虑了一下优化成O(2^N), 再交就过了-_- 而这个时候已经80多分钟了。后来的一段时间我在非常天真纯洁地在想F 的O(MN^2)算法……直到2小时多放弃这个题; 同时Peter证出了E题的枚举可以限制在某个范围之内，然后提交并1Y。
这个时候由于我们没有可以写的题，LynnKaye决定写D。然后我转去看题发现H/I均可写； 但这时LynnKaye说D的程序效率太低 (而这时场上已经有不少队伍3题/4题了) 于是我转去协助D, 同时peter开始打G题的表格。(当然我那时大脑短路没发现D被我们想复杂了。。。 导致莫名其妙计算量多了10倍-_-bbbbbb)
另外我调D的过程中LynnKaye说F题O(MNMlogN)的算法一定可以过， 但当时由于我错误估计了最坏情况下复杂度坚决拒绝去写……比赛后却知道judge们的标准做法就是那样-_-bbbbbb 我错了……
这一段时间场上发生了很多神奇的事情——
1)主办方提示今天比赛很多的题目看起来可能很难但其实不是这样的，鼓励大家去尝试做题……但我们却没有一个人意识到Judge们的意思是今天很多题是可以水的-_-比如那道xx的F题……
2)由于场上过题队数过少裁判宣布放宽A的时限+Rejudge! 然后似乎一次放的时限还不够多，一会儿之后又第二次Rejudge——结果好象就是A无论多暴力的枚举都过了-_-bbbbbbb
3) 据说离比赛结束一个半小时主裁判曾经让大家去做字符串处理题I -_- “字符串处理那题很简单，现在写还肯定来得及.”(不过这句话我没听见……当然听见了我也不会去做的…)
总之过了一段时间就封Board了……这时D的程序仍然很慢（5~10组极限数据就足够让程序超时）而我感觉D我们的算法应该不是最优的但又没有什么更好的思路，无奈之下放弃D去写H；期间同时发现Peter G题的打表效率有问题……最后我拍H直到<10min过样例+自己出的数据提交&返回WA；LynnKaye修改D直到最后发现之前加的某个剪枝有问题，无奈之下删掉所有剪枝后提交居然返回WA而不是TLE-_-
然后比赛结束之后我郁闷的检查H的代码然后在10分钟内发现两个低级错误(当时拍的太急了……)当时有!@#$%^的冲动。。。
总体上说 我们的主要失误首先是我和LynnKaye没有尽早把题目完整地读一遍（我个人开始只读了A和F, 直到过了A之后才去读其他题目），而这直接导致初期错误的做题顺序；其次Peter的代码能力非常强而这两场比赛都主要在想题。再有一点就是我们最后应该集中精力去攻一道题；我相信D和 H如果再多一点时间应该都能过的。另外我们还有一点失误就是D的代码备份不够多 (没记错的话我们一共只留了2份……)
最后虽然这场比赛的题目比较不爽(暴力+打表 …) THU PKU等队伍仍然出了4~5题……我觉得这也说明了我们队存在的一些问题。
暂时到这里。
最后惯例，题目分析。
A: 枚举+凸包。朴素做法(O(2^N*NlogN)),优化后的复杂度是O(2^N). 这道题利用凸性质剪枝应该可以做到赛后裁判长说的N=40, 不过后来我没有测试过。
B: 搜索+打表, 当时据Metaphor队说他们的打表程序跑了2个多小时。
C: 首先枚举R-robot的修理方案，然后对于G-robot网络流检查解是否可行。
D: DP+剪枝-_- 比较郁闷的是我们之前一直在想怎么优化算法……最后10分钟决定交了才发现程序是错的-_-bbb
E: 据说给定的数的可分解性与a^2 + 2 * b^2是否为质数有关~具体我不会证，请参阅P大牛blog~ 但是据说这道题数据水到随便限一下边界枚举都能过……
F: 这是我整场比赛最无语的一道题了-_- 据说O(M*N^3)的算法优化一下常数就能过，而出题者的标准做法居然是O(MN*MlogN)! 而我当时一直在想计算量在10^7左右的算法-_-bbbbbb 另外这题的最优做法是最短路树。
G: DP+打表~~~复杂度应该是是O(N^4*logC)，不过当时我们打表的方式似乎有问题，导致程序效率很低。
H: 分块处理，或者线段树
I: 模拟题，但是当时由于在网络预赛中已经对JLU命的这种题有点心理阴影而没有做-_-
最后, Scoreboard以及成绩……