孫大烈　車萬翔

1ACM競(jìng)賽的背景

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

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

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

2ACM競(jìng)賽的價(jià)值

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

ACM ICPC的競(jìng)賽模式如下:

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

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

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

(4) 每個(gè)參賽隊(duì)伍由3人組成,比賽時(shí)每個(gè)隊(duì)使用一臺(tái)機(jī)器解答問題。

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

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

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

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

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

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

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

(5) 英文閱讀能力。

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

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

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

3我國(guó)參加ACM競(jìng)賽情況

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

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

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

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

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

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

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

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

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

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

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

我們的具體做法是:

(1) 將ACM ICPC題目作為實(shí)驗(yàn),加大實(shí)驗(yàn)成績(jī)比重

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

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

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

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

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

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

5結(jié)束語

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