Codeforces Round #119 (Div 1) A~C

表現差強人意，希望下次能再做得好點 :-)

A: 給了兩個$1\cdots N$的排列，對於任意一個排列，可以取出最右邊的數字並可以放在餘下數字中任意位置(除了不能原封不動)。問最少需要多少次操作才能把排列$A$變成排列$B$。良久後才發現如果$A_1, A_2, \cdots, A_p$的相對次序在$B$中並沒有改變，則只需要把剩下$N-p$個數字按插其中即可。答案就是找出最大的$p$並輸出$N - p$。

B: 給了$M$種車輛，並且給了第$i$輛車在一個$N$個城市之間的行走時間。現有$R$場賽事，每場賽事表示要從$s$城到$t$城的最短路，而且只能允許中途轉換最多$K$次車輛。

基本上我看漏了很多東西…首先，$R \le 10^5$，表明最短路需要預計算。其次，$K \le 1000, N \le 60$其實不太可能轉車$1000$次吧？即是其實$K$最多只有$N-1$而已。知道後其實題目是在層圖上做所有點對的最短路。首先固定一種車輛求最短路，然後迭代$N-1$次在層圖上再做Floyd-Warshall即可。

C: 題目給了$N$點及$M$條路，然後在$K$個不同的點上皆放了指示牌。每個指示牌只能顯示長度$q$的路線，問從$s$到$t$，$q$最少是甚麼？保証點$s$一定有路牌。

首先想到的是二分找$q$吧。不過固定了$q$，怎樣才能判斷$s$可以到達$t$？這問題好像和為網絡封包找最少的ttl差不多。不過想到的是直接用BFS，然後記下通過一點時還餘多少步。這樣一來好像跟Shortest Path沒分別，而且狀態一共有$O(Nq)=O(N^2)$個，好像不行。提交時也不能過pretest，以為算法錯了。怎料事後發現自己初始餘下步數的數組為$0$，即是剛好剩一步便到終點的話便沒法更新，改了初始值是$-1$後便AC了。到現在我沒法証明這算法的Worst case complexity…總之應該很快就是。

Topcoder SRM 542 Div 1 Easy + Medium

Easy: 題意非常簡單，給定$X\times Y$的格網，問多少三角形$\triangle ABC$使得以下條件成立。

1) $A, B, C$的縱座標必須各不相同。
2) $A, B, C$的橫座標必須各不相同。
3) $\triangle ABC$的邊長必須介乎$T_\min$與$T_\max$之間。

任意兩點$(X_1, Y_1), (X_2, Y_2)$的距離定義取曼哈頓距離，即$|X_1-X_2| + |Y_1-Y_2|$。

已知$X, Y \le 4000$，$2 \le T_\min \le T_\max \le 20000$，求有多少個符合條件的三角形並取除$1000000007$的餘數。

利用窮舉肯定不可行，$O(X^3Y^3)$無望。從題目特質入手。條件(1)和(2)似乎沒有甚麼特別，似乎保証三角形必定是proper triangle，但卻沒有把題目變得更容易。條件(3)好像也沒有特別作用，但如果定義$F(k)$為三角形的數量使得長度最多為$k$，則在可以著手求$F(T_\max) - F(T_{\min-1})$。不過題目依舊沒有容易很多。

唯一著眼點是曼哈頓距離。可以得出任意三角形在曼哈頓距離的情況下必如下圖﹕

其周界即相等於平行縱橫軸的最小包含長方形周界，長度為$2(\Delta_x + \Delta_y)$。由此可知我們其實想求所有可行的$\Delta_x$和$\Delta_y$使得
$$T_\min \le 2(\Delta_x+\Delta_y) \le T_\max$$
即表明我們毋需枚舉三點，只需枚舉$\Delta_x$及$\Delta_y$即可，當中$\Delta_x$及$\Delta_y$包含的三角形數即屬答案一部分。

那麼顯而易見對於$\Delta_x$($\Delta_y$亦然)，必須有兩點的橫座標相隔$\Delta_x$，第三點則任意取其中間的點。而根據橫座標最多$X$點，則$\Delta_x$的長度有$X-\Delta_x$種取法，第三點則有$\Delta_x-1$種取法，因此符合條件的所有橫向座標有$(X-\Delta_x)(\Delta_x-1)$種。同埋縱向座標有$(Y-\Delta_y)(\Delta_y-1)$種。

可能你會覺得奇怪，為何分開縱橫軸計算？看如下圖片便知﹕

只要我們知道縱軸三點和橫軸三點，則可以構造$6$個不同的三角形。因此，對於$\Delta_x$及$\Delta_y$，只要符合條件(3)，一共有$6(X-\Delta_x)(\Delta_x-1)(Y-\Delta_y)(\Delta_y-1)$個三角形。

因此本題能在$O(XY)$時間計算答案
$$\sum_{\Delta_x=2}^{X-1}\sum_{\stackrel{\Delta_y=2}{T_\min \le \Delta_x+\Delta_y \le T\max}}^{Y-1} 6(X-\Delta_x)(\Delta_x-1)(Y-\Delta_y)(\Delta_y-1) \bmod{1000000007}$$

Medium: 給了$N$個長度恰好為$L$且互不相同的字串，以均等機會隨機取一任意固定排列，然後為字串依排列重組，並為$N$個字串排序，問每個字串排首位的概率是多少。$1 \le N \le 16$，擺明是Exponential Time動態規劃吧。不妨設$F(B, i)$表示以集合$B$內的字串$s_i$經排序後排首位的概率。可以知道對於$s_i \not\in B, F(B, i) = 0$，而且$F(\{s_i\}, i) = 1$。由於字串互不相等，因此必定存在位罝$p$使得存在$i, j$並且$s_{ip} > s_{jp}$，即存在$s_{ip}$不可能再成為首位。假設$B'$包含了該種字串，枚舉$L$個字串位置後有$K$個可排除集合$B'_1, B'_2 \cdots B'_K$，因此得遞迴公式
$$F(B, i) = \frac{1}{K}\sum_{B' = B'_1, \cdots B'_K}F(B-B', i)$$

並可於$O(2^NL)$計算答案$\{F(S, 1), F(S, 2), \cdots F(S, N)\}$，其中$S = \{s_1, \cdots s_N\}$。

有一個小問題﹕為何不用考慮排除集合為空集的的情況？如果考慮了後則會有$F(B, i)$依賴自身狀態的情況？

答案﹕Principle of Deferred Decision。

另外，我們亦可以憑如下關係得到同樣答案﹕
$\begin{align*} F(B, i) &= \frac{1}{L}\sum_{B'}F(B-B', i)\\ F(B, i) &= \frac{1}{L}\sum_{\stackrel{B'}{B'\ne \emptyset}}F(B-B', i) + \frac{1}{L}\sum_{\stackrel{B''}{B''= \emptyset}}F(B-B'', i)\\ F(B, i) &= \frac{1}{L}\sum_{\stackrel{B'}{B'\ne \emptyset}}F(B-B', i) + \frac{L-K}{L}F(B, i)\\ \frac{K}{L}F(B, i) &= \frac{1}{L}\sum_{\stackrel{B'}{B'\ne \emptyset}}F(B-B', i)\\ F(B, i) &= \frac{1}{K}\sum_{\stackrel{B'}{B'\ne \emptyset}}F(B-B', i)\\ \end{align*}$

PCOI CCC 2012 Warm up contest

是次比賽共五題，亦是當年小弟第一次參賽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)。

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)$。

SRM 508 Div1 Easy + Medium

Easy: 給了一個正整數$N$和最初放在第$M$格的物件，你可作如下操作﹕

(1) 把$N$除以其任意一個質因數$p$，並捨棄其他不包含該物件的區間。
(2) 把格子向左或右旋轉一下。

目標是要把物件放在第一格。問最少需要多少步才可。

首先一定要把$N$進行質因數分解。另外需要留意的是，兩個操順序後並無一定關係。可以考慮先處理(2)再處理(1)之前，把$N/p$個等分疊在一起，其結果就等價於先進行(1)再進行(2)。所以可以知道答案必定是先進行若干次(也可能完全沒有)劃分，然後考慮向左或向右旋轉至第一格最划算的費用之和。另，因為$M$是以$1$開始算的，所以要處理劃分後的位置必須先把$M$變成以$0$開始才可。假設劃分後$N'=N/p$，$M'=M \bmod{N'}$。剩下來就是怎樣選取劃分了。因為$N \le 1000000$，其互不相同的質因數最多只有$8$個，因此可以考慮枚舉$8!$的劃分順序。

Medium: 給了$N$個正整數$R_1\cdots R_n$，求有多少數數列$A_1\cdots A_n$使得

(1) $\sum_{i=1}^n A_i = A_1 | A_2 \cdots | A_n$。
(2) $A_i \le R_i$。

答案取模$10^9+9$。$1 \le R_i \le 10^{18}$，$1 \le N \le 10$。

很難的題目。但$N$不大應該可以有一些牽涉$2^N$的動態規劃。未決定狀態之前，首先第條件(1)要求$A_i$必須不能在某一個二進位有多於一個$1$，而且二進位之間的關係是離散的，因此可以考慮二進位$p$為狀態之一。條件(2)限制了決定那個$A_i$的第$p$位應該取值$1$。因為如果某個$A_i$設為$1$的話可能使得$A_i > R_i$；但只要某些條件下不論$A_i$的第$p$位取值多少都不影響條件(2)。例如$R_i = 10101001_{(2)}, A_i = 101*...._{(2)}$，$*$只可以放$0$，否則會違反了條件(2)。但若$R_i = 10101001_{(2)}, A_i = 100*...._{(2)}$，$*$可以取任意值而不影響條件(2)。廣義一點來說，舉凡$A_i$在$p$位以左是$R_i$的前綴的話，則$A_i$在第$p$位的取值必須受$R_i$的$p$位影響，否則可取任意值。這首先說明了兩件事。第一是$p$必須從左至右有依賴性，第二是可以引入一種狀態，標示有多少個$A_i$是不再符合前綴條件。因為$N \le 10$，這個狀態可以用$2^N$來表示。因此便有$f(p, b)$，算出有多少個可行的方案，使得$p$位以左的二進位都符合條件，並且$b$表示了所有不符合$R_i$的集合。注意為方便，我把位元的算法是以$1$為開始的。已知對所有$b$，$f(0, b) = 1$，因為$p = 0$表示決定$A_i$取值的程序已經完成了。否則，其狀態轉移方程如下﹕
$$f(p, b) = f(p-1, b') + \sum_{i=1}^N v_i \times f(p-1, b_i'')$$

其中$b'$是代表在$p$位取$0$的情況下，有多少原本還是前綴的$A_i$現在已經不是了，並加入到$b$之中。
$b''_i$則是決定把$A_i$的$p$位取值為$1$，並根據計算$b'$的方法重新計算$b''_i$有些不再是前綴(留意有些必須前綴的數因為第$p$位的$1$被$A_i$佔用了，所以必須在其第$p$位放置$0$並不再是前綴)。有時候$A_i$是前綴並且$R_i$的$p$位是$0$，因此它不能取值$1$，所以不能把$f(p-1, b_i'')$算進去的，因此$v_i = 0$，其餘情況下都是$v_i = 1$。因此本題可以在$O(2^N\times N^2M)$時間內解決，其中$M$表示最長有多少位元。因為$R_i \le 10^{18}$，因此$M \le 60$。

SRM 509 Div1 Easy + Medium

Easy: 給了一個不帶零的正整數$N$，可任意刪除數位(不能全部刪除、也可以不刪)但保持其原來次序，可得一集合$\mathcal{S}$。求$\sum_{i \in \mathcal{S}} i \bmod{9}$。例如$N = 123$則答案是
$$123 + 12 + 13 + 23 + 1 + 2 + 3 \equiv 177 \equiv 6 \pmod{9}$$
首先求取模$9$的意義。從上式可知
$$123 \equiv 1 + 2 + 3\pmod{9}$$
因此其實是問所有數位出現多少次，求和並取模。不難從例子發現，若$N$是一$L$位整數，則每個數位會出現$2^{L-1}$次。設$d(N)$是$N$的數位之和，則答案顯然是 $$d(N)\times 2^{L-1} \bmod{9}$$
注意$2^{L-1}$可以超越整數範圍。

Medium: 給了一個字串$S$，並只給了幾種特定的操作，其操作形式只有三種。
(1) 在字串內刪除其中一個為$a$的字元，費用為$w_1$。
(2) 在字串內把其中一個為$a$的字元變成$b$，費用為$w_2$。
(3) 在字串加上一個為$a$的字元(可以在字串前後加上)，費用為$w_3$。

現給予$R$種互不相同的操作，問把$S$變成迴文的最少費用。

處理這類字串成問題通常是考慮動態規劃狀態$F(x, y)$，即最少把子字串$S_{x\cdots y-1}$修改成迴文的最小費用。

先考慮簡化版問題﹕允許任意操作，並且一律費用為$1$。那麼其狀態轉移方程可以簡單描述成
$$F(x, y) = \begin{cases} 0 & \text{if $y-x \le 1$} \\ F(x+1, y-1) & \text{if $S_x = S_{y-1}$} \\ \min(F(x+1, y), F(x, y-1)) + 1 & \text{otherwise}\end{cases}$$
但套在這道問題又是否可行呢？首先留意到並非任意操作都可行，所以狀態方程必須因應對應字元而再設計。其次是任意操作的費用不再單純是$1$，意味著若把上述方程的費用$1$寫成通用的$W_{S_x,S_y}$，那麼其意義不只限於單次操作使得$S_x$和$S_y$匹配，而是可以經過一系列操作令$W_{S_x,S_y}$最少化。先考慮$C_{a,b}$，即最少費用把字元$a$修改成字元$b$，然後$W_{a,b}$則可經如下公式求得
$$W_{a,b} = \min_{c}\{C_{a,c} + C_{b,c}\}$$
這引伸了另一個問題﹕如何求$C_{a,b}$？可以想像到的是最短路算法。但首先留意求算需要周全考慮所有操作﹕如果只考慮改變字元的話是不夠的，因為可能最小費用操作可以循這種方式獲得﹕修改$\rightarrow$刪除$\rightarrow$加入$\rightarrow$修改。可見刪除和加入這兩種一般難以用最短路方式描述的操作是可以出現在最小費用操作的任意位置中。解決這個問題的一種思路是﹕何不可以把這兩種操作歸約成修改操作？留意兩種操作可以這樣看的﹕
(1)刪除﹕把字元$a$修改成字元$\emptyset$。
(1)加入﹕把字元$\emptyset$修改成字元$a$。
因此我們只需把空字元$\emptyset$列為可考慮修改字元的話，那麼$C_{a,b}$即可以用最短路
$$C_{a,b} = \min_{c \in \{\text{`a', `b', $\cdots$ `z', $\emptyset$}\}}\{C_{a,c} + C_{c, b}\}$$
求得，因此亦得到$W_{a,b}$。現在重新考慮狀態轉移方程，留意因為費用不再全部都是$1$的關係，因此我們把簡化版的方程的$S_x = S_y$情況一併歸約至一般情況之中，即可得解決本題的方程，如下﹕
$$F(x, y) = \begin{cases} 0 & \text{if $y-x \le 1$} \\ \min(F(x+1, y), F(x, y-1)) + W_{S_x,S_y} & \text{otherwise}\end{cases}$$

SRM 512 Div1 Easy + Medium

因為這次SRM是$2$的冪，所以題目分數也別出心裁的改為$2$的冪。

Easy: 假設某餐店只開$N$日，每日也賣出$M$款菜式。每日每款菜式的價格都有所不同。這餐廳有點古怪，要求你必須一天只買一款菜式；第$i$天買了第$j$款菜式的話必須在$i+7$天買第$j$款菜式；一旦你在第$i$天沒有光顧的話以後都不可以光顧該餐廳。你有$K$元在手，問最多能光顧這餐廳多少天。

算是比較容易的題。首先問題可以轉化為：能不能連續光顧$k$天？設這函數是$f(k)$的話我們就是求最大的$k$使得$f(k) = true$。當然由於$k$很小，線性枚舉所有$f(k)$即可。那麼判斷答案實在是很容易的–設$v_{i, j}^k$是在這連續$k$天內每星期$i$都買菜式$j$的總支出。判斷$f(k)$則只需檢查 $$\sum_{i=1}^7 \min_{1\le j\le M}v_{i,j}^k \le K$$ 即可。

Medium: 一個泛費波那契數列是指任意正整數$f_0, f_1$為數列的首兩個元素，並且其數列遵從遞迴式$f_k = f_{k-1} + f_{k-2}, k > 1$。任何其子序列則稱為泛費波那契子數列。假設有一個正整數集$S$，當中有$N$個各不相同的整數。題目要求從$S$中取出兩個不相交的子集$A$和$B$，使得$A$和$B$皆為泛費波那契子數列，並且$A$的最大值必須少於$B$的最小值，而且$A$和$B$皆為上升序列。

乍看起來有點難。首先可以想到的是﹕能不能把$S$排序，然後劃分兩個子集$S_{1\cdots p}$、$S_{p+1\cdots N}$並分別在其中找出$A$和$B$？基於$N$不太大的關係，似乎有點可行，而且問題會簡化為從一個集合中找出最長的泛費波那契子數列。這個如何找呢？現在假設在$S$中找出$A$，可以試著想想枚舉。現在從$S$選出$S_i$和$S_j$，$i < j$，找出所在$S$中最長的泛費波那契子數列且必需包含$S_i$和$S_j$。不過包含$S_i$和$S_j$的子數列並非唯一，例如$\{1, 1, \mathbf 3, 5, \mathbf 8, 13\}$和$\{1, \mathbf 3, \mathbf 8, 11, 19\}$。但是可以留意兩件事﹕(1) $S_i$是數列的第幾個數並沒關係，只需要假定它是第一個就行；(2) 如果假定$S_j$是第$k$個數，則這個數列的存在性是唯一的，而且其唯一性是基於$S_i$之後的那個數。那麼我每只需枚舉$S_i$、$S_j$和$k$基本上憑求得序列的第二個數便可以確定序列。記得費波那契數的矩陣公式嗎？其實我們可以用同樣公式求得答案﹕
$$\begin{bmatrix}F_k \\ F_{k-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}^{k-1} \begin{bmatrix}F_1 \\ F_0\end{bmatrix}$$
其中$F_k = S_j$，$F_0=S_i$而且$F_1$就是要求的答案。假設該式寫成
$$\begin{bmatrix}S_j \\ F_{k-1} \end{bmatrix} = \begin{bmatrix} a & b \\ c & d\end{bmatrix} \begin{bmatrix}F_1 \\ S_i\end{bmatrix}$$
則可以得到
$$S_j = aF_1 + bS_i$$
然後可得$F_1 = \frac{S_j - bS_i}{a}$。於是若$F_1$有整數解，並且$F_1 > 0$，則可以憑$S_i, F_1, S_j$求得整條數列，然後利用set找出$S$內包含的所有序列元素，並從出找出最長的子序列。需留意的是不要重覆計算元素，例如$S_i = 1, S_j = 8, k = 4$(假設$k$是以$0$開始)，$F_1=1$。另外枚舉子序列時若$F_1 < S_i$，就算$F_1\in S$也不應算為答案之一，因為題目要求答案序列是上升的。
在預計算$\begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}^k$的情況下，這算法是$\tilde{O}(N^5)$的，但是也能足夠通過System test。至於$k$應該是多少？因為$S_i \le 10^8$，所以$k \le 50$足夠了。