2020 ICPC Asia Taiwan Online Programming Contest 簡易題解
===
###### tags: `ICPC` `TOPC`

本文題目順序由裁判長題目難度，從易到難安排。可用 Python 做出的題目至少有 A, B, D, I, J。[題面、測試資料、範例程式在此，可下載。](https://drive.google.com/drive/folders/1q9I8o1v_HEY_-rzy_boflOL_jNx7ODF9)

## Problem I - Site Score

難度設定：簽到題。

題意是定義一個假想的 site score 計算公式： $56U_R+24T_R+14U_O+6T_O$，然後輸入檔給定 $U_R,T_R,U_O,T_O$ 四個正整數，請大家計算。本題只需要能夠讀入四個整數，並與給定的參數相乘後相加即可得到答案。

難度構成：入門格式輸出入、入門四則運算。大一才剛開始學的人也可以答對喔。

## Problem A - Pac-Man

難度設定：簽到題 -- 台灣整體程度上升後的簽到題。

題意是在一個 $10\times10$ 的格子盤面，由輸入給定一個起點，求在 10000 步內走過所有格子的方法，過程中不能走出盤面。建議的做法是，先想好如何從一個特定點出發，完成目標的走法 (如 Sample 測試資料)，然後自己只要寫走到該特定點的走法即可。這部份可以請各位參考我們提供的範例程式。

難度構成：入門格式輸出入、選擇結構、重複結構等流程控制技術的基礎運用。

Bonus: 本題加強版可以作到求 99 步內經過所有格子的方法。
Hint:

{"RRRRRRRRRD",
 "UDLLLLLLLL",
 "URRRRRRRRD",
 "UDLLLLLLLL",
 "URRRRRRRRD",
 "UDLLLLLLLL",
 "URRRRRRRRD",
 "UDLLLLLLLL",
 "URRRRRRRRD",
 "ULLLLLLLLL"}

## Problem B - Folding

難度設定：容易

題意是有一個充分長的透明帶，有兩個連續區間被塗上紅色，並要在 $q$ 個位置折折看，看折完以後有多少長度看起來是紅色的。

由於每一次折都是獨立的，大致上只需要寫好下面幾個部份：
+ 折完之後，一個區間的座標變換成什麼樣子。可觀察不論在任何地方折，都不會變出更多連續區間。
+ 區間雖不會變多，但可能重疊。寫判斷是否重疊的程式。
+ 如果沒有重疊，長度就是兩個區間長度相加。
+ 如果有重疊，算出重疊部份有多長即可。

如果步驟劃分清楚，每一個步驟之間的資料轉換時，可以選擇維護讓他們保有某些性質，比如說折完之後，兩個區間可能依據起點排序，就會比較容易判斷是否重疊、計算重疊時的長度等等。

另一種解:
將折下去的點當成$0$，兩邊各被切成一些線段，把這些線段拿來做線段覆蓋長度。

難度構成：閱讀、分類討論

## Problem D - Last Will

難度設定：中等

題意： $ABCD$ 是一個面積為 1 的正方形，而 $E, F, G, H$ 分別是 $\overline{AB},\overline{BC},\overline{CD},\overline{DA}$ 的中點，要在正方形內部(不含邊界)找到一點 $X$ ，使得 $AEXH, BFXE, CGXF$ 的面積比值為 $p:q:r$ ，有解時以最簡分數形式輸出 $X$ 之座標，無解時輸出 `-1` 。

先假定有解，畫出 $\overline{AX},\overline{BX},\overline{CX},\overline{DX}$ 作為輔助線，不難觀察出四塊地 $AEXH$, $BFXE$, $CGXF$, $DHXG$ 的面積比值為 $p:q:r:p+r-q$。由面積總和為 1 我們可以在推出四塊地的面積分別為 $\frac{p}{2p+2r}$, $\frac{q}{2p+2r}$, $\frac{r}{2p+2r}$, $\frac{p+r-q}{2p+2r}$。接下來，我們可以透過每個四邊形面積由兩個三角形構成來列二元一次聯立方程式：
+ $x+y=\frac{2p}{p+r}$
+ $x-y=\frac{p+r-2q}{p+r}$

因為有解，列兩個就夠了。如果算出來的 $X$ 沒有落在 $ABCD$ 中，那就是無解。剩餘的實做部份，就是利用分數的資料型態，或是自己維護分子分母配輾轉相除法即可。

難度構成：幾何解析、二元一次方程式、輾轉相除法

註：Python 有 `Fraction`，可以省很多實做。但即使用其他程式語言，也大多有內建的最大公因數函數可用。

## Problem H - In the Name of Confusion

難度設定：中等

題意：給 $n$ 個點，每個點有一個值$a_i$，任兩點中間都有一條無向邊，點 $i$ 和點 $j$ 間的邊權為 $a_i\times a_j$，求最大和最小生成樹。

做法：先將點依據 $a_i$ 值分成三個集合： $P=\{v: a_v>0\}$，$Q=\{v: a_v<0\}$ 及 $Z=\{v: a_v = 0\}$。要建立的最小/最大生成樹，每個點連出去的邊，可以只考慮 (後面會證) 另一端會連到 $M^+=\mathrm{maxarg}_{v\in P}a_v$, $m^+=\mathrm{minarg}_{v\in P}a_v$, $M^-=\mathrm{maxarg}_{v\in Q}a_v$, $m^-=\mathrm{minarg}_{v\in Q}a_v$, $z=\mathrm{maxarg}_{v\in Z}a_v$，這五個點其中一個。不一定每個都存在，只要考慮存在的那些即可，如有多個點同權重，選任意一個即可。這五點分別為具有最大正 $a_i$ 值、最小正 $a_i$ 值、最大負 $a_i$ 值、最小負 $a_i$ 值、以及 $a_i$ 值為零的點。因此我們可以建出一個有 $O(|V|)$ 邊數的圖，透過常用的最小/最大生成樹演算法如 Kruskal's 或 Prim's 在 $O(|V|\log|V|)$ 時間內求出解。

證明：假定最小生成樹上使用到某一條邊 $\{i, j\}$，兩端點 $i,j\notin\{M^+,m^+,M^-,m^-,z\}$。考慮下述情形：
+ $a_i<0$ 且 $a_j<0$: 可知 $M^-$ 存在，可推出 $a_i\times M^- \le a_i\times a_j$ 及 $a_j\times M^- \le a_i \times a_j$。當我們移除 $\{i, j\}$ 這條邊時最小生成樹將破成兩塊，而 $\{i, M^-\}$ 與 $\{j, M^-\}$ 中，必有一條可以連通這兩塊形成新生成樹，且不差於原先的最小生成樹。
+ $a_i>0$ 且 $a_j>0$: 與前一情形對稱，在此省略證明。
+ $a_i>0$ 且 $a_j<0$: 可知 $M^+$ 與 $m^-$ 存在，可推出 $a_i\times m^- \le a_i\times a_j$ 及 $a_j\times M^+ \le a_i \times a_j$。當我們移除 $\{i, j\}$ 這條邊時最小生成樹將破成兩塊，而 $\{i, m^-\}$ 與 $\{j, M^+\}$ 中，必有一條可以連通這兩塊形成新生成樹，且不差於原先的最小生成樹。
+ $a_i<0$ 且 $a_j>0$: 與前一情形對稱，在此省略證明。

因假定 $i,j\notin\{M^+,m^+,M^-,m^-,z\}$ 我們可以不討論 $a_i=0$ 或 $a_j=0$ 的情形。另最大生成樹證明方式類似，在此省略證明。

難度構成：最小生成樹相關性質與演算法

註：最小生成樹屬於比較常見的演算法、資料結構類型的題目基底。如果還不熟悉，可在準備過程中，多找這類題來做。

## Problem C - Circles

難度設定：中等

題意：平面上給定 $n$ 個點座標 $p_1=(x_1, y_1), p_2=(x_2, y_2), \dots, p_n=(x_n, y_n)$，以每個點分別為圓心等速率的增加半徑，直到與另一個圓相切為止。輸出最終每個圓的面積總和。

做法：計算任意兩點的距離，將距離的一半與兩點的索引值一同儲存到 Priority Queue 中，以距離的一半當作 Key。每個回合從 Priority Queue 中找到 Key 最小的 $(r, i, j)$，其中$(r, i, j)$ 表示在有圓長到了 $r$ 長度的半徑後，圓心在索引值為 $p_i$ 、 $p_j$ 的兩個圓相切。我們需要維護每個圓到什麼時間停止成長，因此在每筆 $(r, i, j)$ 取出時，檢查其兩端點是否停止成長：

1. 兩端點都還沒停止成長，那他們都會停止在 $r$ ，紀錄兩點停止成長的半徑。
2. 兩端點都停止成長，就進行下一個回合。
3. 有一端點停止成長，那就檢查目前的 $r$ 加上已經停止成長的圓之半徑 $r'$ 是否為兩點間距離。
+ 是：那原先還沒停止成長的圓將會停在 $r$
+ 否：令 $r''$ 為兩者距離扣掉 $r'$，並將 $(r'',i,j)$ 放進 Priority Queue 中。

時間複雜度 $O(|V|^2\log |V|)$，一對 $(i,j)$ 只會放進在 Priority Queue 裡頂多兩次。而沒有放進去的東西是不會被拿出來的，因此複雜度是 $O(|V|^2\log(|V|^2))=O(|V|^2\log|V|)$。

難度構成：內建資料結構、模仿 Dijkstra's $O(|E|\log |V|)$實作的複雜度分析。

註：有 $O(|V|^2)$ 的做法。

## Problem J - Table Tennis

難度設定：中等略偏難

題意：一場標準 7 局 4 勝制，每局 11 分有 deuce 制的比賽中，假設 Robot A 發球時其得分機率固定為 $P_A$，Robot B 發球時其得分機率固定為 $P_B$，問 A 獲勝的機率有多少。其中第奇數局 A 先發球，第偶數局 B 先發球，在 10:10 (deuce) 之前都是輪流發 2 球，deuce 之後輪流發 1 球，直至該局分出勝負。

做法：

這樣的題目不論在單局的得分數或各局勝負總和，都明顯可以用 DP (Dynamic Programming) 來做，需要注意的是奇數局和偶數局先發球的人不同，此外在局中每個得分數出現的機率都需要考慮發球順序。由於題目限制 $0<P_A+P_B<2$，所以不會出現 $P_A=P_B=0$ 或 $P_A=P_B=1$ 的情況，也就是說不論比賽走向為何，都有機會結束。

我們先考慮在單局中各個得分數出現的機率：
1. 可以只考慮 A 得分的機率，當 A 發球時為 $P_{A0}=P_{A}$，當 B 發球時為 $P_{A1}=1-P_{B}$
1. 由於 deuce 之後必需領先 2 分才算獲勝，在這樣的情況下 A 獲勝的機率不論這局誰先發球，都會是 $\frac{P_{A0}P_{A1}}{P_{A0}P_{A1}+(1-P_{A0})(1-P_{A1})}$
1. 在 deuce 之前，假設目前分數為 A 得 $a$ 分，B 得 $b$ 分，且目前已打完 $s$ 局，那麼接下來發球的人會是
$$\left\{\begin{array}{ll} A, & \texttt{(((a+b)&2)>>1)^(s&1)}=0 \\ B, & \texttt{(((a+b)&2)>>1)^(s&1)}=1 \end{array} \right.$$
其中符號 ``&``、``>>`` 和 ``^`` 分別代表 bitwise operation 中的 AND、right shift 和 XOR。
1. 最後，在這局中將以下兩種情況的機率相加即為此局 A 的獲勝機率
(1) A 得 11 分且 B 得 0~9 分的機率加總
(2) AB 各得 10 分的機率乘上 2. 所列的機率

接著考慮各個局數出現的機率：假設 A 先發球時 A 贏得該局的機率為 $S_{A0}$，B 先發球時 A 贏得該局的機率為 $S_{A1}$，且目前 A 已贏得 $a$ 局，B 已贏得 $b$ 局。那麼 A 贏得此局的機率為

$$\left\{ \begin{array}{ll} S_{A0}, & \texttt{(a+b)&1}=0 \\ S_{A1}, & \texttt{(a+b)&1}=1 \end{array}\right. $$

其中符號 ``&`` 代表 bitwise operation 中的 AND。

最後，將 A 贏得 4 局且 B 只贏得 0~3 局的機率加總即為本場比賽 A 獲勝的機率。需要注意的是此題要求的精準度為絕對誤差不超過 $10^{-8}$，只以 ``%f`` 輸出的精準度在部份測資會不符要求，請至少使用 ``%.8f`` 或是其他類似的方式輸出。

難度構成：DP (Dynamic Programming)、機率

註 1：當 input 最多各只有 2 位小數時，可以數學證明 double 型別在計算中絕對誤差不會超過 $10^{-12}$，因此此題要求輸出至少精準到絕對誤差不超過 $10^{-8}$ 的情況下，不需要使用大數即可作答

註 2：亦可枚舉各局 A 或 B 可獲勝的比數 ( $11:p$ 及 $(12+p) : (10+p)$ ) 的情況，再枚舉比賽獲勝的局數 ( $4:k$ ) 的情況來計算。

## Problem G - Garden

難度設定：中等偏難、裝備檢查向

題意：給一個 $n\times m$ 的格子花園，一些格子太溼不能種仙人掌，其他格子可以種仙人掌，但任兩個仙人掌不能相鄰。求最多可以種幾棵仙人掌，並且把種植的方法輸出。

做法：把可以種的格子當點，相鄰的格子建邊，可以發現這是一張二分圖，題目就變成二分圖最大獨立點集。在二分圖上，「最大獨立點集+最大匹配數=圖的節點數」。常用做法：將二分圖左邊接起點，右邊接終點，可以用 Dinic's 算法求出最大匹配，複雜度$O(|E|\sqrt{|V|})$，接著根據 König 定理，選出任意一個最小割，在二分圖左邊的屬於起點跟在二分圖右邊屬於終點的即為一組解。

難度構成：König 定理、格子圖是二分圖、Dinic's 算法或 Hopcroft-Karp 算法求二分圖匹配。

註：本題裝備檢驗，還算是常出現的題材。

## Problem E - Eric's Work

難度設定：中等偏難、構造巧思向

題意：給定兩個長度為 20 的相異零壹字串 $s$ 跟 $t$ 以及一個整數至多 500000 的 $D$ 。每次操作均為修改一個位元，求是否有正好 $D$ 個操作的修改法，能將 $s$ 改成 $t$ 且過程中沒有產生出重複的零壹字串。

做法：首先觀察無解的情形，可以發現如果 $s$ 跟 $t$ 相異的位置數量，比 $D$ 還要多時，一定無解。接下來，如果相異位置數量與 $D$ 奇偶性不同也會無解，因為一步一定會改一個位置。接下來，讓我們斗膽猜測剩餘的情形一定有解！以下我們分兩個情形討論：

+ 相異位置數量為 1：在這種情境下，$D$ 必然是奇數，且小於 $2^{19}$ ，我們可以參考編碼長度為 19 bit 的 [Gray code](https://en.wikipedia.org/wiki/Gray_code) ，從修改一個 bit 可以走到不重複的 $2^{19}-1$ 步，經歷過所有長度為 19 的零壹字串。如果有了解 Gray code 的編碼原理，那會知道基本上除了最終被修改的那一個位置，前面一半的修改經過，反過來就是後面一半，因此我們可以在前面走了 $k$ 步之後，直接修改最終要被修改的那一個，再倒帶回來走 $k$ 步，即可做出一個 $2k+1$ 步，過程中不重複，最後修改到我們想要處理那個位置的方法。
+ 相異位置數量至少 2：承上，我們先標記一個不可以修改的位置，然後用前面的方法，用其他 19 個位置，修改掉另外一個該修改的位置，並把步數走到原先相異位置數減一。接下來修改先前一段沒用到的那個位置 (上一步不可修改，但最終要改的位置)，之後再把其餘每個相異的位置改掉，即可剛剛好用完，也不可能跟前面重複：因為一開始沒動的位置被改了。

難度構成：Gray code 與 Gray code 的設計思維

## Problem F - Homework

難度設定：中等偏難、實作細心向

題意：每個小朋友手上都有一張白紙剛開始都有個 $0$ ，接有$q$次操作，第 $i$ 次操作會把編號在 $[\ell_i,r_i]$ 的小朋友紙上加上一個符號 (加減乘除) 跟一個數字，全部操作完之後，問所有人紙上算式的和，並把所有詢問的答案加起來輸出，並$\bmod 10^9+7$ 。如果是分數 $\frac{p}{q}$ ，則輸出$p\cdot q^{-1}\bmod\ 10^9+7$，其中$q\cdot q^{-1}\equiv 1 \bmod 10^9+7$。

做法： $-x$ 可以換成 $+(10^9+7-x)$，`/` 可以用費馬小定理或是擴展歐幾里德算法求出模逆元換成乘法。接著用懶標線段樹 (可 Google 搜尋 Lazy Propagation in Segment Tree) 維護答案，做乘法時就直接區間乘法，加法先把那區的答案總和存起來，之後將那個區間全部指定為加的值即可，每次操作完的答案為整顆線段樹的總和加上前面所儲存的答案。

難度構成：懶標線段樹(區間乘法、區間詢問、區間改值)、模逆元、實做