# 【題解】Atcoder ABC 314, 318 ## ABC 314 E **Roulettes** 計算期望值的題目經常使用動態規劃來解決。此題我們定義狀態 $dp[i]$ ：目前有 $i$ 點，要達到 $m$ 點的最小花費期望值。 轉移時枚舉要轉哪一個轉盤，接著從該轉盤上的不同值計算出期望值。 $$ dp[i]=max_{j=1\dots n} \, C[j] + \frac 1 P_j \sum dp[i + S[j][k]] $$ 注意到如果某個轉盤上的點數為零，那麼便把它當成不存在，把該輪盤的花費改成 $C_i \frac {P_i} {P_i - Z_i}$。 複雜度 $O(M \sum P)$。 ## ABC 314 F. **A Certain Game** > 給定 $n$ 個隊伍， $n-1$ 場比賽 $u, v$ ，其中 $u$ 獲勝的機率是 $\frac {|u|} {|u|+|v|}$， $v$ 反之。比賽後兩支隊伍會合併。求每個隊伍獲勝的期望次數。 $n \le 2 \times 10^5$ > 對於一場比賽，我們要將一邊隊伍的所有成員累計上一個獲勝機率，另一邊也是。由於兩邊的成員都是確定的，因此機率也是確定的。我們考慮如何高效的加上獲勝機率。 當 $u,v$ 比賽後，隊伍會合併，我們可以用並查集維護。當合併 $u,v$ 兩個連通塊，我們便新建一個點代表該次合併。最後我們會得到一顆 $2n-1$ 個節點的二元樹，為 kruskal 重構樹。在合併時也維護尺寸，那麼我們就能知道重構樹上每個節點的尺寸。 我們從重構樹的根開始，分別把獲勝的機率下推到左右兒子。 複雜度 $O(n)$。 ## ABC 318 D **General Weighted Max Matching** > 在一張完全圖上，你要選擇盡可能多的邊權，使得沒有邊共用一個節點。 $n \le 16$。 > 該題 $n$ 極小，我們可以考慮用位元 DP。可以觀察到影響到是否可以選擇一條邊的因素為：兩點是否已經被其他邊選擇。 因此以每一個點被選擇與否作為狀態，轉移時枚舉每一條邊即可。 複雜度 $O(2^n \times n^2)$。 ## ABC 318 E **Sandwiches** > 給定一個序列 $A$，求有多少三元組 $i < j < k$ 使得 $A_i = A_k$ 且 $A_i ≠ Aj$。 $N \le 3 \times 10^5$。 > 可以觀察到，對於一組一樣的數字 $A_i, A_k$，中間所有不相同的數字都會與他們形成一組答案，而中間是什麼數字並不重要。 我們可以將不同數字分開討論，往下我們只考慮數字 $X$。我們紀錄他們的位置分佈，形成一組新的序列 $P$。 亦即，$P_i$ 為第 $i$ 個 $X$ 在 $A$ 中的位置。我們可以計算 $P_i$ 和 $P_j$ 之間會形成多少三元組： $cnt(i,j) = P_j - P_i - (j-i)$。 觀察一下，整個 $P$ 會形成多少三元組。可以發現，不同起點的三元組數量之間是有變化的關係的。 只要依照這個關係去維護就可以了。維護複雜度為 $O(\sum |P|)$，由於 $\sum P = N$，因此總複雜度為 $O(N)$。 ## ABC 318 F Octopus > 給定嚴格遞增的 $X_1, X_2, \dots, X_n$ 和非嚴格遞增的 $L_1, L_2, \dots, L_n$，求有多少 $k$ 使得可以為每個 $X_i$ 分配恰一個 $L_j$，並且 $X_i \in [k-L_j, k+L_j]$。 $N \le 200, |X| \le 10^{18}, L \le 10^{18}$。 > 我們嘗試枚舉 $k$。當 $k$ 已經決定，那們我們可以得到每個點離 $k$ 的距離： $D_1 \le D_2 \le \dots \le D_n$。顯然最優的方法是分配 $D_i$ 到 $L_i$，也就是越遠分配越長，一一對應。因此我們可以 $O(n)$ 的去檢查 $k$ 是否合法。 但 $k$ 的範圍十分大，我們沒辦法枚舉過所有的 $k$。我們把任一 $k$ 形成的 $D_1, D_2, \dots, D_n$ 放在數線上，以及 $L_1, L_2, \dots, L_n$ 放在數線上。 $D_i$ 會分別屬於不同 $L_i, L_{i+1}$ 的區間。如果我們嘗試去移動 $k$ ，可以發現在使得某個 $D_i$ 改變所屬區間之前，答案是不會改變的。我們稱這時的 $k$ 為關鍵位置。關鍵位置有： $X_i - D_j - 1, X_i - D_j, X_i + D_j, X_i + D_j + 1$。 因此我們只需要枚舉這些關鍵位置。如果兩個相鄰的關鍵位置都是合法的，那他們中間也一定合法。要注意處理連續合法的情況。