---
tags: Programming Contest
---
# AtCoder Beginner Contest 222 題解
## 心得
久違地打了一場…只解出四題，慘。
## A, B, C
(⋋▂⋌)
## D. [Between Two Arrays](https://atcoder.jp/contests/abc222/tasks/abc222_d)
設 $dp[i, j]$ = 合法的 $C_0, C_1, \cdots, C_i$ 數量，且 $C_i = j$。因為 $C_{i - 1}$ 需要少於 $j$ 就可以，可以寫出轉移：
$$
dp[i, j] = dp[i - 1][0] + dp[i - 1][1] + \cdots + dp[i - 1][j]
$$
等式右邊可以隨著 $j$ 增加，用前綴和來記錄。實作上 dp 可以使用二個一維陣列來壓縮空間。這題如果估時間複雜度，是 $3000 \times 3000$，害我在比賽時一直覺得這樣解不對，最後想不到其他硬寫下去就 AC 了……。
```python
mod = 998244353
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
prev = [0 for _ in range(3000 + 1)]
for c in range(A[0], B[0] + 1):
prev[c] = 1
for i in range(1, N):
curr = [0 for _ in range(3000 + 1)]
S = sum(prev[: A[i]]) % mod
for c in range(A[i], B[i] + 1):
S += prev[c]
S %= mod
curr[c] = S
prev = curr
print(sum(curr[A[i] : B[i] + 1]) % mod)
```
## E. [Red and Blue Tree](https://atcoder.jp/contests/abc222/tasks/abc222_e)
比賽中只想到去統計路徑中，各個邊出現的次數，然後看看這些次數 $c_0, c_1, \cdots, c_{N-1}$ 不能不能組出合理的 R 與 B，也想到了可以用 dp 去解這個組合問題。但就是漏了一個條件，害我一直以為要枚舉 R 或枚舉 B……可惜。
漏的條件是 $R + B = c_0 + c_1 + \cdots + c_{N-1}$。這個式子與題目所給的 $R - B = K$ 可以聯立方程，解出 $R = \frac{K + S}{2}$，其中 $S = c_0 + c_1 + \cdots + c_{N-1}$。也就是說給定路徑與 $K$ 後，$R, B$ 就被確定了！$R, B$ 都是定值！
而 dp 的部份也是簡單的，設 $dp[i, j]$ 為只考慮 $c_0 + c_1 + \cdots + c_i$ 組出 $j$ 的方法數。考慮用或不用 $c_i$ 可以寫出轉移方程：
$$
dp[i, j] = dp[i - 1, j] + dp[i - 1, j - c_i]
$$
如同無界背包，實作上我將這個 dp 的空間壓到一維，不壓好像也可以就是了。這題時間複雜度也是很極限，dp 的部份就是 $10^8$，一般 atcoder 的題目不會卡這麼極限的說。另外小心無解的情況，與路徑中可能會有自環！尤其是後者，我被這個卡了許久，例如測資
```
5 5 0
1 1 1 1 1
1 2
2 3
3 4
4 5
```
的答案應為 16。
```python
N, M, K = map(int, input().split())
A = [int(x) - 1 for x in input().split()]
G = [[] for _ in range(N)]
C = dict()
for _ in range(N - 1):
u, v = map(int, input().split())
u, v = u - 1, v - 1
G[u].append(v)
G[v].append(u)
C[(min(u, v), max(u, v))] = 0
for i in range(1, M):
s, t = A[i - 1], A[i]
stack = [s]
visit = [False for _ in range(N)]
parent = [-1 for _ in range(N)]
visit[s] = True
parent[s] = -1
while len(stack) > 0:
u = stack.pop()
if u == t:
break
for v in G[u]:
if not visit[v]:
stack.append(v)
parent[v] = u
visit[v] = True
path = [t]
while parent[path[-1]] != -1:
path.append(parent[path[-1]])
path.reverse()
for u, v in zip(path[:-1], path[1:]):
C[(min(u, v), max(u, v))] += 1
C = list(C.values())
S = sum(C)
# dp[i][j] = number of ways to form j from C[0], C[1], ..., C[i]
# dp[i][j] = dp[i - 1][j - C[i]]
V = 10 ** 5
dp = [0 for _ in range(V + 1)]
dp[0] = 1
mod = 998244353
for i in range(len(C)):
for j in range(V, C[i] - 1, -1):
dp[j] += dp[j - C[i]]
dp[j] %= mod
if (K + S) % 2 == 1 or (K + S) < 0:
print(0)
else:
print(dp[(K + S) // 2])
```
## F. [Expensive Expense](https://atcoder.jp/contests/abc222/tasks/abc222_f)
比賽中就有想到這題跟 diameter/eccentricity 很有關係，但一直想不到怎麼解決節點上的通行費。
官方題解首先利用了 diameter 的性質，在一個無向圖中，假設 $(s, t)$ 是一條 diameter，則對任一個點 $u$，恆有：
$$
ecc(u) = max(d(u, s), d(u, t))
$$
其中 $d()$ 是距離函式，此題包含著終點節點的通行費。
有了這個式子，我們的目標是找出一個 diameter $(s, t)$，然後使用 Dijkstra 找出以 $s$ 為出發點，所有點的最短距離 $dist_s$ ，與從 $t$ 出發所有點的最短距離 $dist_t$，然後任何一點 $u$ 的所求即是 $dist_s(u)$ 與 $dist_t(u)$ 中較大者。$(s, t)$ 可以透過二次 dijkstra 得到，如同在 Tree 中一樣。
```python
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
a, b, c = map(int, input().split())
a, b = a - 1, b - 1
G[a].append((b, c))
G[b].append((a, c))
D = [int(x) for x in input().split()]
dist = dijkstra(G, 0)
dist = [d1 + d2 for d1, d2 in zip(dist, D)]
max_dist = max(dist[u] for u in range(N) if u != 0)
s = next(u for u in range(N) if dist[u] == max_dist and u != 0)
dist = dijkstra(G, s)
dist = [d1 + d2 for d1, d2 in zip(dist, D)]
max_dist = max(dist[u] for u in range(N) if u != s)
t = next(u for u in range(N) if dist[u] == max_dist and u != s)
dist_s = dijkstra(G, s)
dist_t = dijkstra(G, t)
diameter = dist_s[t]
for u in range(N):
if u == s:
print(diameter + D[t])
elif u == t:
print(diameter + D[s])
else:
print(max(dist_s[u] + D[s], dist_t[u] + D[t]))
```
:::success
[< 回到所有題解](https://hackmd.io/@amoshyc/HkWWepaPv/)
:::
Sign in with Wallet
Connect another wallet