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

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

關(guān)鍵詞：ACM-ICPC；程序設(shè)計(jì)；訓(xùn)練方法；競賽策略

0 引言

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

1 知識范疇與訓(xùn)練方法

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

1.1 知識范疇和基礎(chǔ)編程

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

（1）數(shù)學(xué)基礎(chǔ)：算法復(fù)雜性分析方法、概率論、代數(shù)學(xué)、組合數(shù)學(xué)、博弈論、數(shù)論等。

（2）數(shù)據(jù)結(jié)構(gòu)：基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)、集合、排序算法、堆、樹等。

（3）圖論：圖的分類與遍歷、二分圖、網(wǎng)絡(luò)流等。

（4）計(jì)算幾何：向量、點(diǎn)與多邊形、平面交等。

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

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

1.2 求解方法分類

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

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

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

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

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

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

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

線性規(guī)劃法則是最優(yōu)化問題中的重要領(lǐng)域之一，指在線性等式或不等式的約束條件下，求解線性目標(biāo)函數(shù)的最大值或最小值的方法。其中目標(biāo)函數(shù)是決策者要求達(dá)到目標(biāo)的數(shù)學(xué)表達(dá)式，用一個極大或極小值表示。約束條件是指實(shí)現(xiàn)目標(biāo)的能力資源和內(nèi)部條件的限制因素，用一組等式或不等式來表示。比較典型的問題有：最大網(wǎng)絡(luò)流、最小費(fèi)用流和網(wǎng)絡(luò)單純形問題等。

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

1.3 心理訓(xùn)練

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

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

2 ACM-ICPC競賽策略

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

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

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

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

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

3 結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

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

（編輯：孫怡銘）endprint