# AtCoder Beginner Contest 416 Unofficial Editorial ~~為了減少製作成本~~，以下不會幫你翻譯題目，也不會有實作的 code (因為我覺得要自己想過然後用自己的方式實做出來比較好，不要直接抄)。 如果想看 code ，可以去 submission 找，應該有更多實作比我好看的。 然後這次好難喔，好難好難 (＞︿＜) ### A (●'◡'●) ### B :::spoiler 觀察 1 把 `＃` 當作牆壁的話，題目的意思就是在每個「房間」都放一個 `o` ::: :::spoiler 離題 關於題目名稱 ~ 是這個遊戲 [Daily Akari](https://dailyakari.com/) 很好玩喔，推薦大家去玩，搭配教室的觸屏服用風味更佳 (●'◡'●) 至於題目叫做 1D Akari 顯然就是要在每個房間點燈 (●'◡'●) ::: ### C :::spoiler 觀察 1 $N \leq 10$ $K \leq 5$ $N^K$ 才 $100000$ ，暴力 ::: :::spoiler 實作 寫一個 DFS 得到全部 $N^K$ 個字串，排序 ::: :::spoiler 複雜度 $O(N \times N^KlogN^K)$ 因為字串長度 $N$ 也會對排序有影響 ::: ### D :::spoiler 觀察 1 $0 \leq A_i, B_j < M$ 如果 $A_i + B_j \geq M$ ，答案只會加上 $A_i + B_j - M$ 所以答案就是全部 $A_i + B_j$ 再減掉滿出來的那些 $M$ ::: :::spoiler 觀察 2 因為希望答案越小越好，所以配對的時候要讓滿出來的 $A_i + B_j$ 對越多越好，這樣就可以減掉比較多個 $M$。 ::: :::spoiler 實作 將 $A$、$B$ 由小到大排序，對於每個 $A_i$，嘗試用雙指針 $j$ 由後往前掃找到第一個滿足 $A_i + B_j \geq M$ 的 $B_j$ 湊成一對，如果有找到，代表答案可以多減掉一個 $M$。 ::: :::spoiler 為什麼這樣貪心是對的 用反證法證明上述方法可以得到最多對 $A_i+B_j \geq M$： 令用上述方法得到的解叫做 $S$，假設存在最優解叫做 $S^*$ 。 因為 $S \neq S^*$ ，所以 $S^*$ 中必存在一組以上和 $S$ 不同的配對方式，假設 $S^*$ 中將 $A_i$ 和 $B_j$ 配對在一起、$A_k$ 與 $B_l$ 配對在一起，其中 $i<k$ 且 $j<l$，考慮交換使得 $A_i$ 和 $B_l$ 配對在一起、$A_k$ 與 $B_j$ 配對在一起 : 因為 $B_l \geq B_j$ ，所以 $A_i$ 配 $B_l$ 也會大於等於 $M$ 因為 $A_k \geq A_i$ ，所以 $B_j$ 配 $A_k$ 也會大於等於 $M$ 交換後配對數不會減少，而且可以不斷透過以上的交換把 $S^*$ 變成 $S$，得證 $S$ 就是最優解。 ![2025-07-27 20 25 16](https://hackmd.io/_uploads/SkXa95QPxx.png) ::: :::spoiler 複雜度 $O(nlogn)$ ::: ### E :::spoiler 觀察 1 $N \leq 500$ type 3 的詢問要計算全點對最短路 適合用最短路演算法中的 ||Floyd Warshall|| ::: :::spoiler 觀察 2 先令 `dis[i][j]` 表示 $i$ 到 $j$ 的最短路 機場怎麼辦 ? 令 `fly[i]` 表示 $i$ 到最近的機場要走多遠，則 `dis[i][j] = min( dis[i][j], fly[i]+T+fly[j] )` ::: :::spoiler 觀察 3 增加機場怎麼辦 ? 假設在 $x$ 蓋新的機場 則對所有 $i$ 更新 `fly[i] = min( fly[i], dis[i][x] )` 再對所有 $i$、$j$ 更新 `dis[i][j] = min( dis[i][j], fly[i]+T+fly[j])` 增加公路怎麼辦 ? 假設增加 $x \leftrightarrow y$，花費時間 $t$ 的路 則對所有 $i$、$j$ 更新 `dis[i][j] = min({ dis[i][j], dis[i][x]+t+dis[y][j], dis[i][y]+t+dis[x][j] })` 因為增加公路可能使 `fly[i]` 變短，所以也要 : 對所有 $i$ 和所有機場 $a$ 更新 `fly[i] = min( fly[i], dis[i][a] )` 再對所有 $i$、$j$ 更新 `dis[i][j] = min( dis[i][j], fly[i]+T+fly[j] )` ::: :::spoiler 複雜度 $O( N^3 + Q \times N^2 )$ ::: :::spoiler WA ? 小心==重邊==，所以建圖的時候要 `dis[x][y] = min( dis[x][y], t )` ::: ### F :::spoiler 觀察 1 樹 DP ::: :::spoiler 觀察 2 令狀態 `dp[i][j][k]` 表示以 $i$ 為根的子樹，目前進行 $j$ 次操作，其中 : 1. $k=0$ 代表 $i$ 沒用到，是白色 2. $k=1$ 代表 $i$ 是某條路的端點，可以再延伸 3. $k=2$ 代表 $i$ 是某條路的中繼點，不能再延伸 ::: :::spoiler 觀察 3 (轉移) 先用 DFS 把 $i$ 的子節點們的 DP 值都算完，假設現在要從子節點 $u$ 來轉移。假設 $i$ 共做了 $j$ 次操作，$u$ 共做了 $k$ 次操作 : 1. $i$ 挑的路和 $u$ 挑的路沒有關係 `dp[i][j+k][x] = max( dp[i][j+k][x], dp[i][j][x]+dp[u][k][y] )`，$x$、$y$ 為任意狀態 3. $i$ 挑的路是 $u$ 挑的路再往上延長一個點 ($i$ 是端點) `dp[i][j+k][1] = max( dp[i][j+k][1], dp[i][j][0]+dp[u][k][1]+ i 這個點的權重 )` 5. $i$ 挑的路是 $u$ 挑的路再和另一條路接在一起 ($i$ 是中繼點) `dp[i][j+k-1][2] = max( dp[i][j+k-1][2], dp[i][j][1]+dp[u][k][1] );` ::: :::spoiler 複雜度 $O(N \times K^2)$ ::: :::spoiler WA ? 為了避免 DP 重複轉移，可以開另一個陣列，轉移完再複製回來。 還有 DP 初始化不能是 $0$ ，不然轉移的時候會把不合法的狀態也算進去。 :::