今天看了一下博弈（game theory）的幾個(gè)問(wèn)題，看到了一篇文章，ikki的懷念自己ACM/ICPC日子的文章。
全文轉(zhuǎn)載如下：
又是一個(gè)賽季……看到很多不知名的ID開(kāi)始在OJ上的出頭，看到以前我們傳統(tǒng)意義上覺(jué)得可能是“弱校”的一些學(xué)校也開(kāi)始奮起，真的很為他們感到高興，尤其是天津大學(xué)，看到天大已經(jīng)可以在沒(méi)有RoBa的情況下也能力壓其他的名校拿到學(xué)校名次第三，真的還是有很多感慨的。
于是，作為styc筆下的"a notorious martyr of acm/icpc"，懷念我的6次Regional。
1) Shanghai 2004
上來(lái)就全場(chǎng)第一個(gè)Submit了C - The Counting Problem，沒(méi)有看數(shù)據(jù)規(guī)模就暴力了一下，沒(méi)有任何懸念的TLE掉了，然后開(kāi)始搞H - Tian Ji - The Horse
Racing，看了一眼題目就說(shuō)是最大匹配，開(kāi)始拍匹配，又沒(méi)算復(fù)雜度，匹配匹完之后發(fā)現(xiàn)又TLE了……最搞笑的事情是我當(dāng)時(shí)還寫了個(gè)Hopcraft-Karp匹配……后來(lái)發(fā)現(xiàn)說(shuō)可以最優(yōu)匹配...當(dāng)然，也TLE了……
最后我在比賽場(chǎng)上幾乎就是無(wú)所事事，憑著我們隊(duì)長(zhǎng)jwise的神勇發(fā)揮在最后一個(gè)小時(shí)頂住全場(chǎng)N多氣球但是我們沒(méi)有氣球的壓力，把那兩個(gè)題目過(guò)了..最后一分鐘我好像是在貪心J - Jamie's Contact Group，后來(lái)才知道那個(gè)題目是個(gè)網(wǎng)絡(luò)流。
第一次比賽總是很難忘，不過(guò)現(xiàn)在回想起來(lái)除了反應(yīng)出來(lái)自己弱也沒(méi)什么其他可以說(shuō)的。
2) Beijing 2005
一個(gè)暑假在POJ上割了800+題目之后發(fā)現(xiàn)很多題目好像可以寫一寫了，這就有了自己的Beijing Regional之行。我如果沒(méi)有記錯(cuò)這場(chǎng)比賽是ACRush第一次出道acm/icpc，開(kāi)場(chǎng)3分鐘ACRush過(guò)掉了E – Holiday
Hotel，全場(chǎng)震驚，后來(lái)大家發(fā)現(xiàn)這是一個(gè)菜題紛紛AC，我好像是在10分鐘還是15分鐘過(guò)掉了這個(gè)題目。在這個(gè)時(shí)候ACRush過(guò)掉了G – Desert
King，15分鐘，過(guò)了2個(gè)，大家就紛紛覺(jué)得G也是個(gè)菜題，然后開(kāi)始看G，我也不例外……不過(guò)看著看著我先以為G可以貪心，后來(lái)想了想（我不記得有沒(méi)有交程序驗(yàn)證了），反正過(guò)不掉，后來(lái)突然想起來(lái)這個(gè)題目好像在SRbGa的黑書上有寫類似的……所以拿出黑書，找到“最優(yōu)比率生成樹(shù)”
，現(xiàn)場(chǎng)學(xué)算法，現(xiàn)場(chǎng)過(guò)掉了……好像那個(gè)題目還有一點(diǎn)點(diǎn)卡常數(shù)因子，因?yàn)槭浅砻軋D所以Kruskal過(guò)不掉，好像焦哥當(dāng)時(shí)是被卡在了這里。
過(guò)了兩個(gè)題目之后隊(duì)友發(fā)現(xiàn)了A – Angle and Squares是個(gè)弱題，寫了一下過(guò)了，中間好像還以為忘記了sin和cos是弧度制的調(diào)了很久……然后就是比較順利的用匹配過(guò)掉了C – Purifying Machine，當(dāng)時(shí)4題的時(shí)候自己真的以為快要出線了，因?yàn)楹孟襁€有兩個(gè)小時(shí)。
然后就是痛苦的2個(gè)小時(shí)了，先是看到了我覺(jué)得最有希望過(guò)的D – Finding Treasure，明顯就是一個(gè)高斯消元嘛，但是怎么都過(guò)不去……怎么寫也過(guò)不去，雖然后來(lái)我知道更簡(jiǎn)單的做法是隨機(jī)代點(diǎn)，但是高斯消元也是可過(guò)的……但是我就是過(guò)不去……B – Get Luffy
Out是個(gè)2SAT，但是我不懂2SAT……所以看著隊(duì)友眼睜睜的貪心了很久，很久很久……后來(lái)傳聞?wù)f這個(gè)題目數(shù)據(jù)弱，搜搜也過(guò)了……其他題目我連題目都沒(méi)看……
3) Hangzhou 2005
在Beijing拿了個(gè)第七，宋老師當(dāng)時(shí)還對(duì)我們隊(duì)寄予厚望說(shuō)爭(zhēng)取在杭州出線，我也真以為我們能圓個(gè)Final夢(mèng)，很開(kāi)心的去了杭州，這次比賽HQM，ZY，YSY好像是一隊(duì)，并且很順利的他們切掉了ACRush……
上來(lái)很順利的切了A – Auction，然后看到B – Bridge發(fā)現(xiàn)不會(huì)那個(gè)積分，看到C -
Cell我一下就開(kāi)心了，說(shuō)我KAO這不是個(gè)LCA么，拿出例程開(kāi)始敲，敲完發(fā)現(xiàn)RE了，頓時(shí)FT，以為數(shù)組開(kāi)小了數(shù)據(jù)不合法，所以測(cè)試了很久很久很久……甚至到最后自己開(kāi)始寫了一個(gè)測(cè)試機(jī)開(kāi)始生成數(shù)據(jù)，在自己機(jī)器上測(cè)試發(fā)現(xiàn)也RE了……那個(gè)時(shí)候想到原來(lái)是stack
overflow…我就問(wèn)隊(duì)友會(huì)不會(huì)把遞歸改非遞歸，得到的答案是不會(huì)……當(dāng)時(shí)我就知道這個(gè)題目，完全知道問(wèn)題在哪里，知道該怎么做，但是不可能過(guò)了……當(dāng)然了，后來(lái)我知道那個(gè)題目對(duì)應(yīng)于白色括號(hào)定理，可以直接DFS……但是還是要寫非遞歸的DFS，我還是過(guò)不掉，所以死在了DFS上。
B發(fā)現(xiàn)不可做之后我開(kāi)始翻手頭的大學(xué)數(shù)學(xué)書，在大學(xué)數(shù)學(xué)書上找到了一個(gè)類似的式子，把那個(gè)拋物線長(zhǎng)度積分積出來(lái)了，記得當(dāng)時(shí)的judge還有點(diǎn)卡常數(shù)，不過(guò)幸好，B – Bridge過(guò)了。當(dāng)時(shí)的情況我記得我的判斷是出4可以出線，所以只能拼題數(shù)了，把I –
Instructions丟給what20，what20看了看告訴我是貪心，他肯定能過(guò)，我就沒(méi)管了，后來(lái)發(fā)現(xiàn)怎么寫也不過(guò)怎么寫也不過(guò)，到最后比賽還有20分鐘結(jié)束我看了一下題目我說(shuō)KAO這不是個(gè)最短路么，刪掉他的支離破碎的程序開(kāi)始重寫……但是來(lái)不及了……在最后比賽結(jié)束的時(shí)候，我的程序好
像剛剛寫出了可以compile的雛形，but that’s definitely too late.
說(shuō)說(shuō)G – Generator，這個(gè)題目是具體數(shù)學(xué)上的原題，我的隊(duì)友猜出了一個(gè)公式，我口算了一下說(shuō)好像和答案差的遠(yuǎn)……根本沒(méi)試……2題，結(jié)束了杭州之行，連銅牌都沒(méi)有。
賽后Savior跟我說(shuō)的一句話，我到今天都記得。因?yàn)槲覀冊(cè)诒本┑拿握f(shuō)不定你該運(yùn)氣好還能出線，所以Savior說(shuō)：“Final見(jiàn)啦……” 這一句話成為我永遠(yuǎn)的傷，無(wú)限逼近但是永遠(yuǎn)進(jìn)不去……后來(lái)，我們還確實(shí)扎扎實(shí)實(shí)的為了從Beijing拿名額出線做了一番爭(zhēng)取，Beijing一開(kāi)始給了非常
少的名額，我就想去爭(zhēng)取這個(gè)名額，發(fā)信給李文新老師和黃金熊，北大的李文新老師還為
我們爭(zhēng)取名額，最后幫我們排名前面一位的USTC爭(zhēng)取到了，我們沒(méi)有……還記得當(dāng)時(shí)USTC在POJ的BBS上說(shuō)謝謝李老師，李老師說(shuō)不用寫我，要謝謝Ikki……哎，雖然看到USTC的兄弟出線也不錯(cuò)，但是好歹是為他人做了個(gè)嫁衣裳……
4) Beijing 2006
2006年，我準(zhǔn)備出國(guó)了，在準(zhǔn)備GRE和GRE SUB……所以我其實(shí)基本沒(méi)做什么準(zhǔn)備，但是這次組到了JiangYY同學(xué)和FreeDian同學(xué)，當(dāng)時(shí)我感覺(jué)這是南大近幾年能組出的最強(qiáng)隊(duì)了，所以對(duì)Final也充滿了美好的YY。
還記得JiangYY同學(xué)跟我說(shuō)：“拿金牌和出線哪個(gè)意義更大，我們顯然要出線……”好吧，那就出線吧，清華的比賽，賽前那一天晚上朱澤園同學(xué)跑來(lái)告訴我們說(shuō)明天你們不要緊張，我們賽前試題這套題目很簡(jiǎn)單，你們的實(shí)力應(yīng)該能做出7題……我在這個(gè)時(shí)候開(kāi)玩笑跟JiangYY說(shuō)，如果明天
考平面圖最大流你會(huì)做不，JYY說(shuō)當(dāng)然懂，我全懂，不就是Dijkstra么……我說(shuō)你會(huì)做就好，反正我是不懂……
比賽的時(shí)候FreeDian先告訴我E – Guess是貪心，迅速的過(guò)了E，當(dāng)時(shí)的速度好像差一點(diǎn)就是全場(chǎng)第一個(gè)過(guò)E的，然后發(fā)現(xiàn)H –
Ruler明顯可做，但是我不知道怎么做，當(dāng)時(shí)先猜了一個(gè)猜想，發(fā)現(xiàn)猜想不對(duì)，后來(lái)搜，發(fā)現(xiàn)那個(gè)數(shù)據(jù)規(guī)模搜肯定超時(shí)了，所以我就問(wèn)JiangYY 同學(xué)怎么做，我說(shuō)“JiangYY你不是還寫過(guò)如何搜索的文章么……你搜一個(gè)。”JiangYY同學(xué)說(shuō)毛……我搜不出……后來(lái)實(shí)在沒(méi)辦法了，我開(kāi)始加隨機(jī)
化的剪枝和一些小的優(yōu)化，并且拿一個(gè)暴力的搜索和那個(gè)隨機(jī)化的優(yōu)化在不停的對(duì)拍，等到對(duì)拍那個(gè)優(yōu)化后版本能全過(guò)了，我就交。
為了這個(gè)題目我寫了N個(gè)貪心版 + 一個(gè)暴力版 + N個(gè)改進(jìn)優(yōu)化版 + 數(shù)據(jù)生成對(duì)拍器，當(dāng)我過(guò)了之后我興奮不已，但是細(xì)細(xì)一看，咦，我好像交錯(cuò)程序把那個(gè)暴力版交上去了，我KAO，原來(lái)這個(gè)題目數(shù)據(jù)弱，暴力搜索就能過(guò)……當(dāng)時(shí)要?dú)⑷说男亩加辛恕?
差點(diǎn)忘了本次比賽最戲劇性的場(chǎng)景了，JiangYY同學(xué)翻題目，翻了一下告訴我說(shuō)“昊哥，真的出平面圖最大流了。”我說(shuō)那好啊，你不是會(huì)做么……JiangYY同學(xué)說(shuō)：“會(huì)個(gè)毛，我就知道Dijkstra，不知道怎么Dijkstra。”我KAO當(dāng)時(shí)我在場(chǎng)上心都涼了，然后YY同學(xué)就在不停的建模怎么Dijks
tra……一會(huì)告訴我要三次，一會(huì)告訴我要6次，一會(huì)告訴我要12次Dijkstra……這就是B – Animal Run的悲慘遭遇。
后來(lái)YY同學(xué)，自稱為過(guò)了USACO所有Gold Contest圖論題，圖論小王子的YY同學(xué)，開(kāi)始搞G – What a Special
Graph，然后一會(huì)告訴我要收縮一下花做DFS啥的……后來(lái)我說(shuō)不對(duì)…幸好我沒(méi)被迷惑住開(kāi)始敲G……賽后和Bamboo的一句話，Bamboo 說(shuō)：“我們判斷一個(gè)隊(duì)，有沒(méi)有前途，就是看他在不在搞G，如果在搞，就沒(méi)前途了……”G是個(gè)論文題，不可做的…當(dāng)然了，這套題目我當(dāng)時(shí)在賽場(chǎng)上好像是
都看了的，A – Robot有點(diǎn)想法但是不會(huì)，I – A Funny Stone Game太像DP了，但是也不會(huì)……都不會(huì)@_@
2題，再一次結(jié)束了，結(jié)束了我本科生涯的acm/icpc。
5) Seoul 2007
陰差陽(yáng)錯(cuò)的來(lái)到了HKUST之后，可以出國(guó)比賽，Seoul和Danang也成為了人生acm/icpc的絕響，最后的兩個(gè)第四也讓我永遠(yuǎn)對(duì)Final說(shuō)了聲再見(jiàn)。其實(shí)Seoul的失敗，可以說(shuō)死在我的手上，B –
Editor是一個(gè)非常弱的最長(zhǎng)公共子串的題目，串長(zhǎng)小于5000，明顯DP嘛，不知道我當(dāng)時(shí)大腦為什么抽筋了，開(kāi)始寫Suffix Array，而且還是寫的是線性時(shí)間的Suffix
Array，寫完之后發(fā)現(xiàn)自己很久沒(méi)寫后綴數(shù)組了，過(guò)不去了，調(diào)不過(guò)樣例，這個(gè)時(shí)候細(xì)細(xì)一想才把B用近乎暴力的方式過(guò)了……這個(gè)時(shí)候在時(shí)間上我們已經(jīng)浪費(fèi)將近一個(gè)小時(shí)了，后來(lái)發(fā)現(xiàn)如果我們把這一個(gè)小時(shí)節(jié)約在罰時(shí)上，每個(gè)題目都少了不少的時(shí)間，我們應(yīng)該就第三名出線了……第三名
也是7題，罰時(shí)比我們好一點(diǎn)，比我們少了123分鐘的罰時(shí)，如果我們這道題目沒(méi)有按照我YY的方式做，就……應(yīng)該是第三了吧？
當(dāng)然，現(xiàn)實(shí)沒(méi)有如果，而且我那兩個(gè)隊(duì)友當(dāng)時(shí)還問(wèn)我說(shuō)是不是可以DP的樣子，我直接斬釘截鐵的說(shuō)“不可以！”并且告訴他們這個(gè)是后綴數(shù)組經(jīng)典題，他們聽(tīng)完就不說(shuō)話開(kāi)始任我YY的寫了……
我犯的第二宗罪就是那個(gè)I – Turtle Graphics，當(dāng)時(shí)我過(guò)完一遍題目看到I – Turtle
Graphics之后我頓時(shí)就想到了CERC還是NEERC一道也是這種走水平豎直方向亂搞的題目，那個(gè)題目我好像不會(huì)，頓時(shí)心理陰影產(chǎn)生了，當(dāng)隊(duì)友問(wèn)我這個(gè)題目可做否，我直接一句話“這個(gè)題目我以前好像看過(guò)，不會(huì)做，你們別看了……”從始至終，那道I就沒(méi)有被我們碰過(guò)……后來(lái)發(fā)現(xiàn)是個(gè)弱
題。
人說(shuō)，自作孽，不可活。
6) Danang 2007
其實(shí)Danang賽區(qū)我對(duì)自己的表現(xiàn)也還是滿意的了，主要是題目太RP，同樣的C – Prime k-tuple，某隊(duì)Miller-Rabin就能過(guò)，我Miller-Rabin就TLE，D – The longest constant
game，這次確確實(shí)實(shí)是要上后綴數(shù)組了，很可惜我只帶了O(nlogn)版本的，發(fā)現(xiàn)居然卡這個(gè)logn的常數(shù)，后來(lái)實(shí)在沒(méi)辦法亂搞了O(n) 的后綴數(shù)組才過(guò)，E – Lazy Susan，這個(gè)題目我和Math Guy現(xiàn)場(chǎng)推了好久的規(guī)律，最后搞出來(lái)的時(shí)候真的是非常興奮，J –Space
Beacon，這個(gè)題目是我最怕寫的題目，陳琛敢于上手，并且在最后WA的時(shí)候我給他現(xiàn)場(chǎng)寫數(shù)據(jù)生成器暴力對(duì)拍，在最后2分鐘的時(shí)候過(guò)掉這個(gè)題目，PH的一聲咆哮Yes，全場(chǎng)為我們的鼓掌……雖然最后由于種種原因詭異的被Rejudge了一個(gè)題目排名掉到了第四，但是第一次，讓我感覺(jué)在賽場(chǎng)
上似乎沒(méi)有遺憾。在4小時(shí)封板的時(shí)候我也第一次看到了Hong Kong University of Science and Technology居然站在當(dāng)時(shí)的第一位上，離Final的夢(mèng)，當(dāng)時(shí)讓我感覺(jué)是這么近。
這么多次，其實(shí)合作最愉快的還是在HKUST，盡管隊(duì)員的實(shí)力不是特別強(qiáng)，但是他們肯配合我肯為我做事情想題目，一直堅(jiān)持不放棄的精神我也一直可以看到……真的很希望能和他們一起站在Final的賽場(chǎng)上。
只是可惜，這一切都已經(jīng)是似水流年。
突然很感慨，就像ikki最后一句，這一切都是似水流年。。。
在Arena上有他的個(gè)人比賽記錄，看到了那句logo:Never underestimate or just rely on your potential.是對(duì)自己的忠告！加油！或許，某一天當(dāng)ikki看到自己的這篇總結(jié)還能激勵(lì)著某些人前進(jìn)行的時(shí)候，他或許也會(huì)感嘆一句，似水流年吧。。。。