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