oyjpArt ACM/ICPC算法程序设计空间

    08年中南赛如期举行。
    废话不多说，先贴成绩。

Rank	School-Name	Solved	Time	A	B	C	D	E	F	G	H	I	Total att/solv
1	csyali(hs)-Yali-1	6	973	3/59	1/--	5/189	3/278	1/6	2/109	0/--	0/--	3/112	18/6
2	tongjiu-三喜馄饨	4	761	2/114	0/--	5/--	4/226	1/13	8/--	0/--	0/--	3/288	23/4
3	csyali(hs)-Yali-2	4	856	6/185	6/--	6/101	0/--	1/13	6/257	0/--	0/--	5/--	30/4
4	whu-GCC	3	376	6/--	0/--	1/85	0/--	1/18	7/153	0/--	0/--	7/--	22/3
5	cssyz(hs)-一中队1	3	497	5/169	0/--	1/--	1/--	1/9	0/--	0/--	0/--	2/219	10/3
6	csyali(hs)-Yali-3	3	516	5/67	0/--	2/--	0/--	1/22	4/287	0/--	0/--	5/--	17/3
7	hust-Struggle2008	3	655	5/245	2/--	2/--	0/--	1/11	4/259	0/--	0/--	0/--	14/3
8	hku-T1	3	680	7/266	0/--	18/--	0/--	1/9	3/245	0/--	0/--	0/--	29/3
9	whu-Eternal_Arbiter	3	896	19/254	0/--	27/--	6/--	1/13	5/189	0/--	0/--	0/--	58/3
10	hust-Excalibur	2	106	2/--	0/--	0/--	1/94	1/12	7/--	0/--	0/--	0/--	11/2
11	whu-BFS	2	126	0/--	0/--	3/61	0/--	1/25	0/--	0/--	0/--	0/--	4/2
12	whu-R2	2	158	13/--	0/--	1/142	0/--	1/16	0/--	0/--	0/--	0/--	15/2
13	hnu-Footman	2	209	1/--	0/--	0/--	2/--	1/6	0/--	0/--	0/--	3/163	7/2
14	csyali(hs)-Yali-4	2	219	46/--	0/--	0/--	0/--	2/17	2/162	0/--	0/--	0/--	50/2
15	cscj(hs)-CscjBBT3	2	226	3/178	0/--	1/--	0/--	1/8	5/--	0/--	0/--	8/--	18/2
16	cscj(hs)-CscjBBT2	2	229	6/--	0/--	0/--	1/--	2/13	3/--	0/--	0/--	1/196	13/2
17	alpc-alpcT1	2	269	0/--	0/--	44/--	5/172	1/17	0/--	0/--	0/--	0/--	50/2
18	hnu-sword	2	305	0/--	0/--	14/--	5/202	1/23	0/--	0/--	1/--	0/--	21/2
19	hfut-EarthShaker	2	343	0/--	0/--	0/--	2/--	1/9	4/274	0/--	0/--	0/--	7/2
20	gzhu-MayChord	2	368	0/--	8/--	2/--	2/--	1/19	5/269	0/--	0/--	0/--	18/2
21	cscj(hs)-CscjBBT1	2	397	6/273	3/--	0/--	7/--	1/24	3/--	0/--	0/--	6/--	26/2
22	hku-T2	2	446	0/--	0/--	3/--	2/275	4/91	4/--	0/--	0/--	0/--	13/2
23	csu-III.D	2	517	11/298	0/--	2/--	0/--	1/19	0/--	0/--	0/--	0/--	14/2
24	alpc-alpcT2	2	520	1/--	0/--	9/--	11/298	1/22	3/--	0/--	0/--	0/--	25/2
25	alpc-alpcT5	1	7	0/--	0/--	2/--	0/--	1/7	4/--	0/--	2/--	0/--	9/1
26	hfut-RP_GAO	1	9	0/--	0/--	1/--	0/--	1/9	4/--	0/--	0/--	0/--	6/1
26	whu-novices	1	9	0/--	0/--	18/--	0/--	1/9	2/--	0/--	0/--	0/--	21/1
28	ecust-SURE	1	10	2/--	0/--	8/--	0/--	1/10	1/--	0/--	0/--	0/--	12/1
29	alpc-alpcT8	1	11	0/--	0/--	5/--	0/--	1/11	1/--	0/--	0/--	0/--	7/1
30	alpc-alpcT15	1	12	2/--	0/--	1/--	0/--	1/12	1/--	0/--	0/--	0/--	5/1
30	alpc-alpcT3	1	12	6/--	0/--	1/--	0/--	1/12	3/--	0/--	0/--	0/--	11/1
32	alpc-alpcT12	1	13	0/--	0/--	0/--	2/--	1/13	0/--	0/--	0/--	0/--	3/1
32	ccnu-tower_rush	1	13	0/--	0/--	0/--	1/--	1/13	2/--	0/--	0/--	0/--	4/1
32	hnu-FM2008	1	13	1/--	2/--	0/--	0/--	1/13	1/--	0/--	0/--	0/--	5/1
35	alpc-alpcT7	1	14	3/--	0/--	41/--	0/--	1/14	0/--	0/--	0/--	0/--	45/1
36	alpc-alpcT14	1	15	0/--	0/--	1/--	0/--	1/15	0/--	0/--	0/--	0/--	2/1
36	alpc-alpcT4	1	15	0/--	0/--	1/--	0/--	1/15	3/--	0/--	0/--	0/--	5/1
36	cug(wuhan)-Three_Up	1	15	9/--	0/--	9/--	0/--	1/15	2/--	0/--	0/--	0/--	21/1
39	alpc-alpcT13	1	17	0/--	2/--	2/--	0/--	1/17	0/--	0/--	2/--	0/--	7/1
39	hnu-zealor	1	17	0/--	0/--	2/--	0/--	1/17	0/--	0/--	0/--	7/--	10/1
41	alpc-alpcT6	1	18	0/--	8/--	5/--	0/--	1/18	0/--	0/--	0/--	0/--	14/1
41	whu-Slash	1	18	4/--	0/--	0/--	8/--	1/18	0/--	0/--	0/--	0/--	13/1
43	cssyz(hs)-一中队2	1	20	7/--	0/--	4/--	0/--	1/20	6/--	0/--	0/--	0/--	18/1
43	hust-Apollo	1	20	0/--	0/--	1/--	1/--	1/20	14/--	0/--	0/--	0/--	17/1
45	alpc-alpcT9	1	21	0/--	0/--	1/--	5/--	1/21	0/--	0/--	0/--	0/--	7/1
46	xtu-Pursuer	1	22	0/--	0/--	4/--	6/--	1/22	0/--	0/--	0/--	0/--	11/1
47	ccnu-Athena	1	23	0/--	0/--	0/--	0/--	1/23	0/--	0/--	0/--	0/--	1/1
48	ccnu-Redligt	1	26	0/--	0/--	0/--	0/--	1/26	0/--	0/--	0/--	0/--	1/1
49	ccsu-希望2队	1	27	1/--	0/--	0/--	0/--	1/27	0/--	0/--	0/--	0/--	2/1
50	xtu-Opera	1	33	0/--	0/--	2/--	0/--	1/33	0/--	0/--	0/--	2/--	5/1
51	hnbc-雏鹰	1	35	0/--	0/--	0/--	0/--	1/35	0/--	0/--	0/--	0/--	1/1
52	alpc-alpcT11	1	39	0/--	0/--	3/--	0/--	1/39	0/--	0/--	0/--	0/--	4/1
52	ccnu-FollowDream	1	39	0/--	0/--	8/--	0/--	1/39	0/--	0/--	0/--	0/--	9/1
52	csu-RedFox	1	39	0/--	0/--	3/--	0/--	1/39	1/--	0/--	0/--	0/--	5/1
55	tongjiu-囧	1	42	3/--	0/--	0/--	0/--	2/22	2/--	0/--	0/--	0/--	7/1
56	hnbc-龙	1	57	0/--	0/--	0/--	0/--	2/37	0/--	0/--	0/--	0/--	2/1
57	csu-BlueWhale	1	59	0/--	0/--	0/--	0/--	1/59	1/--	0/--	0/--	1/--	3/1
58	ccsu-希望1队	1	64	0/--	0/--	6/--	0/--	1/64	0/--	0/--	0/--	1/--	8/1
59	ecnu-KOP	1	65	0/--	0/--	3/--	0/--	2/45	0/--	0/--	0/--	0/--	5/1
60	alpc-alpcT10	1	75	0/--	0/--	1/--	0/--	3/35	10/--	0/--	0/--	0/--	14/1
61	hnbc-楚风	1	76	0/--	0/--	3/--	0/--	2/56	0/--	0/--	0/--	0/--	5/1
62	ccnu-Sky	1	80	0/--	0/--	0/--	0/--	2/60	0/--	0/--	0/--	0/--	2/1
63	ccsu-希望3队	1	92	0/--	0/--	0/--	0/--	2/72	0/--	0/--	2/--	0/--	4/1
	Submitted/1st Yes/Total Yes			185/59/11	32/--/0	282/61/5	75/94/7	76/6/63	133/109/10	0/--/0	7/--/0	54/112/5	844/101

School	Abbr.
中国地质大学	cug(wuhan)
华中师范大学	ccnu
同济大学	tongjiu
香港大学	hku
合肥工业大学	hfut
华东理工大学	ecust
华中科技大学	hust-
华东师范大学	ecnu
广州大学	gzhu
武汉大学	whu
湖南大学	hnu
湖南商学院	hnbc
长沙学院	ccsu
湘潭大学	xtu
中南大学	csu
长沙市第一中学	cssyz(hs)
长沙市雅礼中学	csyali(hs)
长沙市长郡中学	cscj(hs)

PART I 比赛过程概览：
    基本上整场比赛处于一种郁闷中。分题是我ABC,李佳鑫DEF，王要得GHI。E题发现的比较晚，好像是我把ABC都读完了（都否决掉了简单题的嫌疑)之后看到蓝气球之后叫李佳鑫赶紧给我讲E题题意。按照计划，我准备把前面1-2道简单题留给新人王要得来敲，我来敲后面的题。所以我又给王要得说了题意，然后把关他的程序过掉E。过掉E之后我对D题有信心，主要考察的是字符串的离散化（stl::map）和双端优先队列（stl::set），想了想，这个题目给王要得估计不行。他对STL不熟，不可能现场教他STL吧。中间我和王要得讨论了C题，因为MS很多人扎堆做C题。我估计n^3的算法过不去，惯性地想了想凸包+二分。是王要得讨论了下，是根本错误的。王要得喜欢数学，我要他想想能不能找到n^2或者n^2 logn的算法。当然，场上最后大家都是预处理对点距离+n^3算法水过去的，这是后话。于是我就抢了机器开始敲D。敲D，我认为策略并没有错，但是我没敲好。敲第一行const int N = 10010；的时候，隐患就买下了。我没有细想任务数有多少，迷糊中以为题目中的最大同时下载任务数就是任务数。后面的代码也敲错好些地方，改来改去的。好不容易过了样例和李佳鑫给我的数据，交上去一个WA，心都凉了。打印代码，查错。既然过了那么多数据，肯定程序是没有大错的。又仔细读了题，果然发现一个漏掉的地方：Waiting & Downloading Task can both be paused.我以为只有Downloading。改了重交还是WA。发现自己没有改完，后面有一段也要改。再改再WA.中间还有一次莫名奇妙的TLE，迫使我当时优化了一遍代码。到那之后我就再也找不到错了。王要得觉得F题有规律，我也没管了，让他去敲。我则一遍一遍的看程序，给李佳鑫讲程序，都没有发现逻辑上的问题。我火了，等自己拿到机器，就开始测官方数据（就是在可能出错的地方写大量的debug语句如while(1)，一个个来测试）因为题目中有很多东西是Assumed，不知道数据有没有错。测试的时候果然发现数据有问题，因为我的程序检测到一个已经pause的任务再次被pause掉！我仔细看了我的程序，不可能发生这种问题！顿时就崩溃了，终于我觉醒了，放下了D题，放下了机器，伤心地离开了键盘。王要得看到场上C题过得人过，示意要 n^3水一下。这个时候我没报任何希望，我认为n^3能过的话，场上应该全是C题气球了。下到场上，他们敲C，我开始审视A题。我心里明白，这场比赛肯定要丢人了。而我现在能做的，就是尽可能少丢点人！心里虽然些许不安，可是我还是很清醒的分析了A题。很快发现一个简单的2次DFS的树形DP就可以搞定。等他们C题TLE之后我上去敲了A。很高兴的过了测试数据之后，Runtime Error。立即意识到爆栈了。说实话，树形DP爆栈，人生第一次。我当时想都没想BFS的做法，就只记得去人工模拟栈了。现在回想起来，还不如改成 BFS。人工模拟栈我还真不会写，而且我觉得我那个DFS还是以边做DP的，更复杂了，压栈还得压点。我就只记得压栈弹栈了，磨蹭了半天，就没写出个像样的模拟栈出来！说我弱也好，说我烦也好，比赛还剩下最后的30分钟，我丢下了A题。在王要得的建议下，用随机去水C题，水啊水，就是水不过（已经沦落到这个地步了，有什么办法呢）到了最后5分钟的时候，我心不死，再次翻出D题。砸头一看就是一个const int N = 10010,心里一惊，怎么是10010呢！靠！不是100010吗！马上改了重新交，怕交不上，反复交了几次。同时又把C题的程序交了几次。就在那静静的等待死亡。过了又如何，不过又如何？已经很丢人了，也罢也罢。但是看到D题YES之后还是兴奋了一下的。就这样，结束吧结束吧，化悲痛为食量吧。。。

PART II 失败的原因
    整体上来说，这次alpc是全军覆没。部分原因是我们的主力们都分散到各个队伍中了，可是这不是理由。即便是个人赛，我们的主力们也决不能赛成这个样子啊！我是典型重犯，所以分析我的失败原因亦是很有借鉴意义的。
    经过我自己的反思，我把失败的原由按照大小排序如下：
    1.D题我的敲题错误和反复修改延误了队伍。影响了我思考其他题目，严重限制了我对其他题目的发挥，场上GHI我都不知道题目。
    2.题目没有读完。实际上他们俩读了题，但是我深陷D题，我没有去读GHI。如果D题早些过掉，有时间看看F,I题，形势会好过很多。
    3.没有问过他们敲得C的细节，F的做法，因为贯彻2人负责制。但是实际上我应该对较难题目的算法全权负责，把关时间复杂度。
    4.根本原因：自己代码能力下降了。敲题不在状态。上两个星期发生了太多无奈的事情，有少许影响。

PART III 失败后的反思
    1。也许自己思维还过得去，但是不得不正视的是，我们和真正的高手比起来，代码能力已经差了一大截。对于Regional,我对于自己的定位可能仍然是敲题手，至少得先成为单挑很强的敲题手，才能很好的把握队伍的动向（from dwyak，戴文渊，world final冠军）。下个阶段的训练可能主要针对的是自己的敲题能力，因为我觉得自己在比赛的时候敲代码脑袋不清楚。tomek（world final冠军，poland）是这样说的：being forced to work on paper with no terminal access, I found I would solve the problems quicker。显然，我会在以后加强纸上的训练，让自己的手在键盘上的时候成为反射而不是边想边敲。或者至少也要敲得时候想清楚。
    2。正视ACM。如果真的喜欢ACM,要在ACM里面做出一番成绩，不努力是不实际的。生活中总是有很多不顺意的事情，你有他也有，他能化解，你也得学会化解。有时候会很累，可是为了自己喜欢的东西，又有什么关系。前段时间做web开发方面的事情很是分心，恋爱的事情也很分心，考试的事情还是很分心。前段时间答应教授研究NP基础理论方面的东西，现在连论文都没看完，sigh。人总是进步就好。ACM啊ACM，只有你才能让我感觉得到自己的灵魂还在，而不是一个机器。

PART IV 祝愿
    祝愿alpcs今年能取得好的成绩！alpcs开心最重要！
    特别祝愿alpc62早日完成心底的夙愿！