AGM—ICPC訓練方法與競賽策略

王春平　王衛(wèi)紅　韓姍姍　李曲　方趙林

摘要：ACM-ICPC競賽規(guī)模日趨增大，為了提高訓練效率和競賽成績，文章依據ACM-ICPC的知識范疇，提出程序設計的訓練方法和相應的競賽策略，引導和增強學生的程序設計能力，提出在比賽中采取正確的組隊策略、團隊合作策略和答題策略。

關鍵詞：ACM-ICPC；程序設計；訓練方法；競賽策略

0 引言

ACM國際大學生程序設計競賽（ACM Inter-national Collegiate Programming Contest，ICPC）是由美國計算機協會（Association for ComputingMachinery，ACM）主辦的一項旨在展示大學生創(chuàng)新能力、分析和解決問題能力、在壓力下編寫程序能力和團隊精神的年度競賽，迄今為止已經舉辦了37屆。大陸高校從1996年開始舉辦比賽，目前中國賽區(qū)擁有5個站點，參賽隊伍穩(wěn)定在150支以上。隨著國內高校參賽規(guī)模的增大，獲取好成績的難度也越來越大。

1 知識范疇與訓練方法

程序設計是計算機科學領域的基礎技術，涉及幾乎所有的計算機基礎課程。要提高學生的程序設計與應用能力，教師必須有規(guī)范的訓練方法，并加以正確引導，才能達到學以致用的目的。計算機程序作為一種管理和數據分析手段，已經滲透到幾乎所有的行業(yè)，而ACM-ICPC的競賽題目有很大一部分是來自計算機實踐的抽象，要想很好地解決這些問題，學生必須掌握相關知識點，擁有熟練的編程調試技術以及頑強不屈的心理素質。

1.1 知識范疇和基礎編程

ICPC競賽涵蓋的知識面非常廣泛，主要由以下幾部分構成。

（1）數學基礎：算法復雜性分析方法、概率論、代數學、組合數學、博弈論、數論等。

（2）數據結構：基礎數據結構、集合、排序算法、堆、樹等。

（3）圖論：圖的分類與遍歷、二分圖、網絡流等。

（4）計算幾何：向量、點與多邊形、平面交等。

由于ICPC只是作為培養(yǎng)學生編程興趣的一種手段，學生在有限時間里要全面學習掌握這些知識點非常困難，因此，知識點的學習可根據組隊有針對性地進行，盡量使同一個參賽隊伍中的隊員之間相互補充。例如，隊員1側重學習計算幾何，隊員2和隊員3則可分別偏重學習數學知識和數據結構，這使得組隊可能在短時間內獲得更好的比賽成績。從長遠來看，要想成為一名優(yōu)秀的參賽隊員，學生須具備“一專多能”的能力，“一?！笔蔷ㄖ辽僖环N類型的不同難度題目，“多能”是指能解決其他類型的一般題目，這樣的隊員所組成的參賽隊伍往往會有1+1+1>3的比賽效果。

在編程技術方面，ICPC競賽主要采用2種程序設計語言：C/C++和Java語言。C/C++語言作為傳統(tǒng)的編程語言，在競賽中擁有很多優(yōu)勢，而Java語言也有自己的特點。Python和C#等語言近期也逐漸被各競賽系統(tǒng)所支持。不論采用哪一種語言，可分為以下3個方面來訓練：①基礎語法訓練：任何微小的語法和編譯錯誤在賽場上都是一種損失；②STL技術：至少熟練掌握一種語言如C++的STL（Standard Template Library）模板；③基本題型訓練。這些基礎的編程訓練都將在賽場上減少不必要的罰時，可以為各組爭取更好的結果。

1.2 求解方法分類

ICPC競賽同其他算法競賽一樣，訓練時需要對求解方法有針對性的訓練。求解方法的主要分類包括：窮舉法、分治方法、動態(tài)規(guī)劃法、貪心法、回溯法、分支限界法和線性規(guī)劃法。

窮舉法又稱為暴力法（Brute Force），是使用比較普通也是最樸素的解題方法，但是時間復雜度非常高，實際解題時往往需要同其他方法進行結合。

分治法是指將難以直接解決的大規(guī)模問題分割成一些規(guī)模較小的相同問題，以各個擊破、分而治之，比較典型的問題有全排列問題、漢諾塔問題等。

動態(tài)規(guī)劃法指解題過程中的每次決策依賴于當前狀態(tài)，又隨即引起狀態(tài)的轉移。一個決策序列就是在變化的狀態(tài)中產生出來的，這種多階段最優(yōu)化決策解決問題的過程就稱為動態(tài)規(guī)劃。動態(tài)規(guī)劃法一般采用自底向上的求解步驟，學生較難掌握。使用動態(tài)規(guī)劃法求解的典型問題有0-1背包問題、矩陣連乘問題、流水作業(yè)調度和最優(yōu)二叉搜索樹等。

貪心法指在對問題求解時，總是做出在當前看來是最好的選擇。貪心法的求解步驟與動態(tài)規(guī)劃法相反，通常以自頂向下的方式進行，以迭代的方式做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。比較典型的問題有：散裝背包問題、最優(yōu)裝載問題、哈夫曼編碼問題、最小生成樹和多機調度問題等。

回溯法則是在解空間樹上采用試錯思想，嘗試分步解決一個問題。這種方法實際上是暴力法的一種變形，最壞情況是會導致指數時間的計算復雜度。比較典型的問題有：圖的m著色問題、旅行售貨員問題和最大團問題等。

分支限界法類似于回溯法，也是一種在問題的解空間樹上搜索問題解的算法，但回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在某種意義下的最優(yōu)解。典型的問題包括：布線問題、電路板排版問題和批處理作業(yè)調度問題等。

線性規(guī)劃法則是最優(yōu)化問題中的重要領域之一，指在線性等式或不等式的約束條件下，求解線性目標函數的最大值或最小值的方法。其中目標函數是決策者要求達到目標的數學表達式，用一個極大或極小值表示。約束條件是指實現目標的能力資源和內部條件的限制因素，用一組等式或不等式來表示。比較典型的問題有：最大網絡流、最小費用流和網絡單純形問題等。

作為競賽選手，掌握這些方法并能夠在實際解題中進行應用是非常必要的，因此通常的競賽題目解題方法都在此范圍內。另外，筆者沒有將搜索排序作為解題方法的基本要求，但實際編程中很少有需要自己寫搜索排序算法的，因為一般在編程語言中已經有相應的庫函數提供。在初期訓練時，動態(tài)規(guī)劃和線性規(guī)劃應作為訓練重點，也是因為此類方法的應用較難，雖然能夠掌握方法的原理，但是需要選手具備具體問題具體分析的能力，而其他方法則相對要簡單一些。在訓練后期，特別是臨近比賽時，要盡量避免做陳題，應該多嘗試訓練新題以增強臨場應變能力。endprint

1.3 心理訓練

ACM-ICPC競賽的時間長達5小時，題目數量一般在10～12道之間，可以說，這對隊員的體力和腦力都是巨大的考驗。實際比賽氣氛非常緊張，如在答題的過程中卡題，隊員較易出現心理波動，導致發(fā)揮失常，因此，注重平時的心理承受能力訓練是非常有必要的。當然，心理承受能力的培養(yǎng)并非一朝一夕可以完成，而是一項長期細致的工作。為了增強激烈競爭下的抗壓能力，教師可以在平時訓練中有意識地設置一些需隊員努力才可以完成的難題，并授予獎品或者懲罰，讓隊員“跳一跳來摘果子”，把學到的對付困難、挫折的方法應用到實際競賽中去，培養(yǎng)其心理承受能力。

在心理訓練層面，一個良好的訓練氛圍也是不可缺少的。團隊中除了培養(yǎng)隊員平日訓練的默契，也需要隊員之間的相互鼓勵。但是，在比賽中還有一種情形，就是多次提交后仍不能被判定正確，此時該題如同雞肋，耗在此題上很容易造成戰(zhàn)機的延誤.這時需要一個具備心理素質強、有大局掌控力的隊長命令大家果斷放棄該題。

2 ACM-ICPC競賽策略

ACM-ICPC是團隊競賽，因此在組隊、團隊合作和答題順序上都要有一定的策略。每個ICPC參賽隊由3名隊員組成，這種奇數規(guī)定不是偶然的，而是ACM-ICPC主辦方長期經驗積累的結果。在1993年以前，參賽隊是由4名隊員組成，經過各主辦方的長期觀察，發(fā)現這樣很容易導致隊伍分成2個小組，其中一個小組（2名隊員）使用電腦輸入程序，另外一個小組則在紙上討論下一題的求解，這樣的情形是與競賽設計者的初衷背道而馳的，因此ACM-ICPC委員會將成員縮減為3個，這樣團隊既可作為一個整體，也可以單獨行動或者輪換組合。

組隊策略一般有3種：強強搭配型、互補型和梯隊型。強強搭配型是各高校為了取得最好成績的常見組合，一般3名隊員都是在該校排名靠前的隊員，一般高校常用這種集中最優(yōu)力量的組合來沖擊全球總決賽?；パa型通常又分為兩種：技術互補型和能力互補型。技術互補型的隊伍分訓由英文閱讀能力強、編碼能力強和邏輯能力強的3名隊員構成，這樣可以在技術上相互補充。能力互補型則由知識面不同的隊員構成，例如，隊員1擅長數據結構，隊員2擅長計算幾何，隊員3擅長圖論等。梯隊型則是為了完成傳幫帶的梯隊建設需要，讓老隊員幫助新隊員快速成長。

雖然目前在程序設計訓練和競賽中女隊員所占比例非常少，但一個訓練團隊或隊伍中如果有女隊員的存在，往往會最大限度地激發(fā)男隊員的學習激情和潛力，最近幾年大陸世界總決賽參賽隊都有這樣的例證。

在團隊合作策略上，一般分為3種：完全配合型、獨立型和配對型。完全配合型指在全場比賽時間中，整個隊伍在同一時刻只處理一道題，三名隊員一起讀題，編碼直至題目被判定正確。獨立型則通常出現在強強搭配的隊伍中，三名隊員能力都很強，一般在開場時就分配好各自任務，然后分頭解題，這種策略是奔著最好成績去的，但存在著集體卡題的危險。配對型則是兩名隊員討論一個題目的確定解法后，剩余一名隊員負責編碼實現，而配對兩名隊員接著討論下一個題目，如此循環(huán)配合；當然實際操作時，也可進行配對切換。

在答題策略上，一般有順序答題、從易到難、中檔一容易一難等3種答題策略。順序答題是按照題目的順序答題，但現在題目的難易程度都是打亂的。從易到難則是比較容易接受的答題順序，但是實際競賽中題目閱讀實際上比較費時間，有時候也很難確定每道題的難易對比從中檔到容易再到難的答題順序則是一種折衷策略，如果發(fā)現有比較容易的題目，則可以留著最后來解決。當然，實際競賽出現的情況是多種多樣的，這也需要隊員隨機應變。

3 結語

ACM-ICPC的訓練方法和競賽策略可作為程序設計類課程學生培養(yǎng)的參考。當然，培養(yǎng)出色的程序設計人才是一項長期且艱苦的任務，作為教練，不僅需要制定完備的訓練計劃和競賽策略，還承擔著“學生導師”的角色，只有深入了解隊員的學習生活狀況，去幫助他們解決所面臨的各種困難，才能培養(yǎng)他們對程序設計的“感情”，使得他們體會到編程的樂趣并“愛上”編程，從而最終成為優(yōu)秀的編程人才，正所謂“知之者不如好之者，好之者不如樂之者”。

參考文獻：

[1]姚翠莉，劉一瑋，金博.ACM/ICPC競賽人才培養(yǎng)模式的研究與實踐[J].內蒙古師范大學學報：教育科學版，2012，25（3）：141-144.

[2]俞勇.ACM國際大學生程序設計競賽知識與入門[M].北京：清華大學出版社，2012：7.

[3]王曉東.計算機算法分析與設計[M].北京：電子工業(yè)出版社，2011：5.

[4]夏鴻斌.競賽教育與信息技術創(chuàng)新人才培養(yǎng)模式探討[J].軟件導刊，2009，8（10）：182-183.

[5]Andrew T， Chris H.Programming contest strategy[J].Computers&Education，2008（50）：825-830.

（編輯：孫怡銘）endprint