---
tags: Programming Contest
---

# AtCoder Beginner Contest 183 題解

## 心得

解出 5 題，積分 +54。

第四題漏看了一個條件，害我花了好久。
第六題竟然直接裸著來，我以為這方法會 MLE 就沒寫，可惜。

[source](https://home.gamer.com.tw/creationDetail.php?sn=3060065)

## A. [ReLU](https://atcoder.jp/contests/abc183/tasks/abc183_a)

38 秒，下次挑戰不先測直接 submit XD。

## B. [Billiards](https://atcoder.jp/contests/abc183/tasks/abc183_b)

入射角 = 反射角這樣的反彈，就會想到對稱啦。將 G 對著 x-axis 對稱，然後求出 SG 的直線方程，再把 y = 0 代入即為所求。當使用點斜式時，記得小心斜率可能無窮大，不過這題保證 S.x ≠ G.x，因此不會發生。

sx, sy, gx, gy = map(int, input().split())
dx = gx - sx
dy = -gy - sy
ans = sx + dx * (-sy) / dy
print('{:.15f}'.format(ans))

## C. [Travel](https://atcoder.jp/contests/abc183/tasks/abc183_c)

直接 8! 全排列爆開。

from itertools import permutations

N, K = map(int, input().split())
T = [list(map(int, input().split())) for _ in range(N)]

ans = 0
for perm in permutations(range(N)):
    if perm[0] != 0:
        continue
    need = sum(T[perm[i - 1]][perm[i]] for i in range(1, N)) + T[perm[-1]][0]
    if need == K:
        ans += 1
print(ans)

## D. [Water Heater](https://atcoder.jp/contests/abc183/tasks/abc183_d)

因為之前注的水不能給之後的人用，所以只需考慮有沒有任何一個時刻，所需的總水量大於能供給的水量。實作方法為將 $(s, t, p)$ 視為在時刻 $s$ 增加 $p$，在時刻 $t$ 減少 $p$，這樣當我們從時間 0 迭代到時間 $t$ 時，**累計**的總數就是時刻 $t$ 的需求。

N, W = map(int, input().split())

events = []
for _ in range(N):
    s, t, p = map(int, input().split())
    events.append((s, +p))
    events.append((t, -p))

events.sort()
cum_sum = 0
for (t, p) in events:
    cum_sum += p
    if cum_sum > W:
        print('No')
        break
else:
    print('Yes')

## E. [Queen on Grid](https://atcoder.jp/contests/abc183/tasks/abc183_e)

設 $dp[r, c]$ 為從起點走至 $(r, c)$ 的方法數。

考慮 queen 的三種移動方式，當前位置可能是「從上方來的、從左邊來的、從左上來的」，我們可以寫出轉移方程：

$$
dp[r, c] = \sum_{0 \le i \lt r} dp[i, c] + \sum_{0 \le i \lt c} dp[r, i] + \sum_{0 \le i \lt min(r, c)} dp[r - i, c - i]
$$

明顯這個 dp 會 TLE，讓我們想辦法優化。一個常見手法是使用額外容器記錄之前 dp 值：

1. 一個長度為 `W` 的 list `cntC` 記錄每個 column 目前的累計 $dp$。
2. 一個長度為 `H` 的 list `cntR` 記錄每個 row 目前的累計 $dp$。
3. 一個長度為 `H + W - 1` 的 list `cntD` 記錄每個 diagonal 目前的累計 $dp$。

如果 $(r, c)$ 是障礙物，記得重設（清零）各個累計 $dp$。

當我們算出 $dp[r, c]$ 後，記得更新這些容器。

實作上，如何處理對角線會是一個難題，但我想到我以前有將之寫成[模版](https://amoshyc.github.io/CPsolution/template/math/index_of_diagonal.html#d)。

$(r, c)$ 的如果使用 $H - 1 - r + c$ 作為對角線編號會形成如下：

$$
\begin{split}\begin{pmatrix}
3 & 4 & 5 & 6 & 7 \\
2 & 3 & 4 & 5 & 6 \\
1 & 2 & 3 & 4 & 5 \\
0 & 1 & 2 & 3 & 4 \\
\end{pmatrix}\end{split}
$$

H, W = map(int, input().split())
mod = 10 ** 9 + 7
S = [input() for _ in range(H)]

dp = [[0 for _ in range(W)] for _ in range(H)]
cntR = [0 for _ in range(H)] # row
cntC = [0 for _ in range(W)] # col
cntD = [0 for _ in range(H + W - 1)] # diagonal

for r in range(H):
    for c in range(W):
        if S[r][c] == '#':
            cntR[r] = 0
            cntC[c] = 0
            cntD[H - 1 - r + c] = 0
            continue

        if r == 0 and c == 0:
            dp[r][c] = 1
        else:
            if r > 0:
                dp[r][c] += cntC[c]
            if c > 0:
                dp[r][c] += cntR[r]
            if r > 0 and c > 0:
                dp[r][c] += cntD[H - 1 - r + c]
            dp[r][c] %= mod
        
        cntR[r] = (cntR[r] + dp[r][c]) % mod
        cntC[c] = (cntC[c] + dp[r][c]) % mod
        cntD[H - 1 - r + c] = (cntD[H - 1 - r + c] + dp[r][c]) % mod

print(dp[H - 1][W - 1])

## F. [Confluence](https://atcoder.jp/contests/abc183/tasks/abc183_f)

又是集群又是合併，Disjoint Set 無誤啦。
難點是如何處理 class，一個直覺的想法是對 dsu 中每個 tree 都記錄該 tree 有幾個 class 1, 幾個 class 2, etc，然後這個方法就能 AC 了。我比賽中一直以為這個方法要 $O(N C)$ 的空間，因此會 MLE。但實際上如果用 `dict` 來存各 class 數量，所需空間與時間就能少上許多。

實作上可以修改 dsu 的程式碼，把 `dict` 放進去。因為我不能改模板太多，所以 `dict` 我是放在 dsu 之外，dsu 只需額外告訴我，合併 tree a 與 tree b 時，是 a 併入 b 還是 b 併入 a，我對應地修改 `dict`。這題我有嘗試用 `collections.Counter` 來代替 `dict`，但會 TLE，果然寫 python 真的不能用 `Counter`。

from collections import defaultdict

class DisjoinSet:
    def __init__(self, N):
        self.par = [-1] * N
        self.sz = [1] * N

    def root(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return None, None
        if self.sz[a] > self.sz[b]:
            a, b = b, a
        self.par[a] = b
        self.sz[b] += self.sz[a]
        return a, b

    def same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, x):
        return self.sz[self.root(x)]

    def __str__(self):
        clusters = defaultdict(list)
        for x in range(N):
            clusters[self.root(x)].append(x)
        return str(list(clusters.values()))


N, Q = map(int, input().split())
C = [int(x) for x in input().split()]

dsu = DisjoinSet(N)
rec = [defaultdict(int, {C[i]: 1}) for i in range(N)]

for _ in range(Q):
    cmd, a, b = map(int, input().split())

    if cmd == 1:
        a, b = a - 1, b - 1
        src, dst = dsu.unite(a, b)
        if src is not None:
            for k, v in rec[src].items():
                rec[dst][k] += v
            rec[src].clear()
    else:
        a = a - 1
        root = dsu.root(a)
        print(rec[root][b])

:::success
[< 回到所有題解](https://hackmd.io/@amoshyc/HkWWepaPv/)
:::