這次是 div1 + div2 的比賽
九題裡寫了四題
排在 1116 名，掉了 36 分
最近不管是 LeetCode 還是 Codeforces 都一直掉分 :(
https://codeforces.com/contest/1782
A. Parallel Projection
往四個方向都試一試就可以了
B. Going to the Cinema
從看到不需要 mod 就大概可以猜的出來應該有某種單調性存在
可以發現，假如 a_i >= a_j
則不可能發生需要選 a_i 卻不需要選 a_j 的情形
所以假如對 a_1, ..., a_n 排好序
最後的選法一定是
1 1 ... 1 1 0 0 .... 0 0
這種形式（1 代表去），只會有 n + 1 種可能
而合不合法只需要觀察 0 跟 1 交界的兩個點即可
所以不算排序可以 O(n) 解決
C. Equal Frequencies
以前寫 LeetCode 有被這種要相同 frequency 的題目坑過幾次
坑人的點在於，如果出現次數變成 0 的話就不會被計算在內
例如 [1, 9, 10, 10] 可以把那個 1 移到 9 變成 [10, 10, 10]
我的作法是假設可以分成 k 堆
取前 k 多的來看要搬多少次
因為只有小寫字母數量很少所以沒什麼影響
D. Many Perfect Squares
x 可能的範圍太大了也沒有單調性，不太可能是從這邊做
因為 n <= 50 ，對於兩個點 A[i] 及 A[j]
如果這兩個點都是平方數，則存在
a^2 = A[i] 及 b^2 = A[j]
則有
A[j] - A[i] = b^2 - a^2 = (b + a)(b - a)
顯然 (b - a) <= sqrt(A[j] - A[i]) <= sqrt(10^9)
對 (b - a) 可能的值都試一遍，每個 (b - a) 對應到相應的 x
代表這個 x 可以讓 A[i] 和 A[j] 同時是平方數
用一個 map<int, set<int>> 來紀錄每個 x 總共能讓多少人是平方數
取最高的即可
複雜度：O(n^2 * sqrt(C) * log(n) * log(nC))
其中 C 是 a_1, ..., a_n 的最大值，最多是 10^9