題意是﹕給出一個N x M的棋盤，現有K個黑色的棋子(位置可以重覆)。每一回合可以選一個棋子向四個方向移動，然後對方會把棋盤的一條邊封掉。當玩家可以推一個棋子越過一條未封掉的邊為勝。問雙方用最優策略下，玩家能否勝出。
最初有幾個想法﹕
1. 永遠只選同一個棋子去移動。
2. 可移動回合有限，為2N+2M。
3. 最終棋子的終點是棋盤的任意一個角(直觀想的是這些格子需要封兩次才能防止棋子勝出)
4. 3x3的棋盤任意棋子必勝，故推測存在棋子距離邊的步數最少者少於3為必勝。
但畫出5x5的棋盤想了想也覺得任意棋子也可以勝出，但沒法証明，又不知是否有更大的可能…
故看了題解，答案果然是以棋子最少距離步少於5為勝。証明的方法還是很巧妙的。
只要到達最近的邊的距離至少是5步的話，那麼首四步會把棋盤上屬於那條邊的兩個角落的邊都封掉(總共剛好四條邊)，那麼在第五步的話最快會扺達其中一條邊，那麼只需要封住該邊，之後無論那棋子怎樣移動都把那最近的邊封掉，結論是必然是輸局。
下次一定要好好想想再拓展的情況…
2011年2月6日 星期日
2011年2月4日 星期五
Codeforces #28 B pSort
題意﹕給出一數組A[1..N]，並且A[i] = i，規定A[i]能和A[j]交換數值若且僅若|i-j| = d_i。問能否通過不限次數的交換使得最初的數組A變成目標的排列。
想了一會，其實方法也是挺簡單的﹕定義交換集G = {g_i} 使得A[g_i]能和A[g_j]交換數值。
關鍵是﹕交換集裡的元素可以組成任意排列。例如G = {1, 3, 5, 6}而數組是
1 ? 3 ? 5 6 ? ? ?
我們可以任意排列1, 3, 5, 6的位置，即可以排列成(舉例)
3 ? 5 ? 1 6 ? ? ?
因此，答案是顯然易見的﹕對於目標排列B, 該排列能夠達成若且僅若B[i]和i是屬於同一交換集G之中。
建立交換集的方法有很多，我的方法是用並查集。
想了一會，其實方法也是挺簡單的﹕定義交換集G = {g_i} 使得A[g_i]能和A[g_j]交換數值。
關鍵是﹕交換集裡的元素可以組成任意排列。例如G = {1, 3, 5, 6}而數組是
1 ? 3 ? 5 6 ? ? ?
我們可以任意排列1, 3, 5, 6的位置，即可以排列成(舉例)
3 ? 5 ? 1 6 ? ? ?
因此，答案是顯然易見的﹕對於目標排列B, 該排列能夠達成若且僅若B[i]和i是屬於同一交換集G之中。
建立交換集的方法有很多，我的方法是用並查集。
Codeforces #24 C Sequence of Points
題意是﹕給出二維點M0, A0...A(N-1), 任意Mi (i > 0) 都使得A_((i-1)%N)為Mi及M(i-1)的中點。
問Mj是甚麼，N<=10^5保証是奇數，j <= 10^18。
驟看很複雜，但不妨先重溫中點公式﹕
定理（中點公式）﹕對於兩點A及B，C是兩點的中點若且僅若C=(A+B)/2，這公式皆把三點都看成向量計算。
因此，題意說的是知道(Mi+M(i-1))/2=A((i-1)%N)，問Mj是甚麼。
把公式重寫，得出 Mi = 2A((i-1)%N) - M(i-1) 這道遞迴式。
因為取模使式子變得難分析，故先取i < N的情況。依推導，可得﹕
M0 = M0
M1 = 2A0 - M0
M2 = 2A1 - M1 = 2A1 - 2A0 + M0
M3 = 2A2 - M2 = 2A2 - 2A1 + 2A0 - M0
.
.
M(N-1) = 2A(N-2) - M0 = 2A(N-2) - 2A(N-1) + ... - 2A0 + M0
MN = 2A(N-1) - M(N-1) = 2A(N-1) - 2A(N-2) + ... + 2A0 - M0
好像沒有甚麼有用的資訊。但加入取模的情況下就有點頭緒了，且看M(N+1)﹕
M(N+1) = 2A(N%N) - MN = 2A0 - 2A(N-1) + 2A(N-2) - ... - 2A0 + M0 = - 2A(N-1) + 2A(N-2) - ... + M0
A0被抵銷了。同一道理，A0和A1也會在M(N+2)被抵銷。因此可以推導出A0, A1, ... A(N-1) 會在M(N+N)被抵銷。因此可知M(2N)數值上是和M0一樣，但會不會是-M0呢？留意上述推導的式子中，只有奇數項才會出現-M0，而2N是偶數，因此M(2N) = M0。
因此可以肯定M0...M(2N-1)是數列的循環部分，所以只需預計算M0...M(2N-1)，然後直接取M(K%2N)即可。
問Mj是甚麼，N<=10^5保証是奇數，j <= 10^18。
驟看很複雜，但不妨先重溫中點公式﹕
定理（中點公式）﹕對於兩點A及B，C是兩點的中點若且僅若C=(A+B)/2，這公式皆把三點都看成向量計算。
因此，題意說的是知道(Mi+M(i-1))/2=A((i-1)%N)，問Mj是甚麼。
把公式重寫，得出 Mi = 2A((i-1)%N) - M(i-1) 這道遞迴式。
因為取模使式子變得難分析，故先取i < N的情況。依推導，可得﹕
M0 = M0
M1 = 2A0 - M0
M2 = 2A1 - M1 = 2A1 - 2A0 + M0
M3 = 2A2 - M2 = 2A2 - 2A1 + 2A0 - M0
.
.
M(N-1) = 2A(N-2) - M0 = 2A(N-2) - 2A(N-1) + ... - 2A0 + M0
MN = 2A(N-1) - M(N-1) = 2A(N-1) - 2A(N-2) + ... + 2A0 - M0
好像沒有甚麼有用的資訊。但加入取模的情況下就有點頭緒了，且看M(N+1)﹕
M(N+1) = 2A(N%N) - MN = 2A0 - 2A(N-1) + 2A(N-2) - ... - 2A0 + M0 = - 2A(N-1) + 2A(N-2) - ... + M0
A0被抵銷了。同一道理，A0和A1也會在M(N+2)被抵銷。因此可以推導出A0, A1, ... A(N-1) 會在M(N+N)被抵銷。因此可知M(2N)數值上是和M0一樣，但會不會是-M0呢？留意上述推導的式子中，只有奇數項才會出現-M0，而2N是偶數，因此M(2N) = M0。
因此可以肯定M0...M(2N-1)是數列的循環部分，所以只需預計算M0...M(2N-1)，然後直接取M(K%2N)即可。
2011年2月3日 星期四
Codeforces #33 C Wonderful Randomized Sum
題目簡單，問的是給出一個整數陣列A，取任意一前綴各項乘-1，取任意一後綴各項乘一，問兩個操作後A的所有元素和最大是多少？前後綴長度可以為零。
我花了點時間還是做不到，故看了某blog的解題，其實方法也是用如前幾篇文章所述的Relax法去解題。
Relax﹕如果只允許取前綴的話，那麼最大和是多少？
答案是比較簡單的，只需計算 max{Sum[1..N] - 2 * Sum[1..i], Sum[1..N]}即可，注意第二個參數是代表不取任何前綴之和。留意該公式只有Sum[1..i]是有變化的，故可重寫成Sum[0..N] - min{Sum[0..i]}, 當中設A[0] = 0。故只需O(N)預計算Sum[0..i]，後取k令Sum[0..k]最小者即可。答案即 Sum[0..N] - 2 * Sum[0..k]。
那麼對於A的長度為N的答案我們可以用P[N]來紀錄，即P[N] = i。
Observation 1﹕ P[i] <= P[i+1]。
這是我們取P[N]的時候的by-product而已，同樣可以看作把Relax問題放到A[1..i]然後取P[i]。
Observation 2﹕ 把Relax問題放到A[1..i]，答案P[i]始終固定。
因此我們可以直接計算max{Sum[0..i] - 2 * Sum[0..P[i]] - Sum[i+1..N+1]}，當中設A[N+1] = 0，即可。
我花了點時間還是做不到，故看了某blog的解題，其實方法也是用如前幾篇文章所述的Relax法去解題。
Relax﹕如果只允許取前綴的話，那麼最大和是多少？
答案是比較簡單的，只需計算 max{Sum[1..N] - 2 * Sum[1..i], Sum[1..N]}即可，注意第二個參數是代表不取任何前綴之和。留意該公式只有Sum[1..i]是有變化的，故可重寫成Sum[0..N] - min{Sum[0..i]}, 當中設A[0] = 0。故只需O(N)預計算Sum[0..i]，後取k令Sum[0..k]最小者即可。答案即 Sum[0..N] - 2 * Sum[0..k]。
那麼對於A的長度為N的答案我們可以用P[N]來紀錄，即P[N] = i。
Observation 1﹕ P[i] <= P[i+1]。
這是我們取P[N]的時候的by-product而已，同樣可以看作把Relax問題放到A[1..i]然後取P[i]。
Observation 2﹕ 把Relax問題放到A[1..i]，答案P[i]始終固定。
因此我們可以直接計算max{Sum[0..i] - 2 * Sum[0..P[i]] - Sum[i+1..N+1]}，當中設A[N+1] = 0，即可。
2011年1月12日 星期三
SRM 493 DIV 1 300 StonesGame
是次SRM以慘淡告終，原因無他﹕題目實在比平時要難。
先說第一道題。
給N顆石子，其中只有僅一顆石子是與其他不同顏色。現在兩個玩家輸流玩以下遊戲。
每次操作必須選一連續K顆石子，且必須包含不同顏的那顆。選定後，把該選定段的石子排列倒置。
給定該顆石子初始位置M及目標位置L，和N及K，問誰勝出，還是和局？
首先看到和局二字，必須確定有沒有機會出現。有時Topcoder的題目挺吊詭的，指明若沒有解的話則回傳某個數值，然而題目卻始終有解。尤其是二人遊戲無解者通常不是Nimber型題目，所以若例子沒有和局情況，就需要先証明題目是否有機會無解或者能轉換至經典的Nimber題，從而對300分設定合理化。可是例子中的確有和局情況，那麼我們大可以排除Nimber。難的地方就是如何分情況處理了。
若然真的沒法下手，可以試試把操作條件Relax看看有沒有線索。如果可操作方式從「倒置」改為「任意排列」，
操作就相當於把石子直接向左或向右移動最多K步。那麼結果是顯然易見的。
否則的話，可以再仔細分析一下。首先，先手必須走第一步。對於所有先手能走的位置，假若後手都能順利把石子移至目標位置，則後手必勝。甚麼時候和局呢？留意操作是可逆的，即先手向左移石子K'步，後手把的逆操作則是把石子向右移K'步即可。假設後手無論怎樣移石子都不可能到達目標位置的話，後者每一步都有可能引至贏局或輸局。若至輸局的話，後手會選擇避免輸局而進行逆操作；若後手選擇至贏局的話，先手亦同樣采取逆操作。如此一來，遊戲會變成無限循環，使得成為和局。
定理一和定理二給出的結論就是：遊戲結果始終能在兩步內決定。同樣的定理是否也適用於原題？答案是肯定的，因為原本操作只是把石子限制了左K步右K步內可移動的地方，因此不影響結論的正確性。
在編寫上這個結論可能不夠有效，但用逆向的走法則能給出簡單的寫法。
1. 枚舉從位置L中所有可能一步到達的位置
2. 若位置M已被標記，則先手能一步到達，故先手能勝。
3. 否則從枚舉位置M中所有可能一步到達的位置。若遇上未被標記的位置，則存在未能兩步到達的賽局。故和局。
4. 若3.不能得出和局，則後手能勝。
故答案可以在O(N)的時間內給出。
先說第一道題。
給N顆石子，其中只有僅一顆石子是與其他不同顏色。現在兩個玩家輸流玩以下遊戲。
每次操作必須選一連續K顆石子，且必須包含不同顏的那顆。選定後，把該選定段的石子排列倒置。
給定該顆石子初始位置M及目標位置L，和N及K，問誰勝出，還是和局？
首先看到和局二字，必須確定有沒有機會出現。有時Topcoder的題目挺吊詭的，指明若沒有解的話則回傳某個數值，然而題目卻始終有解。尤其是二人遊戲無解者通常不是Nimber型題目，所以若例子沒有和局情況，就需要先証明題目是否有機會無解或者能轉換至經典的Nimber題，從而對300分設定合理化。可是例子中的確有和局情況，那麼我們大可以排除Nimber。難的地方就是如何分情況處理了。
若然真的沒法下手，可以試試把操作條件Relax看看有沒有線索。如果可操作方式從「倒置」改為「任意排列」，
操作就相當於把石子直接向左或向右移動最多K步。那麼結果是顯然易見的。
定理一：若先手能一步把石子移至目標位置，則先手必勝。
否則的話，可以再仔細分析一下。首先，先手必須走第一步。對於所有先手能走的位置，假若後手都能順利把石子移至目標位置，則後手必勝。甚麼時候和局呢？留意操作是可逆的，即先手向左移石子K'步，後手把的逆操作則是把石子向右移K'步即可。假設後手無論怎樣移石子都不可能到達目標位置的話，後者每一步都有可能引至贏局或輸局。若至輸局的話，後手會選擇避免輸局而進行逆操作；若後手選擇至贏局的話，先手亦同樣采取逆操作。如此一來，遊戲會變成無限循環，使得成為和局。
定理二：若先手未能一步把石子移至目標位置，則若所有先手可步行之位置，後手能移至目標位置，後手必勝；否則和局。
定理一和定理二給出的結論就是：遊戲結果始終能在兩步內決定。同樣的定理是否也適用於原題？答案是肯定的，因為原本操作只是把石子限制了左K步右K步內可移動的地方，因此不影響結論的正確性。
在編寫上這個結論可能不夠有效，但用逆向的走法則能給出簡單的寫法。
1. 枚舉從位置L中所有可能一步到達的位置
2. 若位置M已被標記，則先手能一步到達，故先手能勝。
3. 否則從枚舉位置M中所有可能一步到達的位置。若遇上未被標記的位置，則存在未能兩步到達的賽局。故和局。
4. 若3.不能得出和局，則後手能勝。
故答案可以在O(N)的時間內給出。
2010年5月21日 星期五
PKU 數據結構習作
今天無聊，做起CSC3270四道數據結構習作。
PKU1182 食物链
依據路徑壓縮，可以對x-->y帶三種標號﹕ label(x) = 0 (x 與 y 同類), 1 (x 吃 y), 2 (y 吃 x)。
計算路徑計縮時必須先取x的根點, rx。 對於find(x)一遍後，最多只有這種結構﹕x-->y-->rx。假設它是合法的，那麼label(x)的更新必然是(label(x) + label(y))%3 (可用簡單向量理解)，然後對x進行路徑壓縮。
要判斷x y的關係，先尋找它們的根rx及ry。如果rx == ry，可以直接判同類(label(x) = label(y))或者x吃y ((label(x) - label(y) + 3) % 3 == 1 及 x != y)。
若rx != ry 顯然不會有矛盾。這意味著可以通過并合兩者來構造新的樹。對於x-->rx-->ry<--y，若果認為x跟y是同類的話，必有label(x) + label(rx) = 0 + label(y)。若果認為x吃y的話則有label(x) + label(rx) = 1 + label(y)。繼乎直接更新label和進行普通union就成。
PKU2481 Cows
如果任何可以強於[Si, Ei]的牛[Sj, Ej]，必須有Sj <= Si和 Ei <= Ej。可以想到當我們從最大的E值開始，相同E值的依最小S值來處理線段的話，保証處理當前線段時，所有強於它的線段都已經處理過了(並且不強於它的線段沒有被處理過)。此刻強於線段i的已處理線段必然都有<=Si的值。因此我們可以憑已處理並少於等於Si的S值進行統計並計算答案。然後把Si加進表中。這裡我們直接使用樹狀數組。對於重覆的[S, E]值，我們直接用上一個處理線段的值，因兩者有相等答案。緊記亦需把它加進數組中。
PKU2777 Count Color
純粹普通線段樹應用。一種顏色可用一個位元來記著。
PKU1442 Black Box
用最大堆及最小堆。每次把新的數放進最大堆。只要當前最大堆的大小超過counter，便把它放到最小堆內。最大堆永遠保持首counter小的數。最小堆的最小值便是答案，記得把它放會最大堆中。
PKU1182 食物链
依據路徑壓縮，可以對x-->y帶三種標號﹕ label(x) = 0 (x 與 y 同類), 1 (x 吃 y), 2 (y 吃 x)。
計算路徑計縮時必須先取x的根點, rx。 對於find(x)一遍後，最多只有這種結構﹕x-->y-->rx。假設它是合法的，那麼label(x)的更新必然是(label(x) + label(y))%3 (可用簡單向量理解)，然後對x進行路徑壓縮。
要判斷x y的關係，先尋找它們的根rx及ry。如果rx == ry，可以直接判同類(label(x) = label(y))或者x吃y ((label(x) - label(y) + 3) % 3 == 1 及 x != y)。
若rx != ry 顯然不會有矛盾。這意味著可以通過并合兩者來構造新的樹。對於x-->rx-->ry<--y，若果認為x跟y是同類的話，必有label(x) + label(rx) = 0 + label(y)。若果認為x吃y的話則有label(x) + label(rx) = 1 + label(y)。繼乎直接更新label和進行普通union就成。
PKU2481 Cows
如果任何可以強於[Si, Ei]的牛[Sj, Ej]，必須有Sj <= Si和 Ei <= Ej。可以想到當我們從最大的E值開始，相同E值的依最小S值來處理線段的話，保証處理當前線段時，所有強於它的線段都已經處理過了(並且不強於它的線段沒有被處理過)。此刻強於線段i的已處理線段必然都有<=Si的值。因此我們可以憑已處理並少於等於Si的S值進行統計並計算答案。然後把Si加進表中。這裡我們直接使用樹狀數組。對於重覆的[S, E]值，我們直接用上一個處理線段的值，因兩者有相等答案。緊記亦需把它加進數組中。
PKU2777 Count Color
純粹普通線段樹應用。一種顏色可用一個位元來記著。
PKU1442 Black Box
用最大堆及最小堆。每次把新的數放進最大堆。只要當前最大堆的大小超過counter，便把它放到最小堆內。最大堆永遠保持首counter小的數。最小堆的最小值便是答案，記得把它放會最大堆中。
2010年5月19日 星期三
ZOJ3334 Body Check
ZOJ 5月月賽題目。
大意是給了n個實數，代表了n個人需要完成身體檢的時間。有m個醫生為他們作身體檢查。一個人可以分開不同時段給不同醫生作身體檢查，唯獨是一個人不可以同一時間給多於一個醫生作身體檢查。另，醫院時刻也只能有這兩個情況﹕要麼m個醫生都在為不同的人作身體檢查，要麼就只有一個人在加班。問，最少需要多久能為所有人完成檢查？
首先，可以通過安排，使得工模式為「m位醫生工作 --> 一醫生工作」。如果一個人不可以分開時段給不同醫生檢查，可以得出問題的一種特例就是partition問題，是NP-Complete的。正因為可以任意分開時段，我們第一個想法就是直接取平均數。不過需要注意另一個限制「一個人不可以同一時間給多於一個醫生作身體檢查」。因為像5和5.1而m=2的話，雖然平均數是5.05，但是第二個人的0.1無法分拆成兩個不同時段。可以直接觀察得出，假若有一個需時大於平均數的話，剩出來的時間基本上無法放到任何平均數線之前，因為這位人本身已經獨佔了平均數線以前的時段。若然沒有這樣的問題的話，那麼我們必定可以安排所有人在平數時限前完成檢查。基於平均數本是最優的，所以我conjecture了這個算法﹕
為所有數取平均數，然後檢查每個數，若大於平均數，把多出的加到答案裡，然後把它們設為平均數，完成後重新再取平均數檢查；否則把平均數加到答案裡，並輸出答案。
一次AC。
訂閱：
文章 (Atom)
