ACM/ICPC亞洲區預選賽命題經驗談

　　摘要：ACM國際大學生程序設計競賽，是世界上規模和影響力最大的大學生程序設計競賽。從2008年至2010年，筆者依托北京大學，先后承擔了國內4次亞洲區預選賽的命題工作，積累了一定經驗，也有一些教訓，寫出來與大家分享，希望對兄弟院校今后的命題工作，以及ACM/ICPC選手和教練們有參考價值。
　　關鍵詞：ACM/ICPC；亞洲區預選賽；題目；數據；算法
　　
　　1ACM/ICPC的題目形式、賽制及中國區命題的現狀
　　ACM國際大學生程序設計競賽(ACM International Collegiate Programming Contest，簡稱ACM/ICPC)是全球規模最大，最有影響力的大學生程序設計競賽，它始于1970年，到2010年為止已經舉辦了35屆。
　　ACM/ICPC的形式是三名隊員在5小時內用一臺電腦編程解決8～12道題。每道題由英文題目描述(題面)、標準輸入數據和標準輸出數據三部分組成。英文題面中包含很小一部分輸入數據及其對應的輸出數據，以作為Sample(樣例)。參賽者須根據題目描述編寫程序，該程序讀入標準輸入數據，其輸出必須和標準輸出數據完全一致，而且要在題目規定的時限內(通常是兩三秒，超過10秒的極少)算出結果，才算通過該題。完整的標準輸入數據和標準輸出數據選手們是看不到的，選手的程序提交到裁判的機器上，裁判以標準輸入數據作為輸入運行其程序，然后取得該程序輸出結果和標準輸出數據進行比對，以判斷該程序是否通過。必要時也會用人工來比對輸出結果。比賽最終以通過題目的數量多少來決定名次，過題數相同的，以做題速度區分高下。
　　例如，著名的“A+B Problem”，題目就是：輸入兩個數，請輸出他們的和。標準輸入數據是成對的數，標準輸出數據是每對數的和。當然，真實的競賽是不會有這么簡單的題目，這里只是用它來說明題目的形式而已。
　　ACM/ICPC的競賽題，都是需要編程解決的問題。因此，一道完整的題目，除了英文題面、輸入和輸出數據外，命題者還要提供標準程序(標程)。標程必須在題面規定的時限內，由標準輸入數據計算出標準輸出數據。
　　ACM/ICPC的賽制是每年的9月到12月在各大洲進行預選賽，選拔出優秀隊伍100支左右參加第二年3、4月份進行的全球總決賽。
　　目前，在預選賽階段，中國大陸有5個賽站(賽站并不固定)。因此，每年有5個大學會承辦ACM/ICPC亞洲區預選賽。例如，2010年，哈爾濱工程大學承辦哈爾濱賽站的比賽，天津大學承辦天津賽站的比賽，浙江理工大學承辦杭州賽站的比賽，四川大學承辦成都賽站比賽，福州大學承辦福州賽站比賽。
　　中國的大學申辦ACM/ICPC亞洲區預選賽比較踴躍。但是，有信心或愿意獨自命題的學校并不多(為何如此后文會解釋)。因此，許多大學在承辦比賽時，會委托ACM/ICPC實力較強的學校代為命題。除北京大學外，復旦大學、浙江大學、中山大學都曾為別的大學舉辦的亞洲區預選賽命題。
　　筆者依托北京大學，從2008年至2010年，先后為國內4次亞洲區預選賽命題。這4次比賽的承辦者分別是：北京交通大學(2008年)、浙江大學寧波理工學院(2009年)、浙江理工大學(2010年)和福州大學(2010年)。
　　表1是最近11場中國大陸亞洲區預選賽的比賽結果統計，其中打星號的比賽由北京大學負責命題。
　　北京大學的命題區分度好、難度適中，從未Rejudge (因題目錯誤，或其他原因導致必須對選手們提交的程序重新評判)，因而獲得參賽選手和教練們的廣泛好評。2009年ACM/ICPC中國區指導委員會曾經評選過“優秀命題獎”，北京大學獲得此項榮譽。
　　2ACM/ICPC對題目的要求
　　筆者從2004年起擔任北京大學ACM/ICPC競賽教練，率隊參加過二十多次亞洲區預選賽和六次總決賽，此外還有一定命題經驗，因而對什么題目是ACM/ICPC的好題，有一點自己的看法，希望能與大家探討。
　　筆者認為，一道ACM/ICPC的好題，應該滿足以下條件：
　　1) 題面和數據正確。這是最基本的要求。其中，常見的錯誤是輸入數據的范圍超過了題面所說的范圍。
　　2) 題目描述易于理解，沒有歧義。中國人用英文寫題面給中國人看，如果出題者不仔細斟酌，不同人讀題很可能就會有不同的理解。選手按錯誤的理解去編程，就是一場災難。這樣的題目，必然會遭人詬病。雖然賽場上可以在有人提問后發現二義性問題并且發Clarification予以澄清，但還是比較狼狽的。
　　3) 數據要足夠強。所謂足夠強，有兩個方面的含義，一是指數據里應包含各類邊界條件、特殊情況等(如果有的話)，使得做題者一旦有某個地方考慮不周，就會得出錯誤答案；二是數據應盡可能讓那些算法時間復雜度比標程高五六倍的程序不能在題目規定的時限內算出結果。這第二條有相當的難度，因為，有些程序的算法，其平均復雜度并不比標程更高，只有在最壞情況下才會比標程慢很多，為了要卡住這樣的程序，設計的數據就要包含各種投機取巧算法的最壞情況，使得那些算法無法通過檢驗。
　　4) 程序需要有一定的代碼量。畢竟這是程序設計競賽，如果十幾行代碼就能完成，就算題目設計精巧，思路巧妙，也難說是個好題。當然，比賽中最簡單的題目，可以不作此要求。
　　5) 題面不能太短，而且要有一個故事。題目最好不要是純粹的一個已經抽象好的算法或數學問題，應該用一個故事將這個問題包裝起來，這樣才能對參賽選手的英文閱讀能力和問題的抽象能力有一定要求。
　　6) 題目要有新意。不要和陳題類似，也不要單純地、不加變化地考某個算法，即不要讓選手照抄某個算法的模板就能通過，最好讓選手在建模上就需要花費時間思考。
　　在滿足上述幾條的基礎上，若還能一題多解，則更是錦上添花。
　　由上所述可以看出，ACM/ICPC競賽題，尤其是中等以上難度的題目，對命題者有很高的要求。命題者不但英文要好，而且還要考慮問題足夠縝密；不但要通曉題目所用到的算法原理，而且還必須具有編程實現該算法的能力；當然，還要有一定的想象力和創造性，才能編出有新意的題目，包括題目里的故事也要生動有趣。
　　ACM/ICPC命題費時費力，對于沒有參賽經驗的人來說，哪怕是專門研究算法的教授，出一道好題也并非易事，何況教授們往往也不愿意在此事上花費精力。所以，到目前為止，國內亞洲區預選賽的絕大多數題目，都是由ACM/ICPC的現役或退役選手編寫的。對于ACM/ICPC實力不強的學校來說，沒有足夠多的高水平選手，為亞洲區預選賽命題就成為一項比較困難的任務。所以，許多承辦亞洲區預選賽的大學，往往請別的學校代為命題，或自己出一些相對簡單的題目，委托其他學校出難題。
　　前面說了一道題怎樣才算好題，下面再來談談一套什么樣的題才能算好題。
　　ACM/ICPC官方提到過，一套好題應滿足以下三個條件(當然不要出錯是起碼的)：
　　1) 每個參賽隊伍至少能通過一道題。
　　2) 每一道題目都有隊伍能夠通過。
　　3) 沒有隊伍能夠做出所有的題目。
　　這三個條件得到了大家的廣泛認可。但是以筆者經驗看，一套題目，只滿足這三個條件，還不足以稱為好題。筆者個人認為，一套好題，還應該滿足以下條件：
　　4) 比賽結果有足夠的區分度。
　　5) 第一名至少能過7道題(一般比賽都是10道題)。
　　6) 題目覆蓋知識面要比較廣。
　　
　　7) 題面長短搭配合適。
　　8) 題目要求有一定的代碼量。
　　上述的第1條，并不容易做到。因為現在每個賽站參賽隊伍多達120支到150支，有的隊伍并非是經過網絡預選賽選拔出來的，而是主辦方為支持當地競賽發展而邀請的，隊伍水平有限。為確保所有隊都能過題而出一個像“A+B Problem”這樣的題，沒有意思，也不是命題者所愿。在中國大陸2009年和2010年共10場亞洲區預選賽中，只有3場做到了所有隊都能至少能通過一道題。
　　第2條也不容易做到。為了防止有參賽隊能做出所有的題而使題目顯得太簡單，或希望通過出難題來顯示水平，許多學校會出一兩道難度很高，甚至根本不可做的題來壓軸。這樣的題目，往往導致沒有人通過，甚至根本沒有人提交。因此，在亞洲區預選賽上，2道題無人能過的現象也不少見，在2009—2010年的10場比賽中，其中5場有2道題無人通過，僅有4場是所有題都有隊伍通過。
　　第3條是普遍現象。在中國大陸賽區，2010年前從來沒有一支隊能在比賽時通過所有的題目。2010年的哈爾濱賽站，第一次出現了一個隊做完所有題目的情況；在后來的福州賽站，則有3支隊通過了所有的題。
　　第4條非常重要，筆者甚至感覺區分度是大多數教練判斷一套題目好壞的最重要標準。如果同樣的題數的二、三十支隊，一半得銀獎，一半得銅獎，那么落后的隊伍必定心中不服，認為該場比賽偶然性太大。
　　第5條指的是題目不可太難。國內的比賽曾經不止一次出現過冠軍只做了4道題的情況，這樣的題目，必然區分度也不好，是很難得到大家好評的。
　　第6條，一套題目一般應該覆蓋到以下算法類型：搜索、計算幾何、圖論、數學、動態規劃、數據結構、模擬。
　　第7條，因為總決賽題面一般較長，英文閱讀能力對于總決賽上取得好成績也比較重要，因此筆者認為短題目不應太多。
　　第8條，畢竟是程序設計競賽，不能光靠思考能力取勝，代碼編寫能力也很重要。因此題目應該要求有一定的代碼量，這也和總決賽的要求吻合。
　　3北京大學命題的指導思想
　　筆者一般按照以下幾條指導思想進行命題：
　　1) 題目的難度分布一般是2道最簡單的題，2道中等偏易題，3道中等難度題，3道難題。希望一個半小時內能有隊伍通過4題。
　　2) 比賽時不可能做出的題不出。
　　3) 最容易的題目應該是開賽10到15分鐘即被做出，但很弱的隊，也要等到最后一小時才能將其通過，這樣的題才有技術含量。
　　4) 傾向于讓選手們多過題，希望第一名能通過9題。選手們辛辛苦苦訓練一年，為的就是體驗在賽場上過題的感覺，那么命題者就應盡量讓選手們多體驗一下這種感覺。因此，題目不可太難。但是北京大學近來4次的命題，總有10支左右的隊伍一道題也做不出，這是否和讓選手們多過題的思想矛盾呢？其實不然。因為在我校出的題目中，最簡單的題目一般都是用多重循環窮舉即可解決的，這樣的題目如果5個小時都做不出來，只能說明做題的隊伍根本沒有經過任何訓練。沒有付出，自然也應該沒有收獲。
　　5) 計算幾何、搜索、動態規劃是必考的。計算幾何還常考兩道，其他題型基本上也都能覆蓋到。
　　6) 題面一般較長，向總決賽靠攏。筆者傾向于去掉Sample Input(輸入樣例)和Sample Output(輸出樣例)的部分就應該至少占滿一頁紙。
　　7) 強調代碼實現能力。
　　4北京大學命題的過程
　　從2008年至今，所有題目都由北京大學在校的ACM/ICPC現役/退役隊員，以及筆者編寫。共有10名隊員參加過ACM/ICPC亞洲區預選賽的命題，他們全部獲得過亞洲區預選賽金獎，其中8名隊員參加過總決賽。每套題目一般有6～7名隊員參與命題。出題和驗題的是同一班人馬。每道題由兩個人驗，每個人出一道題，就要驗兩道題。出題者須寫承諾書，承諾不得向任何命題組以外的人提及有關題目的任何信息。
　　有的學校采取的是一組人出題，全套出完后另一組人驗題的方式。筆者擔心，如果驗題時才發現難度不合適需要返工，那代價就太大了，因此沒有采用這種方式。
　　筆者的工作是組織學生反復開會討論題目和驗題(一套題一般要開5～6次會)，把握難度和題型，修改甚至重寫所有題目描述，以及最后檢查所有題目的正確性。筆者還完整編寫過3道題，其中兩道是簡單題，一道中等偏易。此外，有3道計算幾何題的問題也是筆者提出。具體的流程如下：
　　1) 確定要參加命題的同學以及題目的類型(即要考查的算法)分布和難度分布。
　　2) 根據每個同學的長處，以“自愿+指定”的方式，為同學們分配題目類型和難度。比較意外的是，同學們并沒有搶著要出簡單題(所有題目給的報酬都是一樣的)，因為筆者要求簡單題也必須有點新意，要有一個好故事，而想一個好的簡單題也不容易。同學們同樣沒有回避出難題，因為能出一道難題，出題者自己也挺有滿足感。總之，在出題和驗題方面，都沒有發生過挑肥揀瘦的事情。
　　3) 等有了題目想法后，同學們進行討論。根據大家的評價來判斷題目的難度是否合適。
　　4) 寫出完整的題目并進行驗題。
　　驗題時基本上筆者都在場，根據驗題者的表現重新評估題目難度。偶爾會發生需要增減難度的情況，一般都可以通過修改題目條件完成。
　　學生的英文普遍不夠好，寫出來的題面往往晦澀難懂，歧義較多。因此，修改甚至重寫每一道題的題面，是筆者在命題中最花時間的工作。第一次負責命題時，筆者甚至花了5個小時改寫一道很長的模擬題。隨著學生年級增長和經驗增加，他們寫的題面也越來越好，修改題面的工作就會輕松一些。
　　題面寫完后，會找一個有計算機背景的人讀一遍，詢問其是否理解了每個細節。如果理解有偏差，就要改題面。與其強調讀者再認真再仔細點就不會看錯，還不如寫題的寫得再直白再明確一些。題面改寫后，還會返回給出題者看。這一點非常重要，因為對個別題目，筆者可能會忽略了一些細節，導致題目改寫后和出題者原意有出入。
　　筆者認為題面應以容易理解、沒有歧義為第一要點，至于英文是否地道，并不重要。英語已是世界通用的語言，沒有標準，每個國家都可以有自己的英語。在中國舉辦，參賽者又幾乎全是中國人的比賽，題目帶有一點中式英語的風格，理所應當。國內亞洲區預選賽上曾經發生過出題學校為使題目看起來地道而找外國人或英語專家修飾潤色，結果在賽場上反而被選手們詬病歧義太多的情況。
　　在北京大學負責命題的賽站，筆者均帶一名命題組的同學到比賽現場參與裁判工作。筆者發現選手們很少就題意提問，而且也從未因題目歧義發布過澄清(Clarification)。這說明我校的題面質量是不錯的。
　　5) 筆者匯集所有的題目，包括數據、標程和驗題程序，仔細核對每一道題的題面、程序和數據的一致性。核對無誤后就可以交付比賽主辦方了。
　　5命題注意事項
　　經歷過通過多次命題后，筆者總結了以下13條命題注意事項，供大家參考。
　　1) 最難的兩三道題應難度基本相同，不能有一道明顯最難。即便是一道可做的題目，只要它是明顯最難，結果很可能就是沒有人能通過，甚至根本沒有人做。
　　2) 再難想的題目，都可能有人做出來；只有代碼量大、難寫的題目，才可能沒有人通過。
　　3) 大多數情況下，題目的實際難度都比命題者判斷的難度要高。尤其是計算幾何題，即便實際上不難的，由于大家對計算幾何的恐懼心理，不愿意去做，通過率也會低于相同難度的其他類型題目。
　　4) 不要出需Special Judge(答案不唯一，要特殊評判)的題目，因為用來評判選手輸出數據是否正確的那個Special Judge程序，其自身正確性往往難以驗證。
　　
　　5) 題目時限應盡可能短，大部分題目應該時限都是3秒以內。這樣可以加快裁判速度。尤其是簡單題，不要設10秒這樣的長時限，否則由于提交次數多，裁判時間長，會導致許多選手因不能及時得到裁判結果而抱怨。
　　6) 題目的輸入輸出數據不要太大，10M以內為宜，大多數題目應2M以內。簡單題或有陷阱的易錯題，由于提交次數多，更不能有體積大的輸入輸出數據。因為在比賽的判題系統PC2中，標準輸入輸出數據都是在服務器上存放，裁判的機器每次判題，都需要從服務器將數據傳輸到本機，如果題目數據量過大，可能導致網絡擁塞，甚至系統崩潰。
　　7) 輸入數據應該有明確的結束方式(比如以兩個0結尾，或數據開頭就指明test case的數目)，不要讓程序讀到EOF了才能判斷數據已經結束。
　　8) 出題者有時會為了看數據方便，在數據里多個case之間加空行，最后要注意去掉。
　　9) 對于每道題，出題者都要專門寫一個驗證數據范圍的程序，輸出每個變量的取值范圍，看是否和題面描述吻合(不能超范圍，也不能遠小于題目所說范圍)。此外還要看會不會出現無意義的數據，如0的0次方、除數為0等。
　　10) 由于可能改了題面或數據而忘了改 數據樣例(Sample)，甚至文字編輯軟件有可能自動將Sample里的某些字母變成大寫，所以交付前一定要專門將Sample Input和Sample Output從題面里拷貝出來，分別存為兩個文件，然后以Sample Input文件作為輸入運行標程，生成輸出結果再比對Sample Output文件。比對不能用眼睛看，一定要用文件比較程序。
　　11) 要檢查題面中Sample Input和Sample Output里各個數據出現的次序是否和題目描述的一致，Sample Input數據有沒有超范圍。
　　12) 題面由別人改過后，一定要讓出題者再看一遍。
　　13) 在最終發布之前，要把上述9 至11條全部重新做一遍，尤其是第10條，很容易被忽略。
　　6命題中的教訓
　　筆者的命題經歷中，也有一些教訓：
　　1) 對于公式之類容易敲錯的內容，不能僅靠出題者自查，一定要有其他人檢查。
　　第一次命題是在2008年北京交通大學舉辦的亞洲區預選賽上。該套題目的I題是個積分題，題目中寫了幾個公式。雖然筆者一再和出題者強調注意公式不要寫錯，但還是有一個公式里錯了一個數字。由于筆者不懂那些公式，所以也沒發現。幸而該題是個難題，只有15支隊伍提交，其中4支通過；而且要過此題也不是一定要用該公式(或自己也可以推導并看出該公式有誤)，所以現場并無隊伍提出異議，該套題目還是受到了廣泛的好評。賽后上海交通大學一支為此題所困的隊伍發現了這個錯誤，并在北京大學在線判題系統(POJ)的BBS上指出來，我們也承認并且致歉。
　　2) 同一學校的隊員，知識結構相似，甚至可能會有共同的知識盲點。今后在競賽訓練中，和競賽命題中評估題目難度時，都應該充分注意這一點。
　　2010年在福州大學舉辦的亞洲區預選賽，是由北京大學命題的。比賽結果是上海交通大學有三支隊伍都通過了所有的題目，說明此套題目難度不足。造成這一結果的其中一個原因，是一道我們估計只有幾支隊能過的圖論“難題”，事實上成為有近三分之一隊伍通過的中等偏易題。賽前福州大學教練吳英杰老師曾對此題歸類為“難題”提出過異議，可惜筆者沒有足夠重視。因為當初命題組的同學，除了出題者，都不知道此題怎么做。事實上，我校有一支強隊在福州不排名參加了該場比賽，他們也沒有做出此題；而該隊里有兩名隊員，獲得過2010年哈爾濱賽站的冠軍和成都賽站的亞軍，實力非常強。
　　
　　Writing Problems for ACM/ICPC Asia Regional Contests
　　GUO Wei
　　(School of Electronic Engineering and Computer Scie