TIOJ 1317 統治世界 Reign
Description
hellogameboy 正在進行一個神秘的計畫他打算以 H 的力量來征服全世界，讓世界都屈服在他的 H 勢力之下
這時候正義的 hallogameboy 挺身而出，決心鼎力維持這個世界的正直
想像這世界是一個 $n\times n$ 的格子棋盤，每個格子都是一個城市
而時事潮流總有固定的流向，因此對於每個格子都有一個"潮流傳播方向" (上、下、左、右之一)
若某個城市的潮流是流向棋盤邊界外，當然，這個城市的潮流就不會傳播給任何人
hellogameboy 和 hallogameboy 將輪流展開行動，
由 hellogameboy 先展開 H 的攻勢，再換 hallogameboy 進行正直防守......
攻防不斷交替地進行，直到所有城市都被佔領
一開始所有城市都是純潔的，沒有受到任何佔領
而 he(a)llohameboy 將選擇一個"源流城市"佔領
H (正直) 的力量就會從這個源流城市開始沿著每個格子的潮流傳播方向傳播
路上的城市都被佔領，直到某個潮流傳出邊界，或是遇到某個已被佔領的城市才停止。
以上圖為例（佔領攻防還沒結束，也不是最佳佔領策略）
hellogameboy 先選擇 $(2,2)$，並佔領紅色的 $12$ 格
再來換 hallogameboy，選擇 $(5,7)$，佔領藍色的 $8$ 格
再來又輪到 hellogameboy，選擇 $(5,6)$，佔領綠色 $2$ 格
hallogameboy 再選擇 $(2,4)$，佔領黃色等 $5$ 格……
給定一個地圖，假設 hallogameboy 和 hellogameboy 都是絕頂聰明的人物
那麼請問，最後 hellogameboy 將以 H 勢力會統領多少土地呢?
Input Format
第一行為一個整數 $n$，代表地圖邊長。再來為 $n$ 行，每行是一個不含空白的字串，由 l、r、u、d 構成，依序代表左、右、上、下的箭頭。
- $1\leq n\leq 2000$
Output Format
一個整數，代表先者 (hellogameboy) 可以佔領多少格。Sample Input
6drludl
rudlru
dldldl
rldlrd
uuudlr
ddlluu
Sample Output
19
Solution
設 $V$ 為這 $n^2$ 個格子的集合，$f: V\to V$ 為潮流傳播函數，規定如果某個點 $v$ 流向 $u$ 或邊界，則 $f(v) = u$ 或 $f(v) = v$。用 $f$ 建立一張 functional graph $F = (V, E)$，其中 $E = \{(v, f(v)): v \in V\}$。兩位玩家輪流在一局中選定一個點 $s$，令 $S$ 為「從 $s$ 出發能到達的點集合」，則在該局得到 $|S|$ 分，並執行 $F \gets F-S$。
為了方便，我們先定義一些名詞，儘管這些並不是正式名稱。我們定義一隻 (無向) 水母(jellyfish) 為點數和邊數相同的連通近圖 (pseudograph)。一隻水母由一個頭部 (環)，以及從頭部上的每個點長出來的觸手 (樹) 組成。
將一隻水母頭部的邊定向 (順時針或逆時針都可以)，並對每條觸手上的每條邊，規定邊的方向為父節點 (parent node) 到子節點 (child node)，得到總攻有向水母(seme directed jellyfish)。
類似地，我們可以定義總受有向水母(uke directed jellyfish)；注意將一隻總攻有向水母上的每條邊反向後，就得到總受有向水母。
這樣一來，任意 functional graph 都能被拆解成數隻總受有向水母。
回到「選擇一個點 $s$，把 $s$ 能到達的點集合 $S$ 拔掉」這個操作。假定 $s$ 在某隻總受有向水母 $J$ 上，則無論 $s$ 是多少，$S$ 一定包含 $J$ 的頭部。我們可以把 $F$ 中的每隻水母的頭部縮成一個點，規定這個點的權重為頭部大小，而其他觸手上的點的權重為 $1$。這樣一來，原問題就被 reduce 成：給定總受有向森林 $G$ (i.e. 每條邊的方向都是子節點到父節點)，點有非負權重。兩位玩家輪流在一局中選擇一個點 $s$，並設 $s$ 能到達的點集合為 $S$，則該局的得分為 $S$ 的權重和，並執行 $G \gets G-S$。目標求出最佳策略下兩位玩家的得分。
不難發現，如果先手開局選擇某個頂點 $v$ 有策略可以在遊戲結束時拿 $t$ 分，則選擇任意 $v$ 的子孫 (descendant) 開局也有策略在遊戲結束時拿到至少 $t$ 分。所以我們可以在遊戲中加入一條規則：每回合選擇的點必須是葉節點 (leaf node)。這樣一來，遊戲進行一局，$G$ 的葉子數量就少 $1$。
那麼先手該怎麼開局呢？有個簡單的貪婪 (greedy) 策略：選擇最大化第一局得分的葉子開局。我們先定義一些符號讓接下來的證明更加清晰：固定 $m \geq 1$ 並設 $H$ 為任意「有 $m$ 片葉子的總受有向森林」，我們說性質 $\mathcal{P}_m$ 成立，若且唯若對於所有的 $H$，開局貪婪會最大化最終分數。
現在固定 $H$，設貪婪策略選擇以 $H$ 的某片葉子 $v_1$ 開局，並在第一局拿到 $s_1$ 分，最終拿到 $S_1$ 分。假定先手改選擇 $v_2$ (可以等於 $v_1$) 開局，讓他在第一局拿到 $s_2$ 分，最終拿到 $S_2$ 分。以下是一個小引理：
注意 $G$ 可以是任意的，因此 $\mathcal{P}_m$ 對於所有的 $m \geq 1$ 都成立。
這個猜測和證明是我想的(因為當初 google 不到答案只好自己想了 QAQ)，如果有人能提出其他證明歡迎踢館。
至於實作部分，這題的記憶體限制非常緊，我連「用原本的 functional graph 建立總攻有向森林」都辦不到，吃了超多次 MLE。要看某個點的子節點們，只能每次看地圖上的上下左右四格，用時間換取空間。如果這題記憶體不要卡得這麼緊，優先權佇列 (priority queue) 可以用 $n^2$ 條 list 實作，做到 $O(n^2)$ 的時間複雜度。
以下是我的 AC code，時間複雜度 $O(n^2\log n)$，且除了 c++ 的 priority_queue 以外的地方都是 $O(n^2)$ 的：
https://ideone.com/H4nMwe
然後這是我第一次 AC 截的圖，為了不要 MLE 做了各種空間上的優化，真是辛苦我自己了 (無誤)：
為了方便，我們先定義一些名詞，儘管這些並不是正式名稱。我們定義一隻 (無向) 水母
 |
| 一隻頭部大小為 $4$ 的水母，頭部上的每個點是每條觸手的根。 |
將一隻水母頭部的邊定向 (順時針或逆時針都可以)，並對每條觸手上的每條邊，規定邊的方向為父節點 (parent node) 到子節點 (child node)，得到總攻有向水母
 |
| 將上面那隻水母的邊定向，得到總攻有向水母。 |
類似地，我們可以定義總受有向水母
 |
| 將上面那隻總攻有向水母的邊反向，得到總受有向水母。 |
這樣一來，任意 functional graph 都能被拆解成數隻總受有向水母。
回到「選擇一個點 $s$，把 $s$ 能到達的點集合 $S$ 拔掉」這個操作。假定 $s$ 在某隻總受有向水母 $J$ 上，則無論 $s$ 是多少，$S$ 一定包含 $J$ 的頭部。我們可以把 $F$ 中的每隻水母的頭部縮成一個點，規定這個點的權重為頭部大小，而其他觸手上的點的權重為 $1$。這樣一來，原問題就被 reduce 成：給定總受有向森林 $G$ (i.e. 每條邊的方向都是子節點到父節點)，點有非負權重。兩位玩家輪流在一局中選擇一個點 $s$，並設 $s$ 能到達的點集合為 $S$，則該局的得分為 $S$ 的權重和，並執行 $G \gets G-S$。目標求出最佳策略下兩位玩家的得分。
不難發現，如果先手開局選擇某個頂點 $v$ 有策略可以在遊戲結束時拿 $t$ 分，則選擇任意 $v$ 的子孫 (descendant) 開局也有策略在遊戲結束時拿到至少 $t$ 分。所以我們可以在遊戲中加入一條規則：每回合選擇的點必須是葉節點 (leaf node)。這樣一來，遊戲進行一局，$G$ 的葉子數量就少 $1$。
那麼先手該怎麼開局呢？有個簡單的貪婪 (greedy) 策略：選擇最大化第一局得分的葉子開局。我們先定義一些符號讓接下來的證明更加清晰：固定 $m \geq 1$ 並設 $H$ 為任意「有 $m$ 片葉子的總受有向森林」，我們說性質 $\mathcal{P}_m$ 成立，若且唯若對於所有的 $H$，開局貪婪會最大化最終分數。
現在固定 $H$，設貪婪策略選擇以 $H$ 的某片葉子 $v_1$ 開局，並在第一局拿到 $s_1$ 分，最終拿到 $S_1$ 分。假定先手改選擇 $v_2$ (可以等於 $v_1$) 開局，讓他在第一局拿到 $s_2$ 分，最終拿到 $S_2$ 分。以下是一個小引理：
[引理 A] 若 $\mathcal{P}_m$ 成立，則 $S_1 \leq S_2 + (s_1-s_2)$。
證明如下：把 $H$ 裡的 $v_2$ 權重增加 $s_1 - s_2$ 得到 $H'$，則根據 $\mathcal{P}_m$，我們知道在 $H'$ 上的遊戲，開局選擇 $v_1$ 和 $v_2$ 能獲得相同的最終分數。因為在 $H'$ 上，以 $v_2$ 開局的最終分數是 $S_2 + (s_1-s_2)$，而以 $v_1$ 開局的最終分數至少有 $S_1$，可知 $S_2 + (s_1-s_2) \geq S_1$。
[定理] 對於所有的 $m \geq 1$，$\mathcal{P}_m$ 均成立。
我們對 $m$ 做數學歸納法，並設 $G$ 為任意「有 $m$ 片葉子的總受有向森林」。當 $m=1$ 時，$G$ 就是一條串列 (list)，而先手也只有一種選擇，自然是最佳的。假定 $m \geq 2$，不失一般性假定 $G$ 只有一棵樹 (否則加一個權重為 $0$ 的節點 $s$，並對 $G$ 裡的每個樹根 $r$，加入有向邊 $r\to s$)。將葉子編號為 $v_1, v_2, \ldots, v_m$，並假設開局選擇 $v_1$ 能在第一局拿到最大分數 $s_1$。假定先手在開局選擇 $v_2$ 得到 $s_2$ 分，並使 $v_1$ 的分數降低成 $s_1^-$，而在這之後兩人認真玩遊戲。根據歸納法假設，可以假定兩人在第二局以後的每一局都選擇最大化該局得分的葉子。我們把這場遊戲每一局的策略與得分記錄下來： \[A(u_1:=v_2, t_1:=s_2) \to B(u_2, t_2) \to A(u_3, t_3) \to B(u_4, t_4) \to \ldots\] 注意我們有 $t_2 \geq t_3 \geq t_4 \geq\ldots$。設 $k\geq 2$ 是最小的整數滿足 $t_k \leq s_1^-$ ($k$ 必定存在，因為有一局 $v_1$ 被選到，而那時選擇 $v_1$ 的得分必定不超過 $s_1^-$)。為了方便，設- $v_1$ 和 $v_2$ 的 LCA (lowest common ancestor, 最低共同祖先) 為 $a$
- 從 $v_1$ 到 $a$ 的前一個節點為 $p$ (可能為 $v_1$)
- 從 $v_2$ 到 $a$ 的前一個節點為 $q$ (可能為 $v_2$)
Case 1: $k$ 是奇數
在第二場遊戲中，先手只要在第 $k$ 局選擇 $v_2$，最終分數就能和第一場一樣，因此開局選擇 $v_1$ 不會比較差。Case 2: $k$ 是偶數
設在第二場遊戲的第 $k$ 局，後手選擇 $u'_k$ (可以是 $v_2$ 或其他還沒被選到的葉子)。注意在這一局選擇 $u'_k$ 獲得的分數 $\sigma \leq s_1^-$，而選擇 $v_2$ 獲得的分數則是 $s_2^- := ($從 $v_2$ 到 $q$ 的點權重總和$) \leq \sigma$。不妨設這一局，拔去「$u'_k$ 到根的路徑」前的森林是 $H$。假設兩人第三次玩這個遊戲，其中前 $k-1$ 局的策略和第二次一樣，而在第 $k$ 局後手選擇 $v_2$，接下來兩人繼續認真玩遊戲。設第 $i\ (i = 1, 2, 3)$ 場遊戲的最終得分是 $S_i$，則由引理 A 我們有 \[S_2 \geq S_3 - (\sigma - s_2^-) \geq S_3 - (s_1^--s_2^-) = S_1\] 因此開局選擇 $v_1$ 還是不會比較差。注意 $G$ 可以是任意的，因此 $\mathcal{P}_m$ 對於所有的 $m \geq 1$ 都成立。
這個猜測和證明是我想的
至於實作部分，這題的記憶體限制非常緊，我連「用原本的 functional graph 建立總攻有向森林」都辦不到，吃了超多次 MLE。要看某個點的子節點們，只能每次看地圖上的上下左右四格，用時間換取空間。如果這題記憶體不要卡得這麼緊，優先權佇列 (priority queue) 可以用 $n^2$ 條 list 實作，做到 $O(n^2)$ 的時間複雜度。
以下是我的 AC code，時間複雜度 $O(n^2\log n)$，且除了 c++ 的 priority_queue 以外的地方都是 $O(n^2)$ 的：
https://ideone.com/H4nMwe
然後這是我第一次 AC 截的圖，為了不要 MLE 做了各種空間上的優化，真是辛苦我自己了 (無誤)：
留言
張貼留言