0.3 什麼是競程

演算法競賽,圈內習慣叫「競程」

演算法競賽(也有人叫程式設計競賽)就是「寫程式比賽誰解題最快、最準確」的比賽,資訊奧林匹亞、全國資訊學科能力競賽都屬於這一類;APCS 雖然是檢定不是比賽,考的也是同一種題目。它的英文是 competitive programming,直譯是「競技程式設計」,圈內習慣簡稱競程,AA 競程的名字就是這麼來的。本書之後說「競程」,指的都是演算法競賽這件事。

比賽形式

通常會給你一個題目,你需要:

  1. 讀懂題目需求
  2. 想出解法(演算法)
  3. 用程式實現
  4. 在時間和記憶體限制內,用各式測試資料驗證正確性

為什麼要用電腦來算?

實際上,所有寫程式能解出來的問題,人類用手算也一定能解得出來,主要差別在於計算速度。

以加法為例,數學課的題目是「請計算 3+5 的值」;競程的題目長這樣:

這題的範例第一組就是 3+5。加法這麼簡單,為何需要用電腦?因為它一次要算的不是一題,而是最多 1000 組;把 1000 改成一億,人類一生都算不完,但電腦一秒內就能完成。

同樣的問題,方法有好壞之分

那麼,競程就只是把人類做的事寫成程式碼而已嗎?不是。就算解同樣的問題,也有好方法和壞方法之分。以下舉兩個例子:

例 1:質數判定

題目:「給你一個正整數 x,請判斷 x 是否為質數。」

樸素方法:根據質數的定義(大於 1 且只能被 1 和自己整除),把 2 到 x-1 的每一個數都拿去除除看 x;只要它們全都除不盡,x 就是質數。這樣總共要試 x-2 個數。

更好的方法:可以用數學證明,其實只要試 2 到 \sqrt{x} 的數就夠了。例如 x = 10007(它是質數)時,前者要一路試到 10006、約 1 萬次才能確定;後者試到 100 就夠,不到 100 次。

例 2:終極密碼

題目:「主持人心裡想一個 1 到 100 的整數,你每猜一次,他只回答『太大』『太小』或『答對』。運氣最差的情況下,要猜幾次才保證猜中?」

直覺方法:從 1 開始一個一個猜,最差要猜 100 次。

更好的方法:每次都猜剩下範圍的正中間。第一次猜 50,不管回答是太大還是太小,剩下的範圍都少一半;接著猜 25 或 75……每猜一次範圍就砍半,100 → 50 → 25 → 13 → 7 → 4 → 2 → 1,最多 7 次一定猜中。玩終極密碼時你大概早就這麼做了,這就是方法好壞的差別:同樣的規則,100 次變 7 次。這個方法叫「二分搜尋」,之後會正式學到。

演算法 vs 實作能力

如上面兩個例子,大部分競程題目是在考驗大家能否設計出比較好的解決問題方法。解決問題的方法就是「演算法」,這就是為什麼這些比賽也被稱為「演算法競賽」。

但設計出演算法後,我們還得把它用程式碼寫出來,才能在比賽中確實得分。把演算法用程式碼實現的能力就是「實作能力」。沒有實作能力,設計出再好的演算法也沒用。

實作能力跟「對程式語言的熟悉度」與「邏輯思維能力」有關。所以 AA 競程 Level 0 會先幫大家加強對程式語言的熟悉度與基本邏輯思維,之後學習演算法的路才會通順。

有哪些台灣學生能參加的競程比賽與相關檢定?

適合對象 比賽 / 檢定名稱 舉辦時間
升國一 ~ 升大學 YTP 少年圖靈計畫 每年暑假
不限年紀 APCS 大學程式設計先修檢測(升大學的程式檢定科目) 每年 1、3、6、7、10、11 月(各級別開放的月份不同,以官網公告為準)
高三以下 資訊奧林匹亞 TOI(選拔代表參加 IOI) 每年 3 ~ 4 月
高中生 全國資訊學科能力競賽 每年上學期(各校校內初賽可能提前到前一學年度的下學期)
高中職學生 成大暑期高中生程式設計邀請賽(南部少見的高中組隊賽,決賽得獎可取得成大資工特殊選才報名資格) 每年 5 月初賽、8 月決賽
高三以下 美國資訊奧林匹亞 USACO 每年 12 ~ 3 月
大專在學學生 大學程式能力檢定 CPE(上大學後可考的程式檢定,大專生免費報考,常作為資工系所的畢業門檻或推甄參考) 每年四次,每季一次
國際線上 Codeforces、AtCoder 每週都有比賽

競程有什麼有趣的地方?

  • 解題的快感:想出演算法的那一刻、實現它、看它 AC(Accepted,通過全部測試)的那一刻很有成就感
  • 無窮無盡的挑戰:演算法的世界博大精深,永遠有更難的題要挑戰
  • 全球社群:Codeforces、AtCoder 上有來自世界各地的競程者,可以和他們比試高下
  • 業界價值:多數軟體相關的行業,會用競程類型的題目來篩選面試者