今天看了一下博弈（game theory）的幾個問題，看到了一篇文章，ikki的懷念自己ACM/ICPC日子的文章。

   全文轉載如下：

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

   突然很感慨，就像ikki最后一句，這一切都是似水流年。。。

   在Arena上有他的個人比賽記錄，看到了那句logo:Never underestimate or just rely on your potential.是對自己的忠告！加油！或許，某一天當ikki看到自己的這篇總結還能激勵著某些人前進行的時候，他或許也會感嘆一句，似水流年吧。。。。