孫大烈　車萬翔

1ACM競賽的背景

ACM國際大學(xué)生程序設(shè)計競賽(ACM International Collegiate Programming Contest,ACM ICPC)始于1970年,作為一種全新的發(fā)現(xiàn)和培養(yǎng)計算機(jī)科學(xué)頂尖人才的途徑,競賽很快得到美國和加拿大各大學(xué)的積極響應(yīng)。1977年,在ACM計算機(jī)科學(xué)會議期間,舉辦了首屆總決賽,由此拉開了一年一度的國際大學(xué)生程序設(shè)計競賽的帷幕。

30多年來,ACM ICPC由最初的美國、加拿大,拓展到了北美洲、拉丁美洲、歐洲、亞洲、大洋洲和非洲,成為世界性的賽事。2008年,參加各大洲預(yù)賽的隊伍有來自88個國家(地區(qū))1,838所大學(xué)的7,109支代表隊,從中產(chǎn)生的100支隊伍參加了2009年4月在瑞典斯德哥爾摩舉行的世界總決賽。

中國大陸從1996年開始設(shè)立ACM ICPC亞洲區(qū)預(yù)賽賽區(qū)并參與此項賽事,越來越多的高校參與其中,尤其是2005年以后,參賽勢頭更是如火如荼。2008年,亞洲區(qū)預(yù)賽共設(shè)立15個賽區(qū),中國大陸占5席,有近5000支隊伍參加了各賽區(qū)的網(wǎng)絡(luò)預(yù)賽,近480支隊伍參加了現(xiàn)場賽,最終有15支隊伍進(jìn)入總決賽。

2ACM競賽的價值

ACM ICPC的價值和意義主要體現(xiàn)在兩個方面,一是競賽模式新穎,有利于培養(yǎng)學(xué)生的編程實踐能力,二是對參賽選手的綜合素質(zhì)要求高,有利于培養(yǎng)學(xué)生的創(chuàng)新實踐意識。

ACM ICPC的競賽模式如下:

(1) 題目類型比較雜,涉及知識面比較廣,只要能夠編程的問題都可以納入競賽題目范圍。每個題目都需要經(jīng)過研讀、分析、確定算法,然后編程的過程。

(2) 采用在線測評系統(tǒng)進(jìn)行評判,對提交程序的要求不僅包括正確性,還包括對運行時間、占用內(nèi)存和輸入輸出格式的限制。

(3) 所有的題目均采用英文命題。

(4) 每個參賽隊伍由3人組成,比賽時每個隊使用一臺機(jī)器解答問題。

(5) 比賽題目都是由專門機(jī)構(gòu)負(fù)責(zé)制作的,每次賽事都由不同的人出題,題目的風(fēng)格、類型、難易度都有很高的不確定性。

(6) 比賽時間5小時,一共10個題目,100支隊伍同場競技,看誰做出來的題數(shù)多、用時少。

ACM ICPC對參賽選手的素質(zhì)要求有:

(1) 算法實現(xiàn)能力。即編寫代碼、調(diào)試程序的能力。根據(jù)ACM ICPC的規(guī)則,在5個小時內(nèi)解題數(shù)最多、用時最少的為冠軍,所以算法實現(xiàn)能力是基礎(chǔ)。

(2) 通曉各種算法。熟悉各種算法,對常用的算法達(dá)到信手拈來的程度。

(3) 算法選擇能力。面對實際問題,在最短時間內(nèi)確定最優(yōu)算法。

(4) 數(shù)學(xué)知識。包括圖論、組合數(shù)學(xué)、數(shù)論、幾何等,就目前的情況而言,數(shù)學(xué)知識對選手取得好成績是很重要的。

(5) 英文閱讀能力。

(6) 團(tuán)隊合作能力。每支參賽隊由3人構(gòu)成,共用1臺機(jī)器。什么樣的人組成一個隊伍、如何分工、如何協(xié)作、如何決策等,都有很多學(xué)問。

(7) 創(chuàng)新能力。其他的都是基礎(chǔ),唯有創(chuàng)新能力才是根本,這是所有競賽的特點。ACM ICPC的題目涉及各個領(lǐng)域,類型包羅萬象。不是所有的問題都有現(xiàn)成的算法,更多的時候需要在現(xiàn)有算法的基礎(chǔ)上進(jìn)行創(chuàng)新,有時候甚至需要觀念創(chuàng)新、思維創(chuàng)新。

正是ACM ICPC對提高學(xué)生綜合能力尤其是創(chuàng)新能力的價值,深深地吸引了國內(nèi)外高校和莘莘學(xué)子,他們以不同方式、不同程度地介入這項賽事,這也進(jìn)一步提高了這項賽事的價值。

3我國參加ACM競賽情況

3.1參賽學(xué)校的類型

我國高校開展ACM ICPC活動的情況各不相同,時間有先有后,程度有深有淺,廣度有寬有窄,力度有大有小,成績有高有低。但無論怎樣,各高校的積極性越來越高,規(guī)模越來越大。以黑龍江省為例,2005年以前只有哈工大參與這項賽事,而從2006年開始,已經(jīng)連續(xù)舉行了三屆省賽,省內(nèi)幾乎所有高校都參加了網(wǎng)絡(luò)賽和現(xiàn)場賽。

在開展ACM ICPC的過程中,各校采取的模式不盡相同,這主要取決于學(xué)校的特點。有些學(xué)校有眾多優(yōu)秀的OI(信息學(xué)奧林匹克)選手,這些學(xué)生在高中階段就參加信息競賽,有良好的基礎(chǔ),自然就成為該校的ACM ICPC選手,他們要做的就是在大學(xué)繼續(xù)高中階段的競爭。這類學(xué)校的學(xué)生基礎(chǔ)好,有助于在全校范圍開展ACM ICPC活動,同時也是各種賽事中取得好成績的保障。

另一些學(xué)校也有優(yōu)秀的OI選手,雖然人數(shù)不多,但是猶如種子,可以生根、發(fā)芽、結(jié)果。他們可以影響和帶動其他同學(xué),使之成為和他們一樣優(yōu)秀的ACM競賽選手。這類學(xué)校一般對ACM ICPC都比較重視,全校性的活動開展得很好,各種賽事的成績也很突出。

更多的學(xué)校屬于白手起家,沒有優(yōu)秀的OI選手,一切從零做起。這類學(xué)校開展ACM ICPC的基礎(chǔ)比較薄弱,開展這項賽事的目標(biāo)更多的不是取得成績,而是拓展學(xué)生綜合能力的空間。比較而言,雖然這類學(xué)校的成績不是最好,但是進(jìn)步是最大的。他們中許多人在上大學(xué)前從來沒編過程序,通過ACM ICPC,他們可以參加賽區(qū)比賽,獲得銅牌、銀牌甚至金牌,對他們來說變化是巨大的。

3.2選拔和培養(yǎng)參賽隊員的途徑

對于很多學(xué)校來說,如何挖掘有潛力的ACM參賽隊員,是要解決的第一個問題。眾所周知,數(shù)據(jù)結(jié)構(gòu)和算法是ACM ICPC的核心,但如何發(fā)掘從沒有接觸過這方面知識的人的潛力呢?本質(zhì)上看,數(shù)據(jù)結(jié)構(gòu)和算法都是數(shù)學(xué)范疇的知識,所以數(shù)學(xué)成績好要比數(shù)學(xué)成績不好的學(xué)生潛力大,但并不否認(rèn)某些特例?，F(xiàn)今ACM ICPC中有一類題目是直接的數(shù)學(xué)題,與其說是考察學(xué)生的程序設(shè)計和算法,不如說是考察數(shù)學(xué)水平。這類數(shù)學(xué)問題大多涉及組合數(shù)學(xué)、數(shù)論等知識,沒有接觸過這些知識的人很難完成這樣的題目。另外,良好的抽象思維及嚴(yán)密的邏輯思維也能反映出這個人在數(shù)據(jù)結(jié)構(gòu)和算法上的潛力。因此,學(xué)校可以通過測試學(xué)生數(shù)學(xué)水平和邏輯抽象能力選拔隊員,也可以根據(jù)每個人的性格特點或思維習(xí)慣輔助選拔。

隊員經(jīng)過選拔后面臨的問題是怎樣進(jìn)行訓(xùn)練。因為教師的參賽經(jīng)驗并不豐富,所以可行的辦法是高年級帶低年級,形成一個團(tuán)隊,隊員之間鼓勵相互學(xué)習(xí),相互分享知識和經(jīng)驗。不僅讓學(xué)生學(xué)到知識,更要讓他們知道要學(xué)什么,怎樣學(xué)以及自己怎樣提高,學(xué)會解決問題,獨立探索,吃苦耐勞,這對學(xué)生的發(fā)展和綜合能力的提高是大有裨益的。我們以上總說數(shù)據(jù)結(jié)構(gòu)和算法,而不直接說ACM ICPC,因為ACM ICPC從根本上還是一個競賽,而競賽不免會包含很多不確定因素,隊員的成績未必就代表隊員的水平,所以平時的心理素質(zhì)訓(xùn)練也是不可或缺的。

如何培養(yǎng)參賽選手是第二個要解決的問題。大多數(shù)參賽選手大學(xué)前沒有接觸過這些知識,所以他們首先要適應(yīng)ACM ICPC編程比賽。ACM ICPC比賽追求的是速度、準(zhǔn)確、創(chuàng)新,這就要求選手的思維和編程速度都很快。平時的訓(xùn)練大家不僅要攻克難題,提高能力,還要適當(dāng)模擬正式比賽,讓選手能夠適應(yīng)正式比賽的緊張氣氛。比賽策略的訓(xùn)練也很重要,如三個人的配合問題、題目完成的順序問題等。選手的知識儲備不僅要廣博,而且要有自己的“殺手锏”,即每個人都要有自己的專長,達(dá)到一看這些知識的題目就能立即完成的水平。當(dāng)然,隨著大賽的普及,題目的類型不再可以明確區(qū)分,這就更要求選手有足夠多的知識儲備、足夠強的個人能力及一定的分析融合能力。在題目的選擇上也應(yīng)有取舍,選擇有研究價值的題目訓(xùn)練。

在ACM ICPC中,學(xué)生是永恒的主角,他們承擔(dān)培訓(xùn)、集訓(xùn)、宣傳、選秀等工作,教師永遠(yuǎn)是做引導(dǎo)、服務(wù)工作的配角。很多學(xué)校已經(jīng)形成了以老帶新的傳統(tǒng),一年一年下來,形成一種機(jī)制,這正是ACM ICPC培養(yǎng)學(xué)生綜合能力的核心,而在這種機(jī)制中,老隊員和新隊員都得到了很好的自我鍛煉和提高的機(jī)會。

4我校將ACM競賽融入教學(xué)

和體育運動類似,要想在ACM ICPC中獲得好成績,必須有廣泛的群眾基礎(chǔ),盡可能讓更多的學(xué)生受益,提高學(xué)生的整體編程水平。從2004年起,哈工大便將ACM ICPC引入計算機(jī)學(xué)院本科一年級的程序設(shè)計課程中,激發(fā)學(xué)生對ACM ICPC的興趣,吸引更多學(xué)生投身到此項活動中。

我們的具體做法是:

(1) 將ACM ICPC題目作為實驗,加大實驗成績比重

在百分制評定中,將實驗(共10次)成績的比重加大到50分,督促學(xué)生重視每次實驗。實驗題目以ACM ICPC題目為主,有一定的實際背景,但都沒有標(biāo)準(zhǔn)答案,學(xué)生要根據(jù)所學(xué)知識做出解答,每個題目的解決方法有很多。

多數(shù)題目的解決過程是這樣的:首先使用最常規(guī)、最自然的思維方式解決實際問題,然后考慮時間效率較低或空間占用較大的情況,如果新方法不是最好的,還有沒有更好的方法呢?這往往需要花費更多的時間和精力,也是學(xué)生收益最多的地方。對于教學(xué)管理來講,這種具有明確輸入、輸出形式的實驗可以由機(jī)器自動評判成績,減輕了教師的工作量,使這項工作得以順利開展。

為了保證學(xué)生實驗的質(zhì)量,避免雷同情況的發(fā)生,我們引入了Moss(Measure of Software Similarity)雷同判別程序,促使學(xué)生通過自己的思考和努力獨立完成實驗。另外,如何從解題思路、程序風(fēng)格等方面細(xì)致評判學(xué)生的實驗完成情況,給出個性化的實驗評語,也是亟待解決的一個問題。為此,需要大量的學(xué)生TA(Teaching Assistant)輔導(dǎo)實驗,即每半個班級安排一名學(xué)生TA,對其負(fù)責(zé)的學(xué)生進(jìn)行實驗課上實時答疑,課下登錄課程論壇隨時答疑。同時,學(xué)生TA還對所負(fù)責(zé)同學(xué)的實驗進(jìn)行評判,做到仔細(xì)閱讀每行代碼,公正評判,給出詳細(xì)的扣分原因及程序改進(jìn)建議。學(xué)生TA由編程經(jīng)驗豐富的博士生、碩士生甚至本科生擔(dān)任。

學(xué)生實驗情況調(diào)查顯示,39.4%的學(xué)生認(rèn)為“作業(yè)偏難,需要花費大量精力完成,但是從中收獲很多”,有35.2%的學(xué)生認(rèn)為“作業(yè)難度適中,較好地鍛煉了編程能力”?？梢?大部分學(xué)生對這種實驗方式表示認(rèn)可,并通過實驗鍛煉了實際動手能力。

(2) 培養(yǎng)拔尖人才,給學(xué)有余力的學(xué)生“吃小灶”

僅通過完成實驗培養(yǎng)出優(yōu)秀的ACM ICPC選手困難較大,因此我們用多種精神和物質(zhì)獎勵刺激拔尖人才的快速進(jìn)步。完成大量的題目是取得優(yōu)異成績的基礎(chǔ),所謂熟能生巧,量變引起質(zhì)變。我們引入競爭機(jī)制,將學(xué)生在HOJ(HIT Online Judge)上的做題數(shù)進(jìn)行實時排序,如圖1所示,學(xué)生做題數(shù)目穩(wěn)步增長,最終形成一種你追我趕的良好態(tài)勢。為了保證充足的上機(jī)時間,刺激學(xué)生力爭上游,我們給排名靠前(60名)的學(xué)生提供免費上機(jī)機(jī)會,還向綜合表現(xiàn)優(yōu)異的同學(xué)發(fā)放編程和算法方面的書籍。

5結(jié)束語

參與ACM競賽不僅使學(xué)生提高了計算機(jī)編程水平,提升了綜合素質(zhì),還促進(jìn)了相關(guān)課程的教學(xué)改革,提高了教學(xué)效果。目前,我校開展這項賽事活動還處于起步階段,局限于少數(shù)院系的參與,今后將在全校范圍內(nèi)推廣這項活動,讓更多的學(xué)生參與其中,得到鍛煉提高。