ACM/ICPC 2007 Regional Summary: Changchun Site, Nov 2 – Nov 6
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以及成绩……