国产精品免费观看在线,国产一区二区三区日韩欧美,久久国产精品高清

ACM題目的風格和近幾年題目的發展

Posted on 2010-08-21 21:47 Kevin_Zhang 閱讀(296) 評論(0) 編輯收藏引用所屬分類: ACM基礎知識

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

Final的題目和Regional題目的比較

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

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

數學的新題型

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

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

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

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

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

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

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

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

算法的新題型

算法方面的增強主要體現在新的數據結構不斷被選手所熟悉，和一些新領域的題目出現在ACM ICPC中。

數據結構方面，一些特殊性質的平衡樹逐漸被大家掌握，如splay tree，leftist tree等等。Interval tree則被廣泛用于計數。字符串方面，較容易實現的后綴樹組也逐漸被接受。

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

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

一些零散的經典內容也被拿出來考察，如stable marriage，fft等。

總結和一些預計

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

可以預見一些新的優秀的算法將陸續出現在ACM ICPC中。比如由于任意圖匹配的Edmonds-Carp算法實現起來非常繁瑣，使得ICPC中一直不出現任意圖匹配的題目（即使有也是規模非常小）。而Vijay Vazirani的論文<<matching is as easy as matrix inversion>>中給出了一種通用的通過矩陣求逆而求各種匹配的算法，雖然該算法實現起來有一個難點，但相信將會被一些選手采用，從而出現一些任意圖匹配的題目，甚至更困難的exact match（該問題目前沒有deterministic polynomial-time algorithm，但用上面的方法可以得出一個概率算法）。

而一些新的領域也必將給ACM ICPC的出題者帶來靈感。例如已有越來越多Bio-informatics的題目在ICPC中出現。一些有著多項式算法的好題目，如inversion distance of signed permutations，則由于其理論的復雜而尚未出現在題目中。

圖論中還有數不勝數的好的題目，比如linear time求minimum cut，還有Gomory-Hu tree的應用，這些也必將在不久的將來出現在ICPC題目中。

我認為將發生的另一個趨勢是，隨機算法，概率算法和近似算法會在ACM ICPC中占更大的比重，至于對于算法能力和代碼能力考驗的平衡，我個人非常喜歡數學和算法，我希望Final的題目能向中歐賽區的題目靠攏。

ACM ICPC考察的不僅僅是對經典算法的理解和掌握，創造算法的能力同樣非常重要。學那么多算法，必須從中有所領悟，才能在賽場上有靈感去解決實際的問題。

如果大家有興趣的話我可以找幾個具體的問題詳細分析，或是討論一些具體的算法理論。同樣的我也樂意分享一些ACM賽場上的經驗，和在各大算法比賽中認識的一些有趣的人，和經歷過的一些有趣的事。匆匆寫完此文，疏漏之處在所難免，邏輯上也不甚連貫，希望大家見諒。

只有注冊用戶登錄后才能發表評論。


相關文章: ACM中無輸入結束提示時如何判斷到達EOF ACM題目的風格和近幾年題目的發展遞歸方程組解的漸進階的求法——差分方程法算法的復雜性 ACM的算法（覺得很好，有層次感) 見過的一個計劃算法書建議收藏 ACMer應具備的能力 pku1004

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

登山之道

ACM題目的風格和近幾年題目的發展

日歷

常用鏈接

隨筆分類

隨筆檔案

文章分類

文章檔案

程序的靈魂--算法

沙場秋點兵，壯士凱歌還

他山之石，可以攻玉

圍觀強人

搜索

最新評論

閱讀排行榜