東區模擬賽 2021 題解

--- tags: Editorial, north1_110_sim --- # 東區模擬賽 2021 題解 [TOC] ## 上午場 ### A - 防疫破口 (Peko) - Idea：Ccucumber12 - 出題人：Ccucumber12 - 題目敘述：Ccucumber12 - 首殺：6:50 by 蔡平樂 - AC 人數：6 / 9 - 平均分數：17.56 / 25 $\texttt{struct}$ 排序實作題把每筆資料包在一個 $\texttt{struct}$ 裡面並對 $t_i$ 排序。接著依序檢查每筆資料，並以 $cnt$ 紀錄目前的室內人數。若 $op_i = 1$ 則將 $cnt - 1$；若 $op_i = 0$ 則將 $cnt + 1$，同時如果 $cnt > k$ 則將 $name_i$ 記錄於任意容器內。最終將該容器排序輸出即可。第一子題不需任何排序，第二子題須對 $\texttt{string}$ 排序，第三子題須對自定義 $\texttt{struct}$ 排序。 ### B - 礦砂採集 (Ore) - Idea：SorahISA - 出題人：SorahISA - 題目敘述：SorahISA - 首殺：11:10 by 蔡平樂 - AC 人數：7 / 9 - 平均分數：20.11 / 25 首先，往左邊走以及挖左邊的礦砂堆是完全沒用的操作，因為一直往右走一定最好。所以以下敘述都不會包含到往右走的 $N-1$ 次操作。如果 $a_i \ge a_{i+1}$，那麼可以直接往右走；如果 $a_i < a_{i+1}$，那麼往右走會需要花費 $a_{i+1} - a_i$ 單位時間，而且會讓 $a_{i+1}$ 變成 $a_i$。注意到往下挖的操作只會讓後面需要挖的東西變多，所以不應該在不必要的時候往下挖。要移動到第 $N$ 坨礦砂堆上面，挖東西的花費就是 $$\sum_{i=1}^{N}{\left(a_i - \min_{j=1}^{i}{a_j}\right)}$$ 可以在 $O(N^2)$ 或 $O(N)$ 時間計算完成。要特別注意的情況有：沒開 $\texttt{long long}$ 只會拿到 $15$ 分、到第 $N$ 坨礦砂堆之後需要往下挖到高度 $0$。 ### C - A $C$ B Problem (AcB) - Idea：Ccucumber12、SorahISA - 出題人：SorahISA - 題目敘述：SorahISA - 首殺：44:54 by 安馬林 - AC 人數：3 / 9 - 平均分數：9.22 / 25 先考慮 $C = 111 \dots 111$ 的情況，每次都取 $A$ 跟 $B$ 的個位數，將他們加起來並存到一個陣列（或字串）裡面，最後再倒著輸出就可以了。第一個 Subtask 可以用 $\texttt{int}$、第二個 Subtask 可以用 $\texttt{long long}$ 做掉，第三個 Subtask 就需要使用字串來存了。如果 $C$ 的數字可以任意，首先先把 $c_i = 0$ 的情況判掉，因為字串為空不用管它。接下來是處理字串跟數字的轉換的部分，切出一段字串可以使用 $\texttt{str.substr(start_pos, length)}$、轉數字可以使用 $\texttt{stoi(str)}$、轉回字串可以使用 $\texttt{to_string(number)}$。剩下的部分就是實作了，要特別注意的情況有：可能會取到超出字串位置的地方，以及可能兩個位置加起來結果是 $0$。 ### D - 分居 (Partition) - Idea：Ccucumber12 - 出題人：SorahISA - 題目敘述：catJam - 首得分：85:28 by 蔡平樂 (12/25) - 最高分：153:46 by 蔡平樂 (18/25) - AC 人數：0 / 9 - 平均分數：3.67 / 25 對於第一個 Subtask，只要輸出 ``` 1 1 1 2 ``` 就能拿到 $1$ 分了。首先，「把東西分成兩邊使得同一組之內沒有邊」可以被達成若且唯若給定的圖是二分圖，以下以黑色跟白色來表示二分圖的兩塊獨立集。先考慮圖**連通**的狀況：從任意的點開始 DFS，對於所有相鄰的點，如果它還沒有被上色，就把它標示為另一個不同的顏色並走訪；如果它已經被上色了，就去檢查是不是跟當前的點顏色不相同，**如果顏色相同即無解**。在上述的走訪過程中我們會將所有點塗上黑或白兩種顏色之一，接著就去判斷應該要把黑色還是白色給 $\mathrm{Cat}$ 就可以了。如果只考慮圖連通的狀態會拿到 $12$ 分。對於圖**不連通**的狀況，先觀察到兩個不在同一個連通塊的點不會互相影響到對方，所以可以分開做。只要每次對一個連通塊 DFS 完都找出應該要把它的黑色還是白色給 $\mathrm{Cat}$，就能通過本題。 Extra：分成數量盡量平均的兩堆，一樣平均的狀況就使 $\mathrm{Cat}$ 的字典序最小。 ### E - 井字遊戲 (TicTacToe) - Idea：Ccucumber12 - 出題人：Ccucumber12 - 題目敘述：catJam - 首殺：127:38 by 蔡平樂 - AC 人數：1 / 9 - 平均分數：6 / 25 回朔法尋找所有可能性利用一個 $3\times 3$ 陣列紀錄目前盤面，並透過 DFS 去搜尋每一步的可能性。在每次 DFS 前，先檢查目前盤面是否已有人獲勝，若有的話則記錄獲勝方並 return；反之則開始尋找該步可以下在哪裡。並對所有的可能性繼續往下 DFS，直到下完九步若仍無人獲勝，則紀錄為平手並 return。細節上可以將盤面初始化為 $-1$，並利用 $1$、$0$ 分別代表 $\texttt{o}$ 和 $\texttt{x}$，此時 $\texttt{step & 1}$ 就可以代表該步的下棋方。檢查的過程中可以傳入前次的下棋方（該次的反方），因為只有他有可能在這步之前獲勝。如此一來便可以輕易的判斷每行／列／斜線是否等於該方，並以迴圈簡化實作量。 ## 下午場 ### F - 代理股王 (Agent) - Idea：SorahISA - 出題人：SorahISA - 題目敘述：catJam - 首殺：8:55 by 蔡平樂 - AC 人數：5 / 9 - 平均分數：20.22 / 25 可以把題目轉化成以下樣貌 > 定義一個位置 $i$ 的「完美值」$p_i$ 是指對所有 $i - p_i \le j < i$ 都有 $a_j < a_{j+1}$，且對所有 $i < j \le i + p_i$ 都有 $a_j < a_{j-1}$ 的最大值。 > 給定一長度為 $N$ 的數列，求其最高的完美值、以及此完美值的出現次數。接著就可以直接枚舉每個中間點去尋找兩邊的長度最長能到多長。要特別注意的地方是答案可能為 $0$，有不少人都栽在這上面。 Extra：$N \le 1\,000\,000$。 ### G - 字母對消 (Alphabet) - Idea：Ccucumber12 - 出題人：Ccucumber12 - 題目敘述：Ccucumber12 - 首殺：37:24 by 吳畬 - AC 人數：5 / 9 - 平均分數：15 / 25 貪心＋動態規劃首先考慮選取字母對的可能性，選取距離越遠的字母對會消除更多的字母，因此我們會希望能選取越接近的越好。所以對於任意的字母，我們必然只會選擇他與上一次出現或下一次出現的位置相配對，中間不可能再出現相同的字母。（ex. $\texttt{a__a__a}$：我們只會選擇 $(s_1, s_4)$ 或者 $(s_4, s_7)$，而不會選擇 $(s_1, s_7)$。因此在最佳選擇下，我們最多只有 $\mathcal{O}(|s|)$ 個字母對可以選擇，而這些字母對就相當於 $\mathcal{O}(|s|)$ 個線段。此時我們的題目等價於給定多個帶權重線段，請選出一些線段使得任兩個線段不相交且權重總和最大。對於這種題目我們可以考慮動態規劃：$\texttt{dp}[i] = [s_1, s_i]$ 所能產生的最大權重和。對於字母 $s_i = c$，找到 $c$ 上次出現的位置 $j$，並考慮 $$ \texttt{dp}[i] = \max\left\{ \underbrace{\texttt{dp}[j] + V(c)}_{選取該線段}, \underbrace{\texttt{dp}[i-1]}_{不選取該線段} \right\} $$ 而在尋找 $c$ 上次出現的位置，我們可以開一個 $26$ 格長的陣列記錄每個字母最後出現的位置，並在轉移 $\texttt{dp}$ 值後更新。此時的時間複雜度為：$\mathcal{O}(|s|)$ 狀態 $\times$ $\mathcal{O}(1)$ 轉移 $=$ $\mathcal{O}(|s|)$。然而如果我們暴力往後尋找上次出現的位置，考慮平均下來每個位置的時間複雜度：假設我們平均往後走 $k$ 格，則這 $k$ 格內每個字母最多出現一次，否則那個重複的字母長度就會 $< k$。所以我們可以得知 $k\leq|C|$，其中 $|C| = 26$ 代表字母集的大小。因此在這題我們的時間複雜度就會是：$\mathcal{O}(|s|)$ 狀態 $\times$ $\mathcal{O}(|C|)$ 轉移 $=$ $\mathcal{O}(|C||s|)$，是一個好的時間複雜度。（題目測資並沒有出爛，~~暴力本來就可能出奇蹟~~）另外一種分析方法如下：先對每個字母分開來看，如果我們把他的所有位置都抓出來，那麼最後一個位置會往回跑到倒數第二個位置，倒數第二個位置會往回跑到倒數第三個位置。以此類推，第二個位置會往回跑到第一個位置，而第一個位置會往回跑到字串開頭的位置，總共跑的距離和最多是 $\mathcal{O}(|s|)$。因為字元集大小只有 $|\{\texttt{a}, \texttt{b}, \dots, \texttt{z}\}| = 26$，所以暴力的做法只要適當地加上 break 也可以在 $\mathcal{O}(26 |s|)$ 的時間跑完。 Extra：選取一個端點相同的區間消除時，可以獲得的分數改為【區間內出現與端點同字母的數量】乘上【該字母的權重】。 ### H - 石油王與遺跡考古 (Relics) - Idea：mmi366127 - 出題人：SorahISA - 題目敘述：SorahISA - 首得分：80:12 by 李尚哲 (1/25) - 最高分：106:50 by 蔡平樂 (7/25) - AC 人數：0 / 9 - 平均分數：0.89 / 25 TL;DR：暴搜剪枝 + bitset 優化前兩個 Subtask 比較簡單，可以 $\mathcal{O}(2^N)$ 枚舉所有子集，檢查他的大小是不是 $\ge K$（實際上只要檢查 $= K$ 的狀態），再去看所有子集的狀態取 $\texttt{bitwise-AND}$ 的結果，並把該結果的所有子集都丟進答案裡。這樣可以拿到前兩個 Subtask 共 $3$ 分。實作上我們讓 $\texttt{sets}[i]$ 是一個長度為 $C$ 的 $01$-字串，$\texttt{sets}[i][j]$ 代表第 $i$ 個集合有沒有包含數字 $j$。那如果使用暴搜呢？每次搜一個數字集合有沒有出現 $\ge K$ 次，如果有就把他存下來，繼續加一個數字搜尋下去。我們來分析一下暴搜的複雜度：首先，如果遞迴到了一個出現次數 $< K$ 的狀態，那就不會再繼續下去，否則答案數量一定會至少 $+1$，所以你至多只會遞迴進 $ans = 300\,000$ 個節點，且在每個節點內至多會對 $C = 3\,000$ 個數字進行判斷，如果判斷有幾個集合內存在數字的複雜度是 $\mathcal{O}(N)$，直接實作的複雜度就會是 $\mathcal{O}(ans \times C \times N)$，可以通過三到四個 Subtask，拿到 $7 \sim 15$ 分。具體搜尋方法如下，要注意如果直接在 $11 \sim 15$ 行那裡就宣告 $\texttt{nxt_match}$，那麼宣告 $\texttt{nxt_match}$ 的次數會從 $ans$ 退化成 $ans \times C$： ```cpp= // in_sets[i][j] = 1 代表數字 i 存在在集合 j 內 vector<vector<bool>> in_sets(C, vector<bool>(N)); vector<vector<int>> answers; // 目前的所有答案 vector<int> choose; // 當前搜尋的答案 // match[i] = 1 代表集合 i 有包含 choose void dfs(int now, vector<bool> match) { answers.push_back(choose); // 把目前搜尋的狀態加進答案 for (int i = now+1; i <= C; ++i) { // 計算加入數字 i 之後有幾個集合包含 choose int nxt_match_count = 0; for (int j = 1; j <= N; ++j) { // 如果【其他 choose 內的在集合 j 內】且【數字 i 在集合 j 內】就加一 nxt_match_count += match[j] & in_sets[i][j]; } // 如果有超過 K 個集合包含 choose 則遞迴下去 if (nxt_match_count >= K) { // 把包含 choose ∪ {i} 的集合構出來 vector<bool> nxt_match = match; for (int j = 1; j <= N; ++j) { nxt_match[j] = nxt_match[j] & in_sets[i][j]; } choose.push_back(i); // choose <- choose ∪ {i} dfs(i, nxt_match); // 遞迴下去處理 choose.pop_back(); // choose <- choose - {i} } } } ``` 最後的分數需要使用 $\texttt{std::bitset}$ 來優化。這是一個常見的優化技巧，如果你要儲存的值只包含 $0$ 跟 $1$，且在計算上常常使用到 $\texttt{bitwise-AND}$、$\texttt{bitwise-OR}$、或是 $\texttt{XOR}$ 就可以使用他，他的常數會比正常實作還要小 $32 \sim 64$ 倍。觀察到 $\texttt{vector<bool>}$ 可以使用 $\texttt{bitset}$ 代替掉，所以 code 會變成這樣，實作上也非常簡潔： ```cpp= bitset<N> in_sets[C]; vector<vector<int>> answers; vector<int> choose; void dfs(int now, bitset<N> match) { answers.push_back(choose); for (int i = now+1; i <= C; ++i) { if ((int)(match & in_sets[i]).count() >= K) { choose.push_back(i); dfs(i, match & in_sets[i]); choose.pop_back(); } } } ``` 複雜度是 $\mathcal{O}(ans \times C \times \frac{N}{\text{bitset}}) \approx 1.7 \times 10^9$，而實際上常數還會比這個小好幾倍，可以在 $1.5$ 秒左右跑完。