上次腦殘之後，人品突然挺好的…
A: 問每個參賽者的答題的分數，成功及失敗的挑戰，問比賽的贏家是誰。保証只有一個贏家。極點頹題。
B: 捉迷藏遊戲。查票員會從火車的頭卡至尾卡不斷的來回檢查，每個時刻只會移動一個車廂。逃票人則在火車移動的時候選擇留守同一車廂，或向附近一車廂移動。如果火車停站了，他可以先行離開車廂，並能進入任意一個車廂，假設這個步驟是不看耗時的。現在給了查票員和逃票人的最初位置，和查票員的行走方向，並保証最後一個時刻是終點站，問給定每個時刻火車是到站還是行走中，逃票人能否不被查票員逮著？即使一定被逮到，最遲必定在甚麼時候被逮著？其實處理上有點麻煩的，對於火車移動的時刻，逃票人的移動有最多3個選擇，並且對查票員的前後移動跟逃票人的距離進行排序，然後往最遠距離的一點移動。如果該距離只能是0的話則會被抓。對於火車停站的時刻，逃票人永遠可以躲在查票員背對的盡頭的車廂，當然，若查票員已站在頭卡或尾卡，則必須站在該對面盡頭即可。寫的時候人品超好，一次就寫對了…
C: 問一個 $N \times M$ 的板，問有多少條不同的桌球的彈道。球的移動遵從45度的斜線運動，碰壁的話會改變方向。卡了很久沒能找到 $O(1)$ 算式…至放棄時想想不如直接寫程序計算一些數值再想想，但之前已經想到一件事﹕彈道必先會經過第一行的其中一個格子。寫的時候想到不用逐步移動，直接可以算出碰在那了。然後在第一行的起點經過剛好3次就能保証遍歷一條完整的彈道。跑的時候跟手算答案一致，無聊試試最大的情況 $N = M = 10^6$ ，竟然不消半晌就跑出答案了﹗後來猛然醒起寫的時候那個直接算出碰撞點可以讓算法變得很高效的…直接提交並通過了。早知一早放棄手寫，然後寫程序找答案還來得有效。後來看tourist的答案… $\text{gcd}(N-1, M-1)+1$ …徹底輸了。
D, E: 待補
2011年4月17日 星期日
Codeforces Round #67
本人極其腦殘的一次比賽，幸好不算rating，否則糟榚。
A: 問兩整數 $A,B$ 把零除去後，其和是否等於 $A+B$ 把零除去的值。頹。
B: 有一社交網站(名字…你懂的)，有三項動作﹕(1)X在Y的留言板上留言 (+15分) (2)X在Y的貼文內留言 (+10分) (3)X讚Y的post。你知道你名字和一系列的動作，每項動作將會替X和Y添加括號內所述的分數。問對於你來說，跟你互動而分數最多至最少的的人的排序是怎樣。即使沒跟你互動都要顯示出來。我錯了幾次是因為沒看到分數是相對於自己…
C: $Q$ 次詢問，每次問區間 $[a, b]$ 內 $\text{gcd}(X, Y)$ 最大的因數。腦殘的爆發點，明明 $O(Q\sqrt{\text{gcd}(X, Y)})$ 可以搞定，我卻寫了質素因數分解，二分找答案…當然是趕急的寫，最後也過不了…
D: 有 $N$ 個小數組，現有 $M$ 個標號，把各標號對應的數組接了起來，問其最大連續子序列和最大是多少。又一腦殘點，漏了個很容易考慮到的情況。首先對每個小數組，求出其左連接最大和，數組和，及右連接最大和。那麼對每標號則考當前和加上數組和是否單調上升。若是則加上數組和並繼續，否則應先更近答案，皆因當前數值可至少加上該標號的左連接最大和使得更大但沒法再向右繼續；之後應從甚麼數開始再繼續？答案就是數組和或右連接最大和之間的最大值。但是注意，每次輸入一個新標號之後，其小數組的最大連續子序列和可能就是唯一答案，必須同時預先比對答案和其數值。我漏了處理這個，連pretest都過不了。
E: 待補。
A: 問兩整數 $A,B$ 把零除去後，其和是否等於 $A+B$ 把零除去的值。頹。
B: 有一社交網站(名字…你懂的)，有三項動作﹕(1)X在Y的留言板上留言 (+15分) (2)X在Y的貼文內留言 (+10分) (3)X讚Y的post。你知道你名字和一系列的動作，每項動作將會替X和Y添加括號內所述的分數。問對於你來說，跟你互動而分數最多至最少的的人的排序是怎樣。即使沒跟你互動都要顯示出來。我錯了幾次是因為沒看到分數是相對於自己…
C: $Q$ 次詢問，每次問區間 $[a, b]$ 內 $\text{gcd}(X, Y)$ 最大的因數。腦殘的爆發點，明明 $O(Q\sqrt{\text{gcd}(X, Y)})$ 可以搞定，我卻寫了質素因數分解，二分找答案…當然是趕急的寫，最後也過不了…
D: 有 $N$ 個小數組，現有 $M$ 個標號，把各標號對應的數組接了起來，問其最大連續子序列和最大是多少。又一腦殘點，漏了個很容易考慮到的情況。首先對每個小數組，求出其左連接最大和，數組和，及右連接最大和。那麼對每標號則考當前和加上數組和是否單調上升。若是則加上數組和並繼續，否則應先更近答案，皆因當前數值可至少加上該標號的左連接最大和使得更大但沒法再向右繼續；之後應從甚麼數開始再繼續？答案就是數組和或右連接最大和之間的最大值。但是注意，每次輸入一個新標號之後，其小數組的最大連續子序列和可能就是唯一答案，必須同時預先比對答案和其數值。我漏了處理這個，連pretest都過不了。
E: 待補。
Codeforces #73 D FreeDiv
題意﹕給了 $N$ 個點，現在接了 $M$ 條藍色邊，一個由藍色邊接成的連通塊稱作藍色領域。現在你可以添加紅色邊使得所有藍色領域都連通起來，但是有限制﹕(1)每點只能接上最多一條紅色邊。(2)每個藍色領域不能接上超過 $k$ 條紅色邊。
根據這個限制，有可能沒法添加紅色邊使得所有藍色領域都連通起來。現問至少需添加多少條藍色邊使得能達成要求？
首先，我們若把所有藍色領域縮成一點，每點標號為 $\min(k, b_i)$ ，當中 $b_i$ 為第 $i$ 個藍色領域的點數。那麼其標號即為限制讓人藍色領域最多可外接多少條紅色邊。現在問題可看成兩種操作﹕
(1) 添加藍邊連接領域 $u$ 和 $v$ 。那麼新的點 $w$ 即可看作新的藍色領域，標號為 $\min(b_u+b_v, k)$ 。
(2) 添加紅邊連接領域 $u$ 和 $v$ 。那麼新的點 $w$ 即可看作新的藍色領域，標號為 $(b_u+b_v - 2)$ 。
假定不允許操作(1)(即添加藍色邊)，甚麼時候會不能滿足問題條件？明顯是存在兩個點 $u, v$ 使得 $b_u=b_v=1$ 並只能為這兩點進行操作(2)。甚麼時候可以盡量防止這情況發生？留意當 $b_u, b_v \ge 2$ 操作(2)只會製造一個新點 $w$ 使得 $b_w \ge \max(b_u, b_v)$ ，故不會導致失敗。那麼可以先為標號從大到小排序，順著標號進行操作(2)即可，只要當中有標號少於零的即當作失敗。
如果允許操作(1)，怎樣可以把操作(1)的數量最少又使得條件滿足？可用二分搜索答案。假設你只允許進行操作(1) $p$ 次，你會怎樣進行操作(1)使得用上段的方法添加紅邊後條件滿足？不難留意上段說明失敗的情況只有標號為1的點太多的時候才會發生。要避免這個情況，可以考慮每次把兩個標號為1的點用操作(1)連起來，成為一個標號為 $2$ 的點。再由上段可知，它和標號大於2的點添加紅邊，不會出現失敗情況；它杏標號為1的點添加紅邊，會變成只有一個標號為1的點。故把兩兩標號為1的點用藍邊連接最能防止失敗的情況。
我寫的時候用了STL的priority_queue，結果超時(5秒都超…)。改用STL的make_heap之後剛好4.5秒通過了…另，我認為可以不用二分，直接可以算出應最少用多少次操作(1)。
根據這個限制，有可能沒法添加紅色邊使得所有藍色領域都連通起來。現問至少需添加多少條藍色邊使得能達成要求？
首先，我們若把所有藍色領域縮成一點，每點標號為 $\min(k, b_i)$ ，當中 $b_i$ 為第 $i$ 個藍色領域的點數。那麼其標號即為限制讓人藍色領域最多可外接多少條紅色邊。現在問題可看成兩種操作﹕
(1) 添加藍邊連接領域 $u$ 和 $v$ 。那麼新的點 $w$ 即可看作新的藍色領域，標號為 $\min(b_u+b_v, k)$ 。
(2) 添加紅邊連接領域 $u$ 和 $v$ 。那麼新的點 $w$ 即可看作新的藍色領域，標號為 $(b_u+b_v - 2)$ 。
假定不允許操作(1)(即添加藍色邊)，甚麼時候會不能滿足問題條件？明顯是存在兩個點 $u, v$ 使得 $b_u=b_v=1$ 並只能為這兩點進行操作(2)。甚麼時候可以盡量防止這情況發生？留意當 $b_u, b_v \ge 2$ 操作(2)只會製造一個新點 $w$ 使得 $b_w \ge \max(b_u, b_v)$ ，故不會導致失敗。那麼可以先為標號從大到小排序，順著標號進行操作(2)即可，只要當中有標號少於零的即當作失敗。
如果允許操作(1)，怎樣可以把操作(1)的數量最少又使得條件滿足？可用二分搜索答案。假設你只允許進行操作(1) $p$ 次，你會怎樣進行操作(1)使得用上段的方法添加紅邊後條件滿足？不難留意上段說明失敗的情況只有標號為1的點太多的時候才會發生。要避免這個情況，可以考慮每次把兩個標號為1的點用操作(1)連起來，成為一個標號為 $2$ 的點。再由上段可知，它和標號大於2的點添加紅邊，不會出現失敗情況；它杏標號為1的點添加紅邊，會變成只有一個標號為1的點。故把兩兩標號為1的點用藍邊連接最能防止失敗的情況。
我寫的時候用了STL的priority_queue，結果超時(5秒都超…)。改用STL的make_heap之後剛好4.5秒通過了…另，我認為可以不用二分，直接可以算出應最少用多少次操作(1)。
2011年4月7日 星期四
Codeforces #62 D Wormhouse
題意﹕現有一個 $N$ 點的歐拉迴路的遍歷，這遍歷包含 $M$ 條邊。詢問字典序的下一個大的遍歷。可以不存在，圖亦可以不連通。 $3 \le N \le 100, 3 \le M \le 2000$ 。
做法是比較直接的。枚舉迴路的前綴，假設前綴的末點是 $u$ ，本來的下一遍歷點是 $v$ ，則在此刻嘗試找迴路的時候，嘗試的點應至少由 $v+1$ 開始。其餘時候則保持從最小標號點開始。然後直接比較路徑(如有)即可。
做法是比較直接的。枚舉迴路的前綴，假設前綴的末點是 $u$ ，本來的下一遍歷點是 $v$ ，則在此刻嘗試找迴路的時候，嘗試的點應至少由 $v+1$ 開始。其餘時候則保持從最小標號點開始。然後直接比較路徑(如有)即可。
2011年4月6日 星期三
Codeforces #12 D Ball
問題非常簡短﹕給了 $N$ 個三維空間的點，問有多少個點 $i$ 使得存在點 $j$ 令 $x_i < x_j, y_i < y_j, z_i < z_j$ 。 $1 \le N \le 500000$ ， $0 \le x_i, y_i, z_i \le 10^9$ 。
其實做法非常經典，屬練習題程度，可是我比較笨，老是想不出正確的方法。
為 $x_i$ 排序，然後把 $y_i$ 離散化。按 $x_i$ 從大至小遍歷，則問題等價於找出 $y_i < y_j$ 並且 $z_i < z_j$ 。再把問題重新看一下則是尋找 $\max_{j: y_i < y_j}\{z_j\}$ 。因 $y_i$ 已離散化則不妨把它看成位置，現求在點 $i$ 的情況下，範圍 $j \in [y_i+1, M]$ 內 $z_j$ 的最大值，當中 $M$ 是指 $y_i$ 有多少個不同的數值(即離散化後的最大值)。如此一來即是求範圍內最大值，線段樹秒殺之。
注意題目要求的是 $x_i < x_j$ 。遍歷 $x_i$ 值從大至小的時候要把相同的 $x_i$ 值暫緩更新，否則會出錯。附一樣例作例子。
其實做法非常經典，屬練習題程度，可是我比較笨，老是想不出正確的方法。
為 $x_i$ 排序，然後把 $y_i$ 離散化。按 $x_i$ 從大至小遍歷，則問題等價於找出 $y_i < y_j$ 並且 $z_i < z_j$ 。再把問題重新看一下則是尋找 $\max_{j: y_i < y_j}\{z_j\}$ 。因 $y_i$ 已離散化則不妨把它看成位置，現求在點 $i$ 的情況下，範圍 $j \in [y_i+1, M]$ 內 $z_j$ 的最大值，當中 $M$ 是指 $y_i$ 有多少個不同的數值(即離散化後的最大值)。如此一來即是求範圍內最大值，線段樹秒殺之。
注意題目要求的是 $x_i < x_j$ 。遍歷 $x_i$ 值從大至小的時候要把相同的 $x_i$ 值暫緩更新，否則會出錯。附一樣例作例子。
3
0 0 0
0 0 1
0 0 1
2011年4月2日 星期六
Codeforces #27 D Ring Road 2
題意﹕給了一個帶 $N$ 個頂點的環 $C_N$ ，現在要添加 $M$ 條邊，你可以把邊畫在環內，或是環外，但必須使得每條邊之間都不能相交(在末端相交除外)。問是否存在一個決定邊的畫法使得條件達成。保証邊連接不同的頂點，沒重邊。
最初有一個很直觀的想法﹕假設邊是 $e = (x, y)$ 且 $x < y$ ，設 $A_e = \{i: x < i < y\}$ ， $B_e = \{1 \cdots N\} - A_e - \{x, y\}$ ，則 $e$ 會把頂點集分開兩半，使得任意邊 $e' = (x', y'), x' \in A_e, y' \in B_e$ 必不能與 $e$ 有相同的畫法。我們稱 $e$ 和 $e'$ 是互斥的。
可惜之後有一個錯的想法。以為順著輸入每條邊，都更新使得互斥的點對的可用的畫法，如遇上某一點對沒有可用的畫法則判無解。這個算法是錯的，只是我未找到反例。
然後有另一個想法，就是基於兩個互斥的點對必須有不同的畫法。可以立刻聯想到的是若把點對看作一個頂點，互斥點對添加一條邊，則此構造圖 $G$ 有解若且僅若 $G$ 是二分的(即可以用兩種顏色為頂點著色)。這就是正確的解。
順帶一提，本題要求的添加邊使得解是一平面圖，但必須基於 $C_N$ 底下該圖仍是平面的。所以不用想平面圖測試的算法了。
最初有一個很直觀的想法﹕假設邊是 $e = (x, y)$ 且 $x < y$ ，設 $A_e = \{i: x < i < y\}$ ， $B_e = \{1 \cdots N\} - A_e - \{x, y\}$ ，則 $e$ 會把頂點集分開兩半，使得任意邊 $e' = (x', y'), x' \in A_e, y' \in B_e$ 必不能與 $e$ 有相同的畫法。我們稱 $e$ 和 $e'$ 是互斥的。
可惜之後有一個錯的想法。以為順著輸入每條邊，都更新使得互斥的點對的可用的畫法，如遇上某一點對沒有可用的畫法則判無解。這個算法是錯的，只是我未找到反例。
然後有另一個想法，就是基於兩個互斥的點對必須有不同的畫法。可以立刻聯想到的是若把點對看作一個頂點，互斥點對添加一條邊，則此構造圖 $G$ 有解若且僅若 $G$ 是二分的(即可以用兩種顏色為頂點著色)。這就是正確的解。
順帶一提，本題要求的添加邊使得解是一平面圖，但必須基於 $C_N$ 底下該圖仍是平面的。所以不用想平面圖測試的算法了。
2011年4月1日 星期五
Codeforces #56 E Domino Principle
題意﹕給定 $N$ 個多米諾/骨牌，每個骨牌皆有不同的位置 $X_1 \cdots X_N$ 和高度 $H_1 \cdots H_N$ 。若推倒第 $i$ 個骨牌則 $X_i+1$ 至 $X_i+H_i-1$ 以內的所有骨牌皆會倒下。問每塊骨牌可推倒多少個骨牌(包括自己)。 $1 \le N \le 10^5$ , $-10^8 \le X_i \le 10^8$ 和 $2 \le H_i \le 10^8$ 。
做法當然不能 $O(N^2)$ 枚舉吧。不過先假設 $X_1 < X_2 \cdots < X_N$ ，定義要求答案為 $f_i$ 。設 $c_i = j$ 使得 $X_i + H_i - 1 \le X_j, j > i$ ，即第 $i$ 個骨牌可以接觸到最遠哪個骨牌，如果遇上任何不能推倒的骨牌則表示為 $c_i = \infty$ 。則 $f_i$ 有如下關係﹕
\[ f_i = \begin{cases} \max_{i+1\le k\le c_i}\{f_k + k - i\} & \text{if } c_i \ne \infty \\ 1 & \text{otherwise} \end{cases}\]
首先，對於任意 $i$ ，查找 $c_i$ 的方法可以用二分搜索。至於計算 $f_i$ ，我們考慮 $c_i \ne \infty$ 的情況。經簡化可得
\[ f_i = \max_{i+1\le k\le c_i}\{f_k + k - i\} = \max_{i+1\le k\le c_i}\{f_k + k\} - i\]
設 $g_k = f_k + k$ 。即，我們從範圍 $i+1$ 至 $c_i$ 之間搜索最大的 $g_k$ 值，這就可以用線段樹輕鬆搞定了。算好 $f_i = \max_k\{g_k\} - i$ 後記得為線段樹的區間 $[i, i]$ 插入數值 $g_i = f_i + i$ 。
說來湊巧，最近與Gagguy聊天起他提起類似問題的做法，之後再做題就剛好遇上此題，所以推導公式還是比較便捷，在此先行感謝Gagguy指點。
做法當然不能 $O(N^2)$ 枚舉吧。不過先假設 $X_1 < X_2 \cdots < X_N$ ，定義要求答案為 $f_i$ 。設 $c_i = j$ 使得 $X_i + H_i - 1 \le X_j, j > i$ ，即第 $i$ 個骨牌可以接觸到最遠哪個骨牌，如果遇上任何不能推倒的骨牌則表示為 $c_i = \infty$ 。則 $f_i$ 有如下關係﹕
\[ f_i = \begin{cases} \max_{i+1\le k\le c_i}\{f_k + k - i\} & \text{if } c_i \ne \infty \\ 1 & \text{otherwise} \end{cases}\]
首先，對於任意 $i$ ，查找 $c_i$ 的方法可以用二分搜索。至於計算 $f_i$ ，我們考慮 $c_i \ne \infty$ 的情況。經簡化可得
\[ f_i = \max_{i+1\le k\le c_i}\{f_k + k - i\} = \max_{i+1\le k\le c_i}\{f_k + k\} - i\]
設 $g_k = f_k + k$ 。即，我們從範圍 $i+1$ 至 $c_i$ 之間搜索最大的 $g_k$ 值，這就可以用線段樹輕鬆搞定了。算好 $f_i = \max_k\{g_k\} - i$ 後記得為線段樹的區間 $[i, i]$ 插入數值 $g_i = f_i + i$ 。
說來湊巧，最近與Gagguy聊天起他提起類似問題的做法，之後再做題就剛好遇上此題，所以推導公式還是比較便捷，在此先行感謝Gagguy指點。
訂閱：
文章 (Atom)
