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

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

Final的題目和Regional題目的比較

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


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

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

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

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

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

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

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

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

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


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


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

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


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


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


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

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

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

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