經過之前四場內掉了超過 250 分
其中一場還只寫出兩題暴扣 144 分
最近這兩場狀況終於回來了
總算重新回到 1900+ 變回紫色
這一場好像還是我表現最好的一次
七題寫了五題排在 75 名
而且這次還第一次成功 hack 到人 舒服
https://i.imgur.com/cnL4mcB.png
A. Two Towers
https://codeforces.com/contest/1795/problem/A
https://codeforces.com/contest/1795/submission/193839884
可以看成是將兩座塔頭對頭接起來找分割點
相鄰顏色一樣就必須切
如果必須切的邊界超過一個就會失敗
B. Ideal Point
https://codeforces.com/contest/1795/problem/B
https://codeforces.com/contest/1795/submission/193845093
可以發現如果沒通過 k 不選一定 optimal
如果有通過 k 選下去一定 optimal
直接維護一個陣列紀錄每個人被選的次數
看 k 選的次數是不是唯一的最大值即可
因為 n <= 50 所以 O(n^2) 就會過了
不過用維護 adjacent difference 的技巧可以 O(n)
這題我成功 hack 了六個人，基本上都是寫成 O(n^3)
我覺得是沒注意到 python 的 `in` 做在 list 上會要遍歷整個 list
C. Tea Tasting
https://codeforces.com/contest/1795/problem/C
https://codeforces.com/contest/1795/submission/193859409
比完才發現很多人是用 binary search 做的
我是用 min heap (priority_queue) 去做
這個 priority_queue 裡存的是還有剩的茶
且在第 i 輪時，priority_queue 裡存的是
a_j + (b_1 + ... + b_{j-1}), for j <= i
第 i 輪時，我們想找出 taster i 總共能喝的數量
能喝光 j 的條件是
a_j <= b_j + ... + b_i (第 j 個茶是從 第 j 個 taster 開始喝)
也就是
a_j + (b_1 + ... + b_{j-1}) <= b_1 + ... + b_i
如果不合法就 pop 掉並計算喝掉的數量
而那些留在 priority queue 的都一定 >= b_1 + ... + b_i
所以他們可以喝整個 b_i 的量
D. Triangle Coloring
https://codeforces.com/contest/1795/problem/D
https://codeforces.com/contest/1795/submission/193870666
這題其實就是在考排列組合而已
首先，每個三角形最多能選兩個邊
因為 n 是偶數，所以一定可以讓每個三角形都恰選兩個邊
總共會有 n/2 組 RRB 及 n/2 組 RBB
有 C(n, n/2) 種分法
對固定好是 RRB 或 RBB 的三角形而言
要獲得最大分數等價於挑掉最小值
所以最小值有幾個就是這個三角形的選擇數
最後乘回 C(n, n/2) 即可
E. Explosions?
https://codeforces.com/contest/1795/problem/E
https://codeforces.com/contest/1795/submission/193897368
因為爆炸必須在最後使用
可以發現，假如我們想要在點 i 使用爆炸
全死光的條件是
H_1 < H_2 < ... < H_i
H_i > H_{i+1} > ... > H_n
所以我們只要分別作出 L, R 讓
L[i] := 使 H_1, ..., H_i 合法的最小 cost
R[i] := 使 H_i, ..., H_n 合法的最小 cost
因為是對稱的所以看 L 怎麼做就好
對 H_1, ..., H_{i-1}
把相鄰且差一的聚集起來，形成很多個梯形
例如是 [a, a+1, ..., b], [c, c+1, ..., d] 這樣
當 H_i 進來，如果 d < H_i - 1 當然就沒事
但如果 d >= H_i - 1, 則 d 必須變成 H_i - 1
且 [c, ..., d] 內的每個人都要減少一樣的量
如果 c 變得比 b 小就繼續往前合併
所以可以用 stack 來維護一堆梯形
每個梯形只需要紀錄頭尾
因為只要某個梯形必須下降的話就會和其他梯形合併
所以對每個 i 而言，以 i 結尾的梯形最多只會進出stack 各一次
還是可以 O(n) 完成
後面兩題 F G 就沒時間做了