應該是第一次寫這種不公開的比賽的貼文吧。
今次比賽4道題，只中兩道題是以前賽事的題目，只有兩題我本人出的。
A. 題目問的是給了M個立方體箱子，能放進N個預定大小的箱子中體積最小的哪個。明顯地只需要把所有箱子按三維坐標排序測試即可。
B. 問一個圓心在原點，半徑為N的圓形，當中覆蓋了多少個整數點。留意普通枚舉不可行。亦可以留意對稱性之下只需求一個象限的答案(不包含縱橫軸以免造成覆算)。在一個象限的答案可以依坐標(N-1, 1) 開始不斷求算直至某點(N-1 - \delta_x, 1)在圓內，然後以(N - 1 - \delta_x, 2) 開始重新計算，直至移動到y = N為止。假設該象限有K個點在圓內，則答案是4(K + N) + 1。
C. 給了N個整數的數列A，並且給定了K個區間，分為是[a_1, b_1], \cdots [a_K, b_K]，問每個區間之下求\max_{i \in [a_i, b_i]}A_i。另外，不存在a_i < a_j \le b_j < b_i，而且a_i必定按遞升次序。直觀的做法當然是可以用線段樹，但就沒有利用到最後給定的條件。留意重新理解這個條件的話，便可以知道，只需按在相同a_i的值下按b_i重新排序(簡單的counting sort即可)其實必定保証了當按左至右查找答案時，第i個詢問完成等價於任何第j < i個詢問也必定完成。這是RMQ的特例，稱為Sliding RMQ。根據這種特性其實用Monotone Deque即可完成本題。時間複雜度是O(N)。
D. 問一條二元字串s經過最少多少次修改後變成反對稱。修改包括「增、刪、換」，反對稱則是指字串倒轉寫後每個字元與倒轉前不一樣。一道經典動態規劃題。假設f(x, y)是對原字串第x至y位作修改後，最少需要多少次修改才成為反對稱字串。則有如下狀態轉移方程﹕
f(x, y) = \begin{cases} 0 & \text{if } x > y .\\ 1 & \text{if } x = y .\\ f(x+1, y-1) & \text{if }s_x = s_y .\\ \min\{f(x+1, y), f(x, y-1), f(x+1, y-1)\} + 1 & \text{otherwise.}\\ \end{cases}
答案是f(0, N-1)。時間複雜度則是O(N^2)。
