LeetCode 周賽心得

前言

2022-04-15紀錄：
周賽也打了不少次，從之前最慘的一題幫，到現在也成功 All Kill 幾次。 紀錄一下從爬到 1923 分的心得。

2022-08-11更新：
這陣子曾經爬到 2040，結果幾次連摔回到 1964，有點慘。
雖然很想說是近期作弊者猖獗害我失分，但其實自己表現不佳才是重點。

2022-12-21更新：
本來今年設下的目標是 2100，沒想到竟拿到 Guardian 徽章，算是給自己最好的禮物。
最近幾次 Q4 的完成率五成，朝著七成繼續努力。

2023-06-03更新： 本來想說今年內能打到 2300 就不錯，結果竟然半年就達成。
勉強有七成機率可以 AK，不過各周賽難度落差有點大，有時候甚至沒有 hard 題。
加上最近作弊風氣盛行，有時候寫得慢一點，直接被兩千個作弊仔超車，痛失分數。

2024-01-10更新：
目前最高分紀錄 2447。
近來 Q4 難度明顯提升，周賽 AK 率連五成都沒。
作弊仔越來越多，常常賺個兩三次 20 分，然後一次噴 50 分，不斷在 23, 24 之間徘徊。
希望今年能穩坐 24、上看 25。

解題策略

• Q1

  通常都是很直觀的題目，而且測資不大，基本上暴力法都能過。
  不要考慮效能，直接寫下去就對了。

• Q2

  大部分還是可以用暴力法過。
  但有時候測資會比較大，需要簡單數學公式(如：等差數列和)求值。

• Q3

  可能會需要比較常見的演算法或是資料結構，例如：排序 + 二分搜，有時候會有回溯和簡單的 dp。

• Q4

  大多數是 dp，有時候問題不太直觀要考慮預計算，省去一些重複計算。

  如果測資範圍異常大且找不出規律，可以觀察答案是否具單調性，往二分答案的方向去猜想。通常會搭配 greedy 或是滑動窗口。

  如果只是看起來很囉唆，但是不需要什麼高級技巧的大型模擬題，記得把變數名稱寫清楚，長一點沒關係。
  分類討論考慮完所有的情況之後再開始寫。可以的話拿張紙把情況寫且下來或是畫圖，會比腦子空想容易很多。

  有時候會跑出比較偏門的東西，如：併查集、線段樹、特殊字串演算法，只能看是不是剛好學過了。
  低機率考腦筋急轉彎，如果 AC 人數多到很奇怪，搞不好思路轉一下其實就過了，根本不需要複雜計算。

看測資盲猜演算法

算是奧步，現實碰到問題沒辦法這樣搞的。
而且只是傾向，並不保證猜中。

• N < 20 回溯暴力枚舉
• N < 32 各元素只能出現一次(有或沒有)，bitmask 表示狀態
• N < 2000 很有可能是二維dp
• N < 10^6 雙指針、線性dp、滑動窗口、heap、stack 或是 greedy
• N < 10^9 高達八成是二分搜；不然就是這參數不影響複雜度
• N > 10^9 目前只看過數位dp

看題型盲猜演算法

• 無向圖中求連續3或4個點，可以列舉中心或是邊
• 求整除的題型往 gcd 或是 lcm 去考慮
• 樹狀結構求直線路徑，考慮 dfs + 樹狀dp
• 計算 n 的高次方，使用快速冪
• 多次重覆使用的值，做預計算或是快取
• 一坨 [x開始, y結束] 的區間可以視作成 位於 x 和 y 的變化量，排序後統整成差分陣列
• 求子序列且要檢查相鄰元素狀態，考慮 dp
• 求陣列合法的分割方式，若存在子問題則 dp 枚舉分割點
• 關鍵字包含最大值最小化，一定可以二分答案
• 區間查詢考慮前綴和；若需要修改才考慮線段樹、BIT
• 一對多/多對一最短路選 dijkstra；多對多選 floyd-warshall

目前需要改進的缺點

1. 看完題目，不揣測題意，WA 懲罰一次 5 分鐘非常痛
2. 測資範圍記得看，避免把問題複雜化
3. 範例測資都通過後，再想想有什麼 edge case，考慮清楚才提交
4. 提交答案時候左手離開鍵盤，避免敲到
5. debug 用的 print 要確定刪乾淨
6. 有時候寫出不來，重讀一次題目確認，不要硬上
7. 變數名稱太長時慢慢打，不要拼錯

參考資料

https://leetcode.com/discuss/general-discussion/940379/Advice-%3A-Contest-Tips-for-those-who-are-Beginning-from-a-Seasoned-Contest-Participant!
https://codeforces.com/blog/entry/21344