AA 競程 2023 TOI 模擬賽決賽

# AA 競程 2023 TOI 模擬賽決賽 --- * 賽前難易度猜測 $E ≈ A < C < D < B$ * 實際每題 AC 人數(包含同步賽) A：12 人 B：0 人 C：16 人 D：6 人 E：12 人 --- E. 這是 TOI 會考的普通題嗎？首殺：Fysty (47 mins) ---- #### 子題 1 * n 對情侶坐成一圈的方法總共有：$2 \times 9! \times 2^9$，直接枚舉所有方案的話，大概會超時。 ---- * 但是每對情侶若確定坐哪兩個位置時，我們可以貪心的決定誰左誰右會比較好。 * 所以枚舉的情況剩下 $9!$ 種。 ---- #### 子題 2 & 3 * 不妨假設情侶坐的位置是 $2i-1$ 和 $2i$。 * 把每個人當圖論上的點，情侶間連一條邊，$a_{2i-1}$ 和 $a_{2i}$ 也連一條邊 * 可發現此圖是由很多環組成，且長度為 2 的環上兩人都可獲得自己想要的餐具。而其餘長度為 2k 的環，至多能有 k 個人坐在自己喜歡的餐具前，並且方案有兩種。 * 每個環各自判斷哪種方案字典序最小，即可 $O(N)$ 解出此題。 ---- * 若只拿到子題 2 的分數，大概是你陣列開太小了。 --- A. TOI 也會出搜索題？首殺：hank55663 (16 mins) ---- #### 子題 1 * ~~為了迎合題目敘述，雖然不知道怎麼估時間複雜度~~，但出題者有測試過，寫了個暴力搜索枚舉所有合法的可能 cycle 就通過所有測試資料了 ---- #### 子題 2 * 先把原有的 '#' 上下左右都標記為不能走方法一： * 接著找到兩個留下來的 path 頭尾端，用 BFS 找他們間合法路徑的最短路，一定滿足環自身沒有在不該相鄰的地方相鄰 ---- 方法二： * 接著找到兩個留下來的 path 頭尾兩端，從其中一端使用 DFS，過程中只走不會和兩步以前走過的地方相鄰的格子，並且不要走已拜訪過的格子，有辦法證明若存在解，最終一定能走到另外一端 --- C. TOI 也會出 IMO 題？首殺：PixelCat (44 mins) ---- ---- #### 子題 1 * 首先呢，$(x1,y1),(x2,y2),(x3,y3)$ 三個點構成的三角形的重心為 $(\frac{x1+x2+x3}{3},\frac{y1+y2+y3}{3})$ ---- * 算出重心後套範例測試資料的海龍公式即可 AC 此子題 ---- #### 子題 2 * 會算重心座標的話，可直接套用 [CSES2191 Polygon Area](https://cses.fi/problemset/task/2191) 的解法解此子題 * 算簡單多邊形的面積可利用 [Shoelace formula](https://en.wikipedia.org/wiki/Shoelace_formula)(中文似乎被稱作鞋帶定理) ---- #### 子題 3 * 請參考題目附圖，可以證明 $\triangle p_1C_1C_2$ 面積是 $\triangle p_1m_2m_3$ 的面積的 $\frac{4}{9}$ * 所以每個詢問其實都是 $p_i$ 以及沒和 $p_i$ 相鄰的邊的中點所形成的凸多邊形面積的 $\frac{4}{9}$，可發現在計算鞋帶定理時，共通的項非常多，不用重新計算。 * 時間複雜度為 $O(n)$ --- D. TOI 也會出構造題？首殺：8e7 (81 mins) ---- #### 子題 1 * 觀察一：每一列黑格是連續的，只需維護左右界 * 觀察二：每一列的黑格左界是先遞減在遞增，右界是先遞增再遞減 ---- 只要暴力枚舉遞迴枚舉所有可能情況可以，有辦法計算出在 $\max(N,M) \le 8$ 的情況下，滿足上頁兩個觀察的不同黑格塗色方式並不多。 ---- #### 子題 2 * 使用 DP，令 $dp[i][l][r][dec][inc]$ 代表現在考慮到第 $i$ 列，且第 $i$ 列黑格左界是 $l$，右界是 $r$，$dec$ 是個布林值代表黑格左界是否正在遞減，$inc$ 是個布林值代表黑格右界是否在遞增。 * 如此一來就有個 $O(N^5)$ 的 dp 作法 ---- #### 子題 3 * 子題 2 的轉移使用噁心的二維 RMQ 優化大概能變成 $O(n^3 log n)$ * 歡迎大家提供優美的作法 ---- #### 子題 4 * 引理：假設 $i < j < k$ 且 row $i,k$ 都至少有一個黑格，定義 $row\_ma_i$ 為第 $i$ row 的黑格最大的 column 座標那麼 $row\_ma_j \ge \min(row\_ma_i, row\_ma_k)$ * 根據此引理可以 $O(n)$ 找出每個 row 的最大 coumn 座標至少有多大，最小的 column 座標至少有多小也能用類似方法求出 ---- * 例如左邊的測試資料，考慮完上頁的情況後，我們會得到右邊的 `#` 是一定要有黑格的位置 ```txt 11 13 #............ #............ ..#.......... .##.......... .#........... .##.......... ............. ............. .....#....... ...###....... ...#..#...... ...####...... .....#....... .....##...... ............. ............. ............. ............. ..........#.. .........##.. .........#.#. .........###. ``` ---- * 可能會有數個連通塊，但每個連通塊的 x 和 y 座標必單調遞增或遞減 * 不妨假設這些連通塊座標 x 和 y 是同時遞增，並把連通塊編號為 $1 \sim k$，考慮每個連通塊的最小包矩形，每個編號 $2 \sim k$ 的連通塊最小包矩形左上角一定是黑格；每個編號 $1 \sim k-1$ 的連通塊最小包矩形右下角一定是黑格 * 把編號 $i$ 的連通塊右下角和編號 $i+1$ 的連通塊左上角以任意最短路連接，就會是最佳解 ---- * 第三張圖的 `X` 展示一種可能的連接所有連通塊的方式 ```txt 11 13 #............ #............ #............ ..#.......... .##.......... X##.......... .#........... .##.......... .##.......... ............. ............. ..XX......... .....#....... ...###....... ...###....... ...#..#...... ...####...... ...####...... .....#....... .....##...... .....##XXX... ............. ............. .........X... ............. ............. .........X... ..........#.. .........##.. .........##.. .........#.#. .........###. .........###. ``` --- B. TOI 也會出字串題？首殺：可惜此題沒人 AC :( ~~賽後 alvingogo 把賽中的 code 做常數優化後就 AC 了(但時限是標程 3 倍，應該不算卡常唷) ~~ ---- #### 子題 1 * 暴力枚舉每個詢問的所有路徑求最小的字串即可通過 ---- #### 子題 2 & 3 此題在考驗大家用正確的順序 DP 要搞清楚一件事： * 令 $s1, s2$ 是字串，$c$ 是字元 * $s1$ 字典序 < $s2$ 不代表 $s1+c$ < $s2+c$ * 例如：$s1=$ `a`，$s2=$`aa`，$c=$`b` ---- * 引理：點 x 到點 y 的字典序最小路徑一定是 x 走恰一條邊至某個點 i，再從點 i 走字典序最小路至點 y * 請不要覺得這件事很顯然，若把它改成：「點 x 到點 y 的字典序最小路徑一定是 x 走字典序最小路到某個點 i，再從點 i 走恰一條邊至 y」就是錯的 ---- * dp[i][j] 代表點 i 至點 j 路徑上字典序最小字串，根據引裡可列出轉移式： $dp[i][j] = \min\limits_{k=i+1}^j{s_i[k-j-1]+dp[k][j]}$ * 此作法時間複雜度為 $O(N^4)$ ---- #### 子題 4 * 對於所有的詢問，$ed_i$ 值相同 (令其為 $t$) 的答案可用 $O(N^2)$ 的時間算出 * 只要用 $x$ 從大到小的順序依序計算出 $x$ 至 $t$ 的字典序最小最短路，此最短路不需要儲存整個字串，只需要儲存離開 $x$ 第一個走到的點是哪個點即可。 ---- * 「只需要儲存離開 $x$ 第一個走到的點」是因為我們可以維護一個 list 按照字典序大小排列所有編號大於 $x$ 的點到 $t$ 的字典序最小路。 * 要比較第一個走到的點是誰比較好，只要比較第一個字母以及走到的點在 list 裡的順序即可。 * 可用 $O(N)$ 時間插入新的點到 list 裡。 ---- * 若用一些高級的平衡樹資料結構，邊數非 $O(N^2)$ 時能做到更好的時間複雜度