斯坦福大學(xué)王穎 淺談ACM ICPC的題目風(fēng)格和acm比賽近幾年

斯坦福大學(xué)王穎 淺談ACM ICPC的題目風(fēng)格和acm比賽近幾年

ACM ICPC的比賽形式一般是五個小時八個題目，綜合考察選手的數(shù)學(xué)能力、算法能力、coding能力和debug能力，還有團(tuán)隊配合能力。數(shù)學(xué)方面主要強(qiáng)調(diào)組合數(shù)學(xué)、圖論和數(shù)論這三個方面的能力；而算法的覆蓋范圍很廣，涉及了大部分經(jīng)典的算法，和少量較前沿的算法。由于每道題目都需要通過所有的測試數(shù)據(jù)才能得分，并且需要精確解，這限制了Approximation algorithm在一些NP-hard的題目中的運(yùn)用，從而使得搜索和剪枝策略對于NP-hard的題目非常重要。

Final的題目和Regional題目的比較

ACM ICPC官方的正式比賽可分為World Final和Regional Contest兩種。Final的題目更加正統(tǒng)和嚴(yán)謹(jǐn)，強(qiáng)調(diào)算法的綜合運(yùn)用，一個題目往往需要幾種算法的結(jié)合。從這幾年的final的題目看，final加大了題目的代碼量，對代碼能力的要求有所增強(qiáng)。而Regional的題目則更加靈活，同時每個賽區(qū)也有自己的出題風(fēng)格。歐洲賽區(qū)的題目以高質(zhì)量出名，對算法和數(shù)學(xué)的強(qiáng)調(diào)甚至超過了World Final；美國的賽區(qū)較多模擬題，強(qiáng)調(diào)代碼量。而亞洲則介于兩者之間，同時由于每年都有一些新的賽區(qū)，所以并沒有很固定的模式。


下面淺談一下近幾年ACM ICPC的題目的覆蓋面。一些常規(guī)的算法和題型沒什么好講的，下面主要側(cè)重一些新穎的知識點(diǎn)或題型，或是一些較前沿的內(nèi)容。

數(shù)學(xué)的新題型

除了一些基本的組合數(shù)學(xué)和組合數(shù)論的問題，近年來概率和Combinatorial Game Theory的題目逐漸增多。很多有趣的題目都是以Markov Process為背景，需要用到一些相關(guān)的知識。

去年國內(nèi)杭州賽區(qū)的一個很有趣的題目是，給出一個字符集（比如{A,B,C}）和一個字符串T（比如ACBBCAC），現(xiàn)在從一個空串S開始，每次等概率的添加A,B,C中的一個字符，直到T是S的一個子串。問得到的字符串S的長度的期望。這是一個典型的Markov Process，其解可以用生成函數(shù)很優(yōu)美的算出來。一個更有趣的版本是，假如還有另一個字串R，當(dāng)S中出現(xiàn)T或者R就終止，問終止在T和R的概率各是多少。這個問題在Graham, Knuth, 和Patashnik合著的Concrete Mathematics里面有詳細(xì)的分析，并有著一個優(yōu)美的結(jié)論。

Game theory方面，主要是經(jīng)典的combinatorial game theory而比較少Zero-sum game和Nash equilibrium的內(nèi)容。以前甚少選手知道的Sprague-Grundy Value現(xiàn)在已幾乎成了必備的知識。雖然大部分題目都是two-person perfect information impartial game，基本都可以用Sprague-Grundy Theorem解決，但也出現(xiàn)過misere play的情況。還有一些題目則是通過找規(guī)律和歸納解決。

Graph theory方面，上海賽區(qū)在多年前就出了一道Chordal graph recognition的題目，使得許多選手投入弦圖和區(qū)間圖的學(xué)習(xí)，并了解到完美圖理論；IPSC有一年出了consecutive ones problem，從而引起了選手們對PQ樹和平面圖判定的關(guān)注。

除此之外，還有一些零散的non-trivial的題目，甚至是一些非常involved的題目。如劉汝佳給達(dá)卡賽區(qū)出的一道unbreakable tiling的題目。其中我非常喜歡的一個題目是四年前東北歐賽區(qū)的一個floodlight problem：平面上給出n個點(diǎn)代表n盞燈，每個燈可以照亮圓心角為2*∏/n的一個扇形區(qū)域。問怎樣控制這些燈的角度，使得可以照亮整個平面。

還有一些數(shù)學(xué)題則考驗創(chuàng)造能力。比如有一題：給出n，要求找出一個n*n的方陣，其中每個元素都是1到n之間的整數(shù)，并且兩兩不等，同時使得每行、每列還有兩個對角線的和兩兩不等。這題的構(gòu)造頗為繁瑣，最簡單的方法是直接隨機(jī)生成再判定是否具有這個性質(zhì)。

近年來幾乎每年的final都有一道考察選手微積分能力的題目。而微分方程類題目較少。


大型線性方程組、復(fù)雜的矩陣代數(shù)、和特征值求解方面的題目較少。


算法的新題型
算法方面的增強(qiáng)主要體現(xiàn)在新的數(shù)據(jù)結(jié)構(gòu)不斷被選手所熟悉，和一些新領(lǐng)域的題目出現(xiàn)在ACM ICPC中。

數(shù)據(jù)結(jié)構(gòu)方面，一些特殊性質(zhì)的平衡樹逐漸被大家掌握，如splay tree，leftist tree等等。Interval tree則被廣泛用于計數(shù)。字符串方面，較容易實(shí)現(xiàn)的后綴樹組也逐漸被接受。


一些算法：網(wǎng)絡(luò)流方面，不少選手開始掌握push-relabel算法而放棄了經(jīng)典的ford-fulkerson算法；劉汝佳的書廣為傳閱后，不少選手又掌握了fractional programming和dinkelbach算法。目前能熟練實(shí)現(xiàn)linear programming的選手較少，但可以預(yù)計過一段時間這也會成為必備的技能。


計算幾何一直是ACM ICPC里面的難題。不僅編程困難，更由于精度問題導(dǎo)致非常難做對。計算幾何往往是在比賽時被放棄的題目。即使算法并不非常難，選手也不敢隨意去做。


一些零散的經(jīng)典內(nèi)容也被拿出來考察，如stable marriage，fft等。

總結(jié)和一些預(yù)計

基本上，實(shí)現(xiàn)起來不算太復(fù)雜的多項式時間復(fù)雜度的算法都可以出成一道ACM ICPC的題目。而出題者知識面的不停增長，也使得越來越多這樣的算法被包括。另一方面，隨著算法的發(fā)展，一些原本沒有簡單算法的題目也出現(xiàn)了新的解法，這樣的題目也被加入到ACM ICPC中。ACM ICPC經(jīng)過多年的積累有著大量的題目，其覆蓋面也是非常之廣。

斯坦福大學(xué)王穎 淺談ACM ICPC的題目風(fēng)格和acm比賽近幾年
可以預(yù)見一些新的優(yōu)秀的算法將陸續(xù)出現(xiàn)在ACM ICPC中。比如由于任意圖匹配的Edmonds-Carp算法實(shí)現(xiàn)起來非常繁瑣，使得ICPC中一直不出現(xiàn)任意圖匹配的題目（即使有也是規(guī)模非常?。?。而Vijay Vazirani的論文<