表現差強人意，希望下次能再做得好點 :-)
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…總之應該很快就是。
2012年5月11日 星期五
2012年5月9日 星期三
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)$依賴自身狀態的情況？
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*}$
另外，我們亦可以憑如下關係得到同樣答案﹕
$\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*}$
訂閱：
文章 (Atom)
