競賽學習方法

• 蔡旻諺 （baluteshih）
  • 新北市立板橋高級中學
  • 台大資工（資訊）系 大二
  • 2019 IOI 銅牌 Rk. 96
  • 2017 沒進選訓, 2018 2!, 2019 3!

剛來選訓營……

• 選訓營的課重要嗎？
• 如果聽不懂教授上的課該怎麼辦？

不好說

但是！

• TOI 教授們上的課大多數都是大學會學到的內容，所以除非已經會了，不然聽一聽也不虧
• 畢竟是教授，給點基本的尊重稍微有點反應比較好，通常可以做自己的事，但是可以開個小視窗注意一下教授在講什麼東西

沒課能上，那選訓營是幹嘛的？

• 選訓營是一個：
  • 讓全國各地好手可以集中在一起交流的場所
  • 讓選手可以請公假專心練習的場所
• 最後，透過集中選手的環境，選拔出最後適合代表台灣出國比賽的選手
• 學習呢？

學習要靠你自己

• 這是集訓營不是補習班，千萬不要抱持著「乖乖上課，乖乖寫作業」就可以學到東西的打算在這裡生活
• 可是資源呢？如果想要主動學習，那應該要去哪裡找資源？

看看左右邊吧

• 選訓營一個最大的用處就是你可以在這裡找到全國各地興趣和你相同的人交流
• 與你同坐在這間教室的其他 35 個人，他們不是敵人，他們全都是你的朋友

多多交流！

• 如果你發現這裡有一群人感覺好強好強，不要害怕與他們交流
  • 多與強者接觸，你自己的實力也可以跟著提升

多多交流！

• 如果你就是那群被認為是強者的人，不要無視那群崇拜你的人
  • 強者往往會不小心沒發現自己在某些地方知識的不足，多跟其他人交流，常常可以幫助你鞏固根本的知識

你應該要有的好習慣

• 主動上網找東西學習、找題目練習
• 主動去找其他人詢問自己不會、不熟的東西
• 主動分享資源給別人，聽聽其他人對你分享的東西的看法

不要讓選訓營成為你的壓力！

• 快樂交流，你在這裡認識到的朋友高機率會持續有聯絡
• 希望你們可以好好享受這 13 天
  • 或 27 天
  • 或更多(?)
• 這有可能是你們高中生涯最快樂的幾天(?)

為什麼會這樣？

刷題固然重要

• 但要進步肯定不能只顧著刷題
• 所以我要來分享一下近期我發現並整理過的一些東西

接下來講的全都是我自己最近思考過後得出的結論

• 沒有任何根據，但各位還是可以參考看看

把 Codeforces 當作比賽練習已經成為了台灣競程界的趨勢

• 每個人開始非常在意 rating，把目標放在打上紫人、橘人

問題一：變質的執著

• 衝高 rating 令人爽快，可是 rating 的成長時常不如預期
• 不少人只要掉 rating 就開始不愉快，甚至會產生挫折，進而造成練習的倦怠

問題一：變質的執著

• 不是說把目標放在衝高 rating 上不好
• 而是想跟各位說，CF 其實沒那麼重要
• 即使是 CF 紅人，都有可能在 OI 的比賽被打成智障

問題一：變質的執著

• 請各位把 CF 當成一種對比賽心境控制的訓練方式
• 線上比賽的好處就是為了讓你有臨場感
• 不管打好、打壞，只要你有辦法穩定住自己的情緒，你就還是成功的
• 所有結果都只會在正式比賽中才真的是實際的

問題二：CF vs OI

• Codeforces 的出題面向其實很不 OI
• 至少這一兩年開始已經越來越明顯了

問題二：CF vs OI

• CF 的題目 （短時間比賽、有 penalty）
  • 大多數著重瞬間性的想法
    • 梗題
  • 實作通常不難
  • 前期題目通常不會有太多經典算法的成份

問題二：CF vs OI

• OI 的題目 （長時間比賽、無 penalty）
  • 基本上著重對性質的觀察
  • 實作通常有一定的難度
  • 部份分成為了引導題目滿分的關鍵
  • 對於經典算法要有一定熟悉度，才有辦法在觀察出性質後繼續套用

問題二：CF vs OI

• 之前和網路上一個在紅人邊界漂蕩的人討論過
• 我們得出的結論是， CF 一般場 (Div1, Div2) 通常的宗旨是讓人享受解題的樂趣，反而不具太多教育性
• 而要練習 OI 解題的話，練 CF 反而會是一個效率非常低的做法
  • 因為實作少、也不太能有機會仔細分析題目（比賽時間短）
  • 真的有練習價值的題目都在後面，但你真的會去補嗎？

結論

• 把打 CF 當成練習比賽心境控制的管道
• 升降 rating 或成績不要太在意
• CF 打得爛，OI 不一定差；CF 打得好，OI 不一定好

很多人在刷題的時候好像都只專注於解開自己遇到的題目

• 這些題目的理論基礎都是環環相扣的
• 觀察出他們的關聯性，你才能解出變化過後的題目！

因為很不實際，我決定舉出我高中的例子跟大家分享

• 還記得我是板橋高中的嗎？
• 我高一的時候勉強有學長能帶一些東西，但他們也沒有了解到很多
• 高二我完全沒人能依靠，所以我選擇自己跳出來教學
• 造成的結果就是我為了教學，做了許多思考上的訓練

動態規劃

• 你會想到什麼？
• 定狀態、寫轉移、找基底
• 無後效性、算過的東西不要再算
• 優化優化優化好多優化

說起來為什麼 DP 的變形可以這麼多啊？

• 我小時候不禁有這樣的疑問
• 但我相信理論是美麗的，這些變形肯定都只是一個單純的理論根據！

我開始觀察優化的本質

• 單調隊列優化？斜率優化？1D/1D 優化？
• 為什麼又有線段樹優化…
• 然後我發現了他們共同的性質
• 他們全都是資料結構問題

所謂 DP 優化，只不過是用資料結構加速轉移的過程！

• 計算 \(dp[i]\) 的值，就是一個詢問
• 維護 \(dp[i]\to dp[i+1]\) 的轉移來源，就是一個修改
• 所以，定好狀態，寫出轉移之後，根本就只要解一個新的問題就好啦！

想到這裡我想通了很多東西

• 為什麼「超大畫框設置」會在 DP 被拿出來講啊？
  • 因為 1D/1D 這個技巧通常都會在 DP 出現，但「超大畫框設置」本身只是一個單純的資料結構問題！
• 為什麼有些 DP 題會突然用到線段樹還是 BIT 啊？
  • 因為有人發現了，轉移來源在變化的時候可以用資料結構維護！

才不只這樣呢！

• 為什麼 LIS 的 DP 可以用二分搜做，不覺得很奇怪嗎？
  • 因為維護滾動後序列的長相是一個資料結構問題，而加元素進去是修改
• 為什麼有些 DP 會互相轉移，但還是能做啊？
  • 想想看 dijkstra

才不只這樣呢！

• 為什麼有些機率、期望值 DP 還要移項甚至要高斯消去啊？
  • 因為 DP 的本質是在解決一個「遞迴函數」的答案
  • 當初 DP 的核心一直以來都只有一個，那就是算過的不要再算
    • 只是一個加速計算函數答案的方法
  • 真的只有這樣，所以列出 DP 式之後反而發現最後的解好像不是在 DP 是正常的
    • 你根本只是在列函數和遞迴式而已

最後談談 greedy

• 不知道有沒有人聽過 greedy 也有狀態這東西
• 當前序列的長相就是一種狀態…之類的
• 其實 greedy 就是只有唯一轉移點的 DP
  • 更精確的說，是所有可能轉移點皆可轉移

不相信嗎？

• 考慮線段最大獨立集問題
• 定義 \(dp[S]\) 代表元素的長相是 \(S\) 這個集合時的最大獨立集大小
• \(dp[S]=\max\{dp[S\setminus\{j\mid i\cap j \ne \phi\}]+1\mid \forall i\in S\}\)
• 透過性質觀察，我們得知「選右界最左邊的，肯定是好的」
• \(dp[S]=dp[S\setminus\{j\mid i\cap j \ne \phi\}]+1\)
  • 其中 \(i\) 是右界最小的線段
  • 然後眾所皆知的，只要排序剩下的事情都能輕鬆解決

多做思考訓練，找出各大變化題的共通性

• 找到這些變化題最原始的「根」，並蓋出「變化樹」
• 這些思考訓練很多都是我為了教學、為了講少一點(?)才一直在思考的
• 各位不妨也可以試試看
• 我不能保證對每個人都有用，但我確定這對我競賽的能力提升很有幫助
  • 思考過程會加深你對這個算法的印象

毒瘤！

• 想那麼多，直接砸 XXX 就好啦！
  • 反正我寫很快
• 我用 OOO，複雜度明明是對的可是 TLE 了…
  • 別人都沒壓力的過欸？
• 我當下看完就直接開始刻 XXX 了，可是我刻不完QQ
  • 為什麼別人只要寫短短的，你要寫這麼長？

到底要不要學毒瘤

• 說起來為什麼會有毒瘤出現？
• 不過是因為他可以
  • 更 general 的直接把同一類問題砸掉
  • 解決只有他才能解決的問題

使用毒瘤會有一定的犧牲？

• 思考的路線多了一種，容易擾亂思緒？
• 看到題目能用就砸，卻都寫不完或 TLE RE WA？
• 那不是科技的問題，那是你的問題

讓科技變毒的是選手，不是理論本身

• 請抱持著欣賞的態度去理解那些高科技
• 學習新科技一點都不可恥，也一點都不毒瘤
  • 重點是不要在比賽中瘋狂想砸，要砸大科技前也請先想好是否真的一定要這樣做
  • 給自己一點緩衝的時間
  • 真的要刻的話，要嘛就是你有自信，要嘛就是你走投無路了

給各位一點參考

• CDQ 分治、整體二分搜為什麼會被時常講在一起是因為他們都是從分治這個概念衍伸出去的
  • 所以學習這兩個東西，比賽不一定會用到，可是卻能加強你對分治的理解
  • 思考訓練

給各位一點參考

• 我高三 APIO 差點看到一個子任務要砸整體二分
  • 我知道整體二分要寫一陣子，所以我停下來給自己五分鐘思考是否真的要這麼做
  • 然後我想到了簡單的排序解，我煞住了
  • 幸好我這麼做了，因為要是我真的寫下去了，我後來賽末壓線拿到的 20 分將會消失

給各位一點參考

• 我高三一模看到一個子任務想到了 treap 套啟發式合併
  • 我知道要寫一陣子，所以我給了一個整點當 deadline，要是沒想到別的，就刻
  • 我出去上了個廁所回來還是沒想到，但這個思考過程釐清了我整個算法的脈絡
  • 因為 deadline 到了我就直接刻下去，因為思考很清楚，我 20 分鐘內就寫完拿到分數了
  • 我夠有自信，刻下去當然不是問題

結論

• 不用排斥學習新科技
  • 理解他們有助於你理解更基本的東西
• 不要真的積極的瘋狂學習新科技
  • 說實在的有些東西可以從別人的消息得知很沒有用
  • 有興趣再學！
• 賽中不要一開始就想砸科技，就算真的不幸發現可以砸，也請停下來想想

Q & A