如何準備程式競賽？ ——我是如何贏得美國資訊學奧林匹克競賽3屆金牌的
如何準備程式競賽？
我是如何贏得美國資訊學奧林匹克競賽3屆金牌的
作者：Andrei Margeloiu，2017 Google HashCode競賽金牌獲得者
高中第一年，我從0開始學習了C++。一開始我對程式設計、演算法和數據結構一無所知，幾個月之後我纔開始寫程式碼，當時計算機資訊學奧林匹克競賽來了，正好我可以試試我的學習方法是否有效。
經過2天的比賽，我贏得了金牌。
我很震驚，因爲我超過了有5年經驗的參賽人員，我知道我很努力，但是這個成績超出了我的期望。這個比賽很適合我，我也因此全心參與其中。
我知道是什麼讓我如此成功，現在也在此將經驗分享與你。
我需要學習什麼語言？
C++ 強烈推薦，非常快，由於可以使用STL，可以很方便的實現不同的演算法。任何比賽都支援C++，我一開始就是使用這個語言。
C語言 —— 如果你懂得C，你也可以使用C++。
Java —— 比較慢，但是Java有大整數，不過只有少數題目需要使用。如果題目的時間卡的比較緊，容易造成time limit exceeded。一般比賽都沒有Java。
你能去哪裏練習？
推薦SPOJ，上面有大量優質題目，並且有解答。也有對應的支援網站SPOJ.pl。
首先，你需要掌握基礎知識
當你學會基礎語法後，你就可以開始解題了。從簡單的題目開始，在這個階段，你的目標是鍛鍊自己的程式碼風格。你可能喜歡寫程式碼的時候用很多空格，或者喜歡將大括號放在if的同一行。
你需要找到你自己的風格，因爲這是你的。
在提高你的編碼風格時記住如下兩點
1、實現簡單。你應該習慣於對你自己的解題思路，爲啥？因爲比賽的時候，你最不想發生的事情是迷失在自己的程式碼中。多思考5分鐘，比動手寫10分鐘要有效的多。
2、簡單易讀。這意味着偵錯簡單。必須承認的是，bugs總是經常出現，你知道當你只有10分鐘的時候你卻不知道bug在哪裏的感受？相信你肯定印象深刻。爲了解決這個問題，程式碼必須易讀，這樣容易跟蹤和偵錯。
如果提高實現的速度？
練習、練習還是練習。我建議你先練習SPOJ上解決最多的前250個題目。逐個順序的解決這些問題，並且思考一個小時以上。
不要說「這個問題對我來說太困難了，我想試試下一題。」這是失敗者的思維習慣。拿一支筆和一張紙，然後開始思考。這樣，你纔有可能找到答案，也因此你才能 纔能夠提高演算法思維，如果你思考超過了一個小時，你可以檢視參考答案。
這個方法的結果是：你能夠快速實現演算法程式碼，並且能夠學會經典的題目和演算法問題。
第二點：你必須熟練掌握演算法和數據結構
通過循序漸進的方式前進。如果不會走路你覺得你會跑步？當然不現實。如果地基不好，你能在上面建造摩天樓嗎？當然也不現實。
這意味着你不能夠把步子跨大了，如果你這樣做，你會漏掉很多細節，隨着時間的推移會造成越來越大的知識缺口。
從基礎演算法和數據結構開始
開始的時候很困難，因爲你不知道要怎樣開始，我建立了一個演算法和數據結構的視訊課程，這個課程是按照我的想法來設計的，結果在開始的一個月，竟然有超過來自100多個國家的3000+的學生加入這個課程。
如果你只做簡單題，你永遠也得不到進步。
有效的解決你不懂的問題的唯一辦法是找到這些題目然後解決掉。我就是這麼做的。通過選擇解決一些難題，我學會了很多我從沒聽過的新技術。
你每解決3個新問題，就能學會一些新的知識。如果沒有，那麼更慎重的選擇題目吧，一定要選擇難的題目。
當你完成了SPOJ上的250道題，你會對演算法競賽有一個大致的瞭解，通過對基礎演算法的深入理解，高難度的演算法題也會變得更加容易理解，以此你能夠快速的運用你的知識。
現在開始在各個演算法專題上更加深入的學習吧。
SPOJ上有很多資源，每個主題都有Top 10的演算法和數據結構。除了那250道題，你可以從列表中獲得更多題目。也有一些你從沒聽過的題目，從簡單的題目開始學習。
如果你不強化你的知識，你就會忘記它。
當你學習一個新的演算法知識點時，在SPOJ上搜尋相同tag的題目，用這個演算法做2到3題。
理解好DP演算法，這是你贏得比賽的必要條件，以我的經驗來看，每次比賽至少有一道DP題，許多人會很頭疼DP題型。
如果你真的掌握了DP演算法，你就離成功不遠了。
我很喜歡DP題型，DP的祕訣是:考慮全域性優化，而不僅僅是區域性優化。你需要將問題分解成簡單的子問題，每次解決一個子問題，最好將這些子問題組合起來形成解決方案。與DP相對的是貪婪演算法，因爲這個演算法每一步只考慮區域性優化，而區域性優化可能導致得不到最優解。
當學習新的概念時，可以看一下TopCoder的入門教學，因爲這些教學很容易學，我就是看這些才真正弄明白二分索引樹的。
努力學習
你聽說過哪個奧林匹克冠軍是沒有經過數年的刻苦訓練才贏得比賽的嗎？美國資訊學演算法競賽每一年的比賽在九月開始次年四月結束。這中間的八個月時間，我每天練習五個小時。
這五個小時我只練習演算法題，有些日子我也會花8到10個小時，爲什麼我能做到這些，主要還是興趣和熱情所在，每天從學校回家我就直接回臥室做題，或者學習這些題裏面新的演算法。
如果你也想拿獎牌，也必須刻苦起來，做題然後堅持，日常生活中也需要多思考，比如你在去超市的路上，或者開車的時候。
當你睡覺的時候，你的大腦會重新組織你當天所學的，就像將書本按照字母順序放到書架上一樣，基本上你的大腦會思考每一個你遇到的問題。
你可以通過這個特點，在睡覺之前看一道難題，記住這道題需要的知識點，你並不需要解決這道題，然後入睡，你的大腦可以自動開始處理這道題，當你醒了的時候，你會驚奇的發現你已經可以解決這道題了。
試試看，你會發現這像黑魔法一樣。
用vlog記錄
這一段和競賽無關，我只是想讓你知道，如果你也是20歲左右，你對我看待這個世界的方式比較感興趣，我在YouTube上有一個vlog，我在這上面發佈了我對這個世界、人生和電腦科學的一些看法。
更聰明的工作，這是成功的訣竅，你需要一個目標。
我們都容易產生拖延症，看美劇總比刷DP容易，但是，你得慢慢糾正這種習慣。
如何戰勝拖延症？
通過制定目標，你總能找到感興趣的問題，因此才能 纔能學到新的知識（上面有很多資料可以參考）。因爲上面推薦的SPOJ題目都是必做的，而不僅僅是看看。
我就是通過制定目標來克服拖延症的，我用一張紙做了一個日曆，上面會標註每天要解決的問題。每次都提前設定好2天的問題，這樣我就能知道接下來如何安排時間。
通過這種方式，我能夠比較積極的完成問題，並且找到新的問題來填充後面的日曆，每次完成目標，就會感覺很有成就感，希望你也能喜歡這樣。
採用紙質日曆，不要使用手機上的checklist之類的app，因爲到第二天你可能就忘了app上的事情。
如何有效的debug？
你想變得更加專業？如果是，那麼你需要練習通過大腦來debug。
這是到目前爲止我所能知道的最有效的debugging技術。這種方式完全不需要偵錯程式。你的大腦需要同時處理多個分支的情況，這樣你對程式碼的執行情況會非常清楚，如果你只是侷限在偵錯程式，那麼你可能很難掌握演算法全域性的執行狀態。
這有點類似於大師級的棋手，每次都會往前考慮3步。
我把這種技術作爲首要偵錯，最次纔會考慮使用偵錯程式。
在大腦中偵錯這種做法需要你不斷地練習，當你提交一個問題報錯的時候，不要用偵錯程式，而是去閱讀程式碼，思考這一行到底發生了什麼，這個if語句會如何影響程式？如果是在回圈中，這個iterator的值會是多少？
這樣你一直獨立自己去思考，你後面在寫程式碼的時候其實就是在實時偵錯。
如果你覺得這篇文章對你有幫助，請關注微信公衆號《ACM演算法日常》。
關於作者
Andrei Margeloiu是一名熱血程式設計師，愛好創業和自然，你可以在LinkedIn上聯繫他。
個人公衆號：ACM演算法日常
專注於基礎演算法的研究工作，深入解析ACM演算法題，五分鐘閱讀，輕鬆理解每一行原始碼。內容涉及演算法、C/C++、軟體設計等。
