oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

    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)-一中隊(duì)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)-一中隊(duì)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隊(duì)	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隊(duì)	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-楚風(fēng)	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隊(duì)	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.
中國地質(zhì)大學(xué)	cug(wuhan)
華中師范大學(xué)	ccnu
同濟(jì)大學(xué)	tongjiu
香港大學(xué)	hku
合肥工業(yè)大學(xué)	hfut
華東理工大學(xué)	ecust
華中科技大學(xué)	hust-
華東師范大學(xué)	ecnu
廣州大學(xué)	gzhu
武漢大學(xué)	whu
湖南大學(xué)	hnu
湖南商學(xué)院	hnbc
長沙學(xué)院	ccsu
湘潭大學(xué)	xtu
中南大學(xué)	csu
長沙市第一中學(xué)	cssyz(hs)
長沙市雅禮中學(xué)	csyali(hs)
長沙市長郡中學(xué)	cscj(hs)

PART I 比賽過程概覽：
    基本上整場比賽處于一種郁悶中。分題是我ABC,李佳鑫DEF，王要得GHI。E題發(fā)現(xiàn)的比較晚，好像是我把ABC都讀完了（都否決掉了簡單題的嫌疑)之后看到藍(lán)氣球之后叫李佳鑫趕緊給我講E題題意。按照計(jì)劃，我準(zhǔn)備把前面1-2道簡單題留給新人王要得來敲，我來敲后面的題。所以我又給王要得說了題意，然后把關(guān)他的程序過掉E。過掉E之后我對D題有信心，主要考察的是字符串的離散化（stl::map）和雙端優(yōu)先隊(duì)列（stl::set），想了想，這個(gè)題目給王要得估計(jì)不行。他對STL不熟，不可能現(xiàn)場教他STL吧。中間我和王要得討論了C題，因?yàn)镸S很多人扎堆做C題。我估計(jì)n^3的算法過不去，慣性地想了想凸包+二分。是王要得討論了下，是根本錯(cuò)誤的。王要得喜歡數(shù)學(xué)，我要他想想能不能找到n^2或者n^2 logn的算法。當(dāng)然，場上最后大家都是預(yù)處理對點(diǎn)距離+n^3算法水過去的，這是后話。于是我就搶了機(jī)器開始敲D。敲D，我認(rèn)為策略并沒有錯(cuò)，但是我沒敲好。敲第一行const int N = 10010；的時(shí)候，隱患就買下了。我沒有細(xì)想任務(wù)數(shù)有多少，迷糊中以為題目中的最大同時(shí)下載任務(wù)數(shù)就是任務(wù)數(shù)。后面的代碼也敲錯(cuò)好些地方，改來改去的。好不容易過了樣例和李佳鑫給我的數(shù)據(jù)，交上去一個(gè)WA，心都涼了。打印代碼，查錯(cuò)。既然過了那么多數(shù)據(jù)，肯定程序是沒有大錯(cuò)的。又仔細(xì)讀了題，果然發(fā)現(xiàn)一個(gè)漏掉的地方：Waiting & Downloading Task can both be paused.我以為只有Downloading。改了重交還是WA。發(fā)現(xiàn)自己沒有改完，后面有一段也要改。再改再WA.中間還有一次莫名奇妙的TLE，迫使我當(dāng)時(shí)優(yōu)化了一遍代碼。到那之后我就再也找不到錯(cuò)了。王要得覺得F題有規(guī)律，我也沒管了，讓他去敲。我則一遍一遍的看程序，給李佳鑫講程序，都沒有發(fā)現(xiàn)邏輯上的問題。我火了，等自己拿到機(jī)器，就開始測官方數(shù)據(jù)（就是在可能出錯(cuò)的地方寫大量的debug語句如while(1)，一個(gè)個(gè)來測試）因?yàn)轭}目中有很多東西是Assumed，不知道數(shù)據(jù)有沒有錯(cuò)。測試的時(shí)候果然發(fā)現(xiàn)數(shù)據(jù)有問題，因?yàn)槲业某绦驒z測到一個(gè)已經(jīng)pause的任務(wù)再次被pause掉！我仔細(xì)看了我的程序，不可能發(fā)生這種問題！頓時(shí)就崩潰了，終于我覺醒了，放下了D題，放下了機(jī)器，傷心地離開了鍵盤。王要得看到場上C題過得人過，示意要 n^3水一下。這個(gè)時(shí)候我沒報(bào)任何希望，我認(rèn)為n^3能過的話，場上應(yīng)該全是C題氣球了。下到場上，他們敲C，我開始審視A題。我心里明白，這場比賽肯定要丟人了。而我現(xiàn)在能做的，就是盡可能少丟點(diǎn)人！心里雖然些許不安，可是我還是很清醒的分析了A題。很快發(fā)現(xiàn)一個(gè)簡單的2次DFS的樹形DP就可以搞定。等他們C題TLE之后我上去敲了A。很高興的過了測試數(shù)據(jù)之后，Runtime Error。立即意識到爆棧了。說實(shí)話，樹形DP爆棧，人生第一次。我當(dāng)時(shí)想都沒想BFS的做法，就只記得去人工模擬棧了。現(xiàn)在回想起來，還不如改成 BFS。人工模擬棧我還真不會寫，而且我覺得我那個(gè)DFS還是以邊做DP的，更復(fù)雜了，壓棧還得壓點(diǎn)。我就只記得壓棧彈棧了，磨蹭了半天，就沒寫出個(gè)像樣的模擬棧出來！說我弱也好，說我煩也好，比賽還剩下最后的30分鐘，我丟下了A題。在王要得的建議下，用隨機(jī)去水C題，水啊水，就是水不過（已經(jīng)淪落到這個(gè)地步了，有什么辦法呢）到了最后5分鐘的時(shí)候，我心不死，再次翻出D題。砸頭一看就是一個(gè)const int N = 10010,心里一驚，怎么是10010呢！靠！不是100010嗎！馬上改了重新交，怕交不上，反復(fù)交了幾次。同時(shí)又把C題的程序交了幾次。就在那靜靜的等待死亡。過了又如何，不過又如何？已經(jīng)很丟人了，也罷也罷。但是看到D題YES之后還是興奮了一下的。就這樣，結(jié)束吧結(jié)束吧，化悲痛為食量吧。。。

PART II 失敗的原因
    整體上來說，這次alpc是全軍覆沒。部分原因是我們的主力們都分散到各個(gè)隊(duì)伍中了，可是這不是理由。即便是個(gè)人賽，我們的主力們也決不能賽成這個(gè)樣子啊！我是典型重犯，所以分析我的失敗原因亦是很有借鑒意義的。
    經(jīng)過我自己的反思，我把失敗的原由按照大小排序如下：
    1.D題我的敲題錯(cuò)誤和反復(fù)修改延誤了隊(duì)伍。影響了我思考其他題目，嚴(yán)重限制了我對其他題目的發(fā)揮，場上GHI我都不知道題目。
    2.題目沒有讀完。實(shí)際上他們倆讀了題，但是我深陷D題，我沒有去讀GHI。如果D題早些過掉，有時(shí)間看看F,I題，形勢會好過很多。
    3.沒有問過他們敲得C的細(xì)節(jié)，F(xiàn)的做法，因?yàn)樨瀼?人負(fù)責(zé)制。但是實(shí)際上我應(yīng)該對較難題目的算法全權(quán)負(fù)責(zé)，把關(guān)時(shí)間復(fù)雜度。
    4.根本原因：自己代碼能力下降了。敲題不在狀態(tài)。上兩個(gè)星期發(fā)生了太多無奈的事情，有少許影響。

PART III 失敗后的反思
    1。也許自己思維還過得去，但是不得不正視的是，我們和真正的高手比起來，代碼能力已經(jīng)差了一大截。對于Regional,我對于自己的定位可能仍然是敲題手，至少得先成為單挑很強(qiáng)的敲題手，才能很好的把握隊(duì)伍的動向（from dwyak，戴文淵，world final冠軍）。下個(gè)階段的訓(xùn)練可能主要針對的是自己的敲題能力，因?yàn)槲矣X得自己在比賽的時(shí)候敲代碼腦袋不清楚。tomek（world final冠軍，poland）是這樣說的：being forced to work on paper with no terminal access, I found I would solve the problems quicker。顯然，我會在以后加強(qiáng)紙上的訓(xùn)練，讓自己的手在鍵盤上的時(shí)候成為反射而不是邊想邊敲。或者至少也要敲得時(shí)候想清楚。
    2。正視ACM。如果真的喜歡ACM,要在ACM里面做出一番成績，不努力是不實(shí)際的。生活中總是有很多不順意的事情，你有他也有，他能化解，你也得學(xué)會化解。有時(shí)候會很累，可是為了自己喜歡的東西，又有什么關(guān)系。前段時(shí)間做web開發(fā)方面的事情很是分心，戀愛的事情也很分心，考試的事情還是很分心。前段時(shí)間答應(yīng)教授研究NP基礎(chǔ)理論方面的東西，現(xiàn)在連論文都沒看完，sigh。人總是進(jìn)步就好。ACM啊ACM，只有你才能讓我感覺得到自己的靈魂還在，而不是一個(gè)機(jī)器。

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