LV. 20
GP 49

【心得】講一些CPE、leetcode還有刷題的事情

樓主 SkankHunt skankhunts42
GP61 BP-
我只是一個隨處可見的上班族

就個人經驗分享一下 解題 這件事

我只是一個普通人 也不是啥IOI國手跟培訓營出身的

開始解題也是這幾年為了面試才開始刷的

現在學生真的是比以前輕鬆也比以前辛苦

輕鬆在哪?因為刷題普及化 所以網路上資源多 入門快 以前這種資訊你不是培訓營的也不會接觸到 演算法怎麼帶 怎麼練 那是要遇到好老師 我有朋友就是每天硬幹UVa 但很多水題其實解了只是浪費時間

那辛苦在哪?因為刷題普及化 所有參賽者的程度都有所提升 題目只會越來越變態

我在學時剛好是CPE第一屆 也是第一批通過的

很多學生甚至對上班族對解題都有障礙 這不難理解

因為解題的練法與一般科目練法不同

我是leetcode contest rating 25%內, top 5% user (但這個水準去codeforces依然會被打爆)

是從白紙練起 我個人的經驗應該算是有些參考價值


首先 解題難在哪?為什麼很多人練不好?

1. 解題的第一個問題 你要能看出題型

書卷獎可能可以默寫紅黑樹 so what?

演算法競賽除初階題不會跟你講"嗨 請你用排序演算法幫我排序這個陣列"(這種在中國叫模板題、板子題)

所以演算法必須要有能夠識別題目的能力


2. 解題的最基本需求 是語言能力

這語言能力有兩個 第一就是英文 你連題目都看不懂 那只能吃鱉 第二個就是程式語言

CPE可能會有中英對照 但到面試 到演算法競賽 不一定會有人給你中文

英文就是搞解題的最最最低門檻



第一階段 幼幼班

幼幼班可能覺得自己程式能執行 編譯能過 就叫會一個語言了

而演算法競賽比的其中一項 就是對語言的熟悉度 這表示標準函式庫的核心內容 你都要會

1. 怎麼用min heap, max heap?你有辦法自定義comparator嗎

2. 怎麼用binary search?什麼是upper bound什麼是lower bound?

3. 如何對map的key值由小到大或由大到小循序存取?

甚至包含 transform/map 還有 tuple的技巧, 可能有些人會納悶transform 跟 map 我用for迴圈就可以了 幹嘛額外再學?

很遺憾的是 程式競賽也比手速 你寫的程式碼越精簡越好懂 解題越快
(經驗告訴我 如果你解一題寫的程式碼越長越複雜 判定條件越多 你越有可能在往錯誤的方向走)

幼幼班要怎麼練?就是狂解easy題跟板子題,但是解的時候要注意幾件事

1. 永遠追求最高效能

2. 永遠問自己有沒有更好/更快的方法寫同樣功能的程式碼

這兩個基準適用到所有階段


第二階段 初學者

初學者我就假設你什麼演算法都不會

只會最基本的 暴力法 跟 模擬題(不過別小看模擬題, 很多人可能連模擬題都寫不出來)

這個時候就是開刷 leetcode 課程

這些課程題目都是分門別類的

排序、二分搜、BFS、DFS、最短路徑、貪婪這些 大部分學校都有教 也是基礎題

初學者可能比較少看過的是 二分圖、union find、bitmask、backtrace

當然 看過不代表會 新手最大的噩夢應該是DP就是一個很好的例子

按課程刷 我是建議一次同時進行兩個課程 不會太多 也不會太少

你很快就能有一個基礎的知識體系

熟悉經典題 你leetcode rating就能上1700 真心不騙


第三階段 撞牆期

當你到1700以後 你會發現自己開始有瓶頸 程度上不去

這時你可能會開始追求一些複雜的演算法或DS

作為過來人 我可以告訴你 絕大多數的競賽 考的都不是複雜的演算法跟DS

舉例來講 十次周賽的hard有沒有出現一次 segment tree 都是問題

複雜的演算法、DS只是補足一些冷門的知識點 如果你leetcode比賽無法穩定解完三題

你的問題不是出在高階技巧 而是練法錯誤

我前個階段是不是告訴你分門別類刷? 如果你還在這樣刷 那就錯了

這種作法只適用於學習階段 當你上到1700 這種練法就已經無效

大部分人會陷入一個誤區 "我XXX題不太會解, 我就搜XXX題狂解"

舉個例子 binary search你會不會? 大部分人的都說會

有些hard題也只需要binary search就能解, 為什麼通過率那麼低?

你有沒有經驗比賽中完全看不出這是binary search的經驗?

因為binary search就是一種典型"江湖一點訣 說破不值錢"的題目

當你用題目分類來練題 你就已經獲得提示 而很多時候 題目考的就是這個鑑別問題的能力

這個時候請你以每天解五題為目標 隨機挑題 但這個五題並不是五題 而是你不會的五題

如果你看到一個題目知道怎麼解 請不算數 解完挑下一題解

至於題目卡多久 要看solution 我的建議是 至少一小時 (有時我甚至會想一天)

甚至有一些極端的例子是想一個月(但這是大師級的練法)

在這個階段你需要練就一種作弊能力

那就是看測資規模猜演算法 這個很作弊 但大家都在做 而且是題目公開資訊

我舉個例子 如果測資規模給你10^5 你還在想n^2演算法 那就沒戲唱了 反過來 如果是1000 那n^2就有可能

同樣 如果數值規模是 15 ~ 31 區間 那很有可能是在考bitmask

簡單來說 你看到測資就要反射性剔除一些不可能的選項 不要傻傻在那邊TLE


第四階段 撞更大牆期

這個時候你的rating少說1800了

應該跟我一樣拿到knight的badget

解題應該變成你的日常 甚至是休閒 每週就是固定打週賽

這個階段其實已經沒人可以教你什麼 我也不能

因為我也還在這個階段

其實這個階段要做的事情就是瘋狂解題 不斷培養敏感度跟題目識別能力

要開始學一些進階的知識也可以



解題最重要的其實是心態

自信心會左右你的表現

我最近都在忙著打電動 有時比賽也能打到一千多名

反觀我自信心低到爆棚時 就算每天狂解 rating還是狂掉

千萬不要忘記 所謂的題目難度 其實是一個機率問題

leetcode分類只有分三個等級 其他網站是按數字來分

舉例來說 一個難度1300的題目 你rating 1500也可能會翻車

同樣 一個難度1500的題目 rating 1300也有機會解得出來

不是說我今天看到程度高出我的題目 我就直接放棄 (甚至說 要提升程度 你只能解你不會的題目)

每個題目要求的知識點 技巧 思維都不一樣 甚至昨天的你跟今天的你也不一樣
(我有的時候看解過的題目 可能這次的解法跟上次完全不同




常見的幾個問題:

1. 每天要解幾題

每天解幾題看個人時間 我自己狂的時候一天解個十幾題 但題數不是重點

如果"我要每天學到新東西" 以我的經驗 一天解個一兩題就夠累了

盲目追求題數跟KPI無法使你成長 只是在瞎忙

但我個人建議 為了保持手感 每天都要解題 週賽也要固定打

2. 有社群嗎

解題是自己的事 我參加過一兩個社群 我只能講絕大數都在伸手或哭難

除非你是培訓營 有教練在帶 但你不是 你是的話也沒必要看這篇文章

我也遇過那種題目過了 效能倒數5%就在灑花以為自己會的

基本上 都在浪費時間 解題是自己的事

我不否認交流的重要性 但有的時候我看別人的程式碼就能學到東西

talk is cheap, show me the code

3. DP好難

很多codeforces的大師級人物也不敢說自己會DP (當然大師可能是在謙虛

DP就是這麼難

我只能說 多解就會有感覺 這是廢話 卻也是適用於所有題型的真理

DP的困難點是狀態轉移 以及是否使用DP

所以有的時候你可能會陷入使用DP還是greedy的疑惑

第一種是從測資規模判斷 第二個是從最佳解的有效性

greedy是當前最佳解可以擴展到全域最佳解 但DP不是 當你發現你需要從子問題的答案挑選最佳組合 那他很有可能是個DP題

我會建議你當你遇到這類問題時 將其拆解成小問題 自己推導看看

4. 數學重要嗎

競賽考的數學主要有幾種: 組合(偶爾會要你算機率, 但還是古典機率的範疇) 幾何 數論

其他你只要會加減乘除跟指數就好

組合跟數論應該算是最大宗 計算幾何因為不好做而且在學/業界出現率都不高 所以也是懂高中數學就好(除非你做電腦繪圖學的)

數學最重要的一個是餘數 因為模太重要了 甚至有時會結合DP來考

質數則是基本 你不會建篩表有些題目你解不了

其次還有一個就是模反 這個雖然leetcode比較少見 但模反在某些數論題目是關鍵

5. 要準備模板嗎

看比賽而定 就leetcode而言 我認為不需要

但就codeforces這類正統的OJ網站 就很有必要

6. 我寫程式的速度不夠快

程式競賽中 解題的速度絕對影響成績

寫程式的速度不夠快 你要檢視自己的幾個能力

a. 是不是有英文閱讀障礙 (畢竟不是native speaker, 我有時也會誤解題目)

b. 是不是對語言不熟

c. 是不是根本就對這個演算法不熟練

d. 是不是無法清楚地實作自己的想法或根本沒有想法

e. 是不是太緊張

b跟c有一個很簡單的檢視方法, 如果你發現你的程式碼跟別人的答案相比長太多, 代表你不熟練

寫python其實是最好壓行數的語言 而C++則取決你對STL的熟悉程度

甚至我可以講 如果你還常常遇到compiler error 代表你程式碼寫太少

請以一次送出/執行就通過編譯為目標來訓練自己 不要依賴自動完成

至於b跟c以外的 就是多解能解決的事




最後, 各階段可用網站:

第一、二階段:

Aizu Online Judge

AtCoder

LeetCode(學習)

第三、四階段:

LeetCode(打比賽、準備面試)

Codeforces

AtCoder
61
-
未登入的勇者,要加入討論嗎?
板務人員: