跳到主要內容區塊

ntuccepaper2019

專題報導

走過NPSC 20週年回顧—系統篇
  • 卷期:v0047
  • 出版日期:2018-12-20

作者: 陳啟煌 / 臺灣大學計算機及資訊網路中心程式設計組副組長


適逢NPSC 20週年加上國際大學程式競賽亞洲區,趁此時機回顧一下過去的歷史,記錄下這20年來比賽系統與語言的演進,並期待下個20週年到臨。

 

今年2018 National Problem Solving Contest on Internet (NPSC)網際網路程式設計全國大賽是第20屆的比賽,加上本校今年也承辦第43屆(ICPC)國際大學程式設計競賽亞洲區台北站區域賽事,正所謂雙囍臨門。趁此時機回顧一下這20年來比賽系統與程式語言的演進,也見證走過這一段程式競賽的歷史。

 

NPSC基本上是承襲ICPC的賽制,在介紹NPSC之前先概述ICPC的發展背景。國際大學程式設計競賽(ICPC)最早第1屆可以追朔到1977年在ACM電腦科學會議期間舉辦了首次總決賽,之後演變成每年一屆由各國參與的國際賽事;1989年建立區域賽制度,區域賽的優勝隊伍才能參加世界總決賽。1995年台灣首度舉辦亞洲區域賽,由國立政治大學舉辦。目前共有南、北美、歐、亞、非、南太平洋等6個區域賽區。此競賽主要參賽者為大專學生,競賽項目為程式解題能力(Programming Problem Solving)。雖設有亞洲賽區,但早期台灣能參與到ICPC世界決賽的機會並不多;鑑於選手應該從小培養,1998年由臺大計資中心林一鵬主任及賴飛羆教授籌辦第1屆網際網路程式設計全國大賽(NPSC)。參賽者為全國高中生,希望讓選手能提早適應ICPC的比賽方式,進而爭取好的成績。NPSC規則參考ICPC,賽制採初賽決賽兩階段;初賽透過網際網路比賽,選手可在全國各地參賽,初賽為門檻賽,取前25名至臺大計資中心參加決賽。在2000年時增加舉辦國中組的比賽,每年舉行國中、高中組競賽,截至今年剛好屆滿20年。

 

一般比賽大都先交解答比賽後再由評審評分,但NPSC參考ICPC賽制,比賽的成績計算是即時計算。所以這個比賽需要一個可靠的比賽系統來掌控比賽時所有答案和裁判審核結果,隨時揭露各隊伍的比賽成績。比賽系統的重要性不亞於題目和測試資料。NPSC的比賽系統一共有3代,第一代系統是個類似架設在Unix上的主機系統,使用者用終端機軟體telnet進系統比賽,系統畫面如圖一所示,比賽的介面可以即時顯示submit的答案被judge的結果,也可以看到比賽的即時公告訊息等。此程式的作者為林永傑(曾經獲得1997年ACM ICPC 世界大賽第4名,現為綠創科技執行長)。這個比賽系統很穩定從1998年使用到2009年共使用了12年。早期比賽使用的程式語言限定為C/C++, Visual Basic , Delphi Pascal等,雖然ACM ICPC主要使用C/C++,但是當時國內的國、高中生大概都是以VB為啟蒙語言,使用VB比賽的比例偏高,怕影響學生參賽意願,花了幾年的時間讓學生改用C/C++,在2010年正式淘汰了VB,程式語言限定使用C/C++。也在2010年時更換成第二代比賽系統PC^2 (Programming Contest Control system),PC^2是由California State University, Sacramento開發,以java語言撰寫的系統,為client-Server架構,使用者介面如圖二所示,PC^2為ICPC常用的比賽系統,

 

更換此系統有助於學生及早適應國際賽的介面。PC^2從2010使用到2014年。

 


圖一 第一代系統

 


圖二 第二代比賽系統 PC^2

 

因PC^2為client-Server架構,參賽者的電腦需要安裝client。初賽時諮詢電話比以往多,存在使用者安裝與設定的問題。在2015年時由當屆裁判長引進web-based的比賽介面Kattis,整合了題目、測試比賽系統和成績看板,主辦單位只要維護設定好比賽,參賽者的電腦只需要瀏覽器和帳號密碼即可使用比賽系統。

 


圖三 第三代比賽系統 Kattis

 

到今年為止已經用了4屆,透過實際比賽使用,已驗證此系統的可靠度,且其使用者介面設計參賽者較無學習上的障礙。希望這個比賽系統可以再陪NPSC走過幾年的歲月。這幾年ICPC所使用的程式語言除了原有的C/C++外,加上了Java和Python,我們會持續觀察程式語言的演變再研議是否增減。

 

回顧20年來NPSC使用的比賽系統演化的軌跡,正如資訊系統的演化潮流一般,主機系統演變成client-server架構再變成web-based系統。這些比賽系統忠實的記錄著每場比賽每個隊伍的表現,一同見證了NPSC這20年的比賽歷史;我們也將持續的辦好以後的每場比賽,讓NPSC有下個10年、20年的記錄。