---
# System prepended metadata

title: ABC 416
tags: [題解, ABC]

---

# 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$ ，不然轉移的時候會把不合法的狀態也算進去。
:::