0.3 什麼是競程
¶演算法競賽,圈內習慣叫「競程」
演算法競賽(也有人叫程式設計競賽)就是「寫程式比賽誰解題最快、最準確」的比賽,資訊奧林匹亞、全國資訊學科能力競賽都屬於這一類;APCS 雖然是檢定不是比賽,考的也是同一種題目。它的英文是 competitive programming,直譯是「競技程式設計」,圈內習慣簡稱競程,AA 競程的名字就是這麼來的。本書之後說「競程」,指的都是演算法競賽這件事。
¶比賽形式
通常會給你一個題目,你需要:
- 讀懂題目需求
- 想出解法(演算法)
- 用程式實現
- 在時間和記憶體限制內,用各式測試資料驗證正確性
¶為什麼要用電腦來算?
實際上,所有寫程式能解出來的問題,人類用手算也一定能解得出來,主要差別在於計算速度。
以加法為例,數學課的題目是「請計算 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 上有來自世界各地的競程者,可以和他們比試高下
- 業界價值:多數軟體相關的行業,會用競程類型的題目來篩選面試者