Chapter III. 漸入佳境
資訊競賽介紹
比賽 + 練習策略
作者nathanlee726

程式競賽考驗選手們在一定時間內對一些演算法相關的題目作答,這除了考驗選手們本身的演算法知識及設計程式的能力、這類的硬實力以外。同時也會需要選手們好好分配時間、決定策略,以能夠在時間限制內最大化在各個題目中拿到的分數。因此,為了準備程式競賽,我們會在各個方面培養自己的能力。

刷題


學習演算法與資料結構固然重要,不過這就如同在培養自己的基本功,若是遇到題目時不知道如何使用這些演算法,那麼空有一身功夫也沒辦法使用,因此除了平時花時間學習演算法知識外,也要花時間寫題目練習,才能知道如何運用這些知識。

練習思考

刷題的主要一個目的,是在練習去思考將問題轉換成一個更好理解的形式,接著再使用自己學過的演算法及資料結構將其解決。程式競賽的題目通常沒辦法透過一眼就看出來它需要用什麼演算法去解決。因此,「將問題轉換成一個更好理解的形式」這個步驟,是解決一個問題時最重要的關鍵。透過大量的刷題,我們便能夠有效的訓練自己思考題目的能力。不僅如此,程式競賽的題目其實很常會用到相似的技巧,尤其是相同領域的題目很容易會有類似的解題思路。舉例而言,動態規劃這類型的題目,在遇到需要優化轉移複雜度的狀況時,大分都會用到單調隊列、斜率優化常見的優化技巧。因此,刷題能夠幫助我們盡早熟悉一些常見的技巧及思路,協助我們在正式比賽中更輕鬆的把題目解出來。

練習實作

除此之外,刷題的目的也在於訓練自己的實作能力。程式競賽與其他學科競賽差別最大的點在於,在想出題目的作法以後,需要透過撰寫程式碼將它實作出來,而不是把作法寫下來就行,因此,培養實作的能力是很重要的。透過刷題訓練,我們能夠培養自己的實作經驗,在遇到特定的功能如某種演算法或資料結構時,便可以熟練地將它實作出來。多多刷題練習實作,也能讓我們提早遇到一些需要 debug 的情境,修正自己在實作上會出現的問題,以免這樣的情況在正式比賽中發生。

模擬比賽 (Virtual)


Virtual 通常是指找一場實際辦過的比賽,在還完全沒有看過題目下的情況下開始計時,在有時間限制的情況下拿到盡量多的分數。通常在 virtual 時我們不會像刷題那樣看一題寫一題,而是挑選最適合的題目去寫,如果卡住的話就跳下一題寫,簡單來講,就是在模擬一場實際的比賽。那前面提到盡量多的分數是指什麼意思呢,這就與我們接下來要講的主題「子題」有關了。

子題

子題對程式競賽的新手而言其實是很友善的東西,不過多數人在剛開始打程式競賽時對子題都非常的不熟悉。這是因為平常在刷題時,我們都會以想出正解為目標。不過在比賽中,因為會有子題,使我們不一定要以想出正解為目標。一個題目的子題通常會是將題目的測資範圍加上一些限制,使得題目變成一個比較簡單的版本。舉例來說,一個題目可能本來的某個變數限制是 $1 \leq N \leq 10^5$,出題者便能設計一個子題,加上限制 $1 \leq N \leq 1000$,使這個子題的難度比原本的題目簡單,我們用 $O(N ^ 2)$ 的演算法便能拿到這個子題的分數。子題在一場 OI 制的程式競賽非常重要,參賽者即使來不及想出題目的作法並實作,也能夠透過子題來拿到一部分分數。對於新手來說,即使是在一場比較困難的比賽,也能透過解出子題來培養經驗。

有些時候,子題也會成為題目的提示。舉例來說,一個題目的內容可能會與 $N$ 個正整數有關,而出題者可以設計一個子題,加上「這 $N$ 個正整數會是 $1$ 到 $N$ 之間的每個整數各出現一次」這條限制,來提示做題者可以先往這種情況思考。因此,利用子題來協助自己做題也是非常重要的一件事。透過 Virtual 比賽的練習,我們便能夠模擬在正式比賽中遇到子題的情況,練習去寫子題、或是利用子題。

時間分配

時間分配則是在比較熟悉程式競賽後會需要注意的事情,通常在自己進步到一定程度後,便會在正式比賽遇到一種情況。就是大部分的題目都是自己有機會做出來的,卻不知道該從哪一題開始寫,在選擇了一題以後,又會擔心自己會不會來不及做其他題目。這種時候,我們會需要幫自己做一些時間分配,像是在選擇做某一題時限制作題時間,來避免自己在一題花太多時間。常見的時間分配方式有:在比賽開始時先花半小時讀題本、比賽一半的時間拿來寫部份分,剩下一半用來想完整題目的解等等。讀者可以在 Virtual 比賽時摸索適合自己的時間分配方式,制定一個能讓自己適當分配時間給每個題目的策略。

另外,剛制定完時間分配的策略後,很難馬上在下一場比賽就完美的照著策略執行。不需要太過灰心,這種比賽才能學習到的事情往往是要靠經驗來累積的。讀者可以透過每一場比賽去更熟悉自己時間分配的策略,同時,也隨時對策略做調整。這樣,便能在一場場比賽中不斷進步。

Chapter III. 漸入佳境