應該是第一次寫這種不公開的比賽的貼文吧。
今次比賽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)$。
