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