是次比賽共五題，亦是當年小弟第一次參賽CCC的題目。
A: 沒甚麼難度，是一道小心編寫的「輸出格式」題。
B: 沒甚麼好注意的，簡單的邊界檢查題。寫的時候可以考慮一行過的寫法﹕假設橫軸長度是$c$，而位於橫軸坐標$x$需要位移$d_x$，則可以透過一道公式更新位置\[ x := max(min(x + d_x, c), 0)\]緃軸亦然。
C: 直接依據題目要求計算矩陣的張量積即可。雖然直觀算法是$O(N\prod n_i\prod m_i)$，其中第$i$個矩陣是$n_i\times m_i$，但是倒是沒有大數據…就是做。
D: 簡單點說，就是給定一個深度優先的遍歷表，求與廣度優先的遍歷下的來回時間的相差。可以肯定的是廣度優先的遍歷只受最長路影響。假設最長路是$K$，答案則是$10(N - 2K)$。注意﹕題目沒說過起點的名稱必定是Home。
E: 給定$N$個遊戲得分順序，求每場遊戲下的排名的平均數。直觀算法是$O(N^2)$，不用說肯定會超時。有三種做法。
(i) 利用平衡二叉樹進行插入及查找，可以用伸展樹，時間複雜度是$O(N\lg N)$。
(ii) 留意我們根本不用「實時」計算排名。若果按分數排序，並且為分數順道記錄其遊戲時序，則順序枚舉遊戲時查找分數比它高且時序比其要早。設符合遊戲數是$K$則其排名是$K+1$。如此一來可以用線段樹查找時序較早的遊戲數量，計得排名後把現時遊戲更新到該線段樹上。由於是Point update Range query，實際上也不是太難寫。
(iii) 同(ii)，直接用Binary Indexed Tree，兩行代碼，方便快捷。
注意輸出浮點數往往會有精度問題。例如$44.445$會有機會存成$44.4449999999\cdots$而最終再取位下輸出成$44.44$(然而希望的是得到$44.45$)。為了解決類似情況，可以考慮用「無限小數」修正並輸出。例如該浮點數是$x$則輸出$x+\epsilon$，其中$\epsilon = 10^{-9}$足夠了(記作eps = 1e-9)。
2012年2月27日 星期一
2012年2月19日 星期日
CCC 2012 PCOI-TFT
應該是第一次寫這種不公開的比賽的貼文吧。
今次比賽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)$。
今次比賽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)$。
訂閱：
文章 (Atom)
