c0mp3t1t1v3 leetcode GKS
[LeetCode 181 & Kick Start 2020 A]
好微妙，難得有我可以寫完的比賽

啊...啊...

LeetCode 第一題模擬一下就對了

第二題因數分解，4 個因數只有出現在 p^3 和 pq 兩種狀況，根號 n 分解 + 檢查數量，剩下的直接算總和

第三題標準 bfs，開二維陣列紀錄是否走訪。因為每片拼圖都有一個編號，善用 index 建出 (dx, dy) 簡化 bfs 主體，還須檢查 (x + dx, y + dy) 是否超出邊界、拼圖形式是否對應，搜完再看 (n - 1, m - 1) 有沒有走過就好。

第四題簡化版模式匹配 (pattern matching)，題目要找出字串尾部的 substring 是 prefix 的最長子字串，看題幹可知用 failure function 比較適合，跑一遍抓 fail[-1] 的長度，回傳 prefix 即可。

---

kick start 第一題，有 n 件物品、拿取有 cost，要求總 cost 在 B 內盡可能拿多樣東西。開局馬上ㄎㄧㄤ掉做 01 背包 TLE，瞬間呆掉寫第二題，後來發現他跟經典背包少了一個維度，因此同樣拿 n 個東西下 cost 越少越好，greedy 味道。

第二題有 n 疊盤子、每疊 k 盤，每個盤子都有分數，拿取規則是由上往下拿，今天要拿 p 個盤子，問最大值。看起來就是背包變形，對盤子數量進行 dp，每疊盤子預先累加後就可以做背包。

原本以為只有三題，所以搶先過小測資，後來寫完第三題發現怪怪的往右點，第四題赫然出現在眼前嚇爛

第三題就是，給一遞增數列，要求相鄰數字差的最大值，但今天給你插入 K 個數字的機會，問最大值的最小可能是多少。標準 minimax 問題，對答案進行二分搜，下界固定一個不可能的答案、上界固定一個可能的答案，每次檢查中間的答案是否能在 K 次插入數字內做完。

第四題給 n 個字串、k 個 k 個分組，保證 k 整除 n，計算每個分組的分數總和，一個分組的分數是：裡面所有字串共同前綴的長度。直覺思路是，把儘可能共同前綴的字串放在一起，接下來要解決的問題是：

1. 如何定義「盡可能」共同前綴？
2. 要解決字串數量大、長度在 10^5 的效率問題

naive 倆倆比對就算在小測資也行不通，更何況假設有 a > k 個字串間共同前綴一樣的情況下，將誰踢出這個分組小圈圈也是問題，考量共同前綴這個性質，就會跟取出前綴建節點的 trie 脫不了干係。

假設現在建棵 trie，想想「共同前綴分組」這件事：字串在 trie 上的共同前綴會表現為 LCA，但如果數量過少就沒法進行分組，這時退而求其次，把未分組字串往更上面的祖先甩鍋，同時這就是多出來未分組的字串併給其他分組的概念，配合樹形結構可以得出 DFS：

對於每個節點
1. 把底下所有甩鍋都接回來
2. 因為是 trie，遞迴可傳遞前綴長度，也因為前綴夠深，於是就儘可能分組，剩下的再往上甩鍋

就可以算出答案

1. 對於字串長度很長的問題，就要做 compressed trie，幸虧 C++11 的語法，配合 vector 加節點 + index 當指標用的手法，編程複雜度沒有太高，建入字串時逐項檢查：當前節點是否分拆(*)、要丟給下面那個子節點、沒子節點可丟就創新節點
2. 頭一次寫出 compressed trie，但是在比賽中兜出來成就感 MAX
3. 依照對字串處理的印象，保守起見就先丟出 [字串]+'$'，後來發現這樣子處理到葉節點與非葉節點字串長度會不一樣，要多一個 if 判斷，但此題因為要計算數量，不用 $ 標示字串末尾應該也可行

(*) 此步驟涉及父節點指向子節點指標會更改

---

AtCoder 在同一天晚上，但實在懶得打 + 沒有在 AtCoder 上玩過就不玩了

---

AtCoder難度變動很大，我跟朋友上個禮拜可以寫出三題，這個禮拜一題都寫不出來XD

渟｜命中帶火辣 σ`∀´)σ : 怕