---
tags: Programming Contest
---

# AtCoder Beginner Contest 182 題解

## 心得

第四題又卡住，還好最後一分鐘 AC，應該先去解第五題，簡單多了 (︶︹︺)
把上一場加的積分全還回去了 QQ

## A, B

簽到。

## C. [To 3](https://atcoder.jp/contests/abc182/tasks/abc182_c)

基於 3 倍數的特性，可以得出不可能刪 3 個 digits 或更多。刪 1 個 digit 的情況為有某個 digit 與 「N 對 3 的餘數（r）」相同。刪 2 個的情況是選兩個 digits 出來，他們的和可以組出 r。實作時小心別讓所有的 digits 都被刪掉了。

from itertools import combinations

N = input()
r = int(N) % 3
A = [int(c) % 3 for c in N]
if r == 0:
    print(0)
elif len(A) >= 2 and any(a == r for a in A):
    print(1)
elif len(A) >= 3 and any((a + b) % 3 == r for a, b in combinations(A, 2)):
    print(2)
else:
    print(-1)

## D. [Wandering](https://atcoder.jp/contests/abc182/tasks/abc182_d)

假設我們看第 $i$ 次操作，我們的位置為這些（假設之前的位置為 `prev[i]`）：

prev[i]
prev[i] + A[0]
prev[i] + A[0] + A[1]
prev[i] + A[0] + A[1] + A[2]
...
prev[i] + A[0] + A[1] + A[2] + ... + A[i - 1] + A[i]

我們想找出其中最大的值：

$$
prev_i + max(0, \sum_{j=0}^0 A_j, \sum_{j=0}^1 A_j, \cdots, \sum_{j=0}^i A_j)
$$

設 $P$ 為 `A` 的前綴，我們可以簡化式子為：

$$
prev_i + max(0, P_0, P_1, \cdots, P_i)
$$

有了這個想法後，讓我們將第 $i-1$ 次操作與第 $i$ 次操作所求的值都寫出來：

$$
\begin{align}
&prev_{i-1} + max(0, P_0, P_1, \cdots, P_{i - 1})
\\
&prev_i + max(0, P_0, P_1, \cdots, P_{i - 1}, P_i)
\end{align}
$$

可以發現我們能輕易的從第 $i-1$ 次操作轉換至第 $i$ 次操作。

根據題意，式子的第一項是這樣轉換：

$$
prev_i = prev_{i - 1} + P_i
$$

而式子的第二項則為

$$
max(0, P_0, P_1, \cdots, P_{i - 1}, P_i) = max(max(0, P_0, P_1, \cdots, P_{i - 1}), P_i)
$$

這暗示了我們可以一個一個迭代操作，然後找出該操作所求的最大值。

完整的程式為：

N = int(input())
A = [int(x) for x in input().split()]

prev = 0
pref = 0
mx_pref = 0
ans = 0
for i in range(N):
    pref += A[i]
    mx_pref = max(mx_pref, pref)
    ans = max(ans, prev + mx_pref)
    prev += pref
print(ans)

## E. [Akari](https://atcoder.jp/contests/abc182/tasks/abc182_e)

這題類似於之前比賽 [某題](https://hackmd.io/@amoshyc/Skr-nHJDP#E-Lamps) 的簡單版。

解法不只一種，而我的是開 4 個 H * W 的陣列，分別記錄會不會被「上、下、左、右」的燈炮點亮：

visL[r][c] = True if (r, c) will be lit by a bulb in (r, k) (0 <= k < c)
visR[r][c] = True if (r, c) will be lit by a bulb in (r, k) (c < k < W)
visT[r][c] = True if (r, c) will be lit by a bulb in (k, c) (0 <= k < c)
visD[r][c] = True if (r, c) will be lit by a bulb in (k, c) (c < k < H)

這 4 個陣列都可以用簡單 dp 求出。考慮該方向相鄰的格子是不是 block，我們可以得出：

visL[r][c] = False if grid[r][c - 1] is BLOCK else visL[r][c - 1]

同理類推。最後統計一下有多少個格子，被一個或多個方向的燈炮點亮。

import sys

input = sys.stdin.readline

H, W, N, M = map(int, input().split())
EMPTY = 0
BULB = 1
BLOCK = 2

grid = [[EMPTY for _ in range(W)] for _ in range(H)]
for _ in range(N):
    r, c = map(int, input().split())
    grid[r - 1][c - 1] = BULB
for _ in range(M):
    r, c = map(int, input().split())
    grid[r - 1][c - 1] = BLOCK

visL = [[False for _ in range(W)] for _ in range(H)]
visR = [[False for _ in range(W)] for _ in range(H)]
visT = [[False for _ in range(W)] for _ in range(H)]
visD = [[False for _ in range(W)] for _ in range(H)]
for r in range(H):
    for c in range(W):
        if grid[r][c] == BULB:
            visL[r][c] = True
            visR[r][c] = True
            visT[r][c] = True
            visD[r][c] = True

for r in range(H):
    for c in range(1, W):
        if grid[r][c] == EMPTY:
            visL[r][c] = False if grid[r][c - 1] == BLOCK else visL[r][c - 1]
    for c in range(W - 2, -1, -1):
        if grid[r][c] == EMPTY:
            visR[r][c] = False if grid[r][c + 1] == BLOCK else visR[r][c + 1]
for c in range(W):
    for r in range(1, H):
        if grid[r][c] == EMPTY:
            visT[r][c] = False if grid[r - 1][c] == BLOCK else visT[r - 1][c]
    for r in range(H - 2, -1, -1):
        if grid[r][c] == EMPTY:
            visD[r][c] = False if grid[r + 1][c] == BLOCK else visD[r + 1][c]

ans = 0
for r in range(H):
    for c in range(W):
        if any([visL[r][c], visR[r][c], visT[r][c], visD[r][c]]):
            ans += 1
print(ans)

## F. [Valid payments](https://atcoder.jp/contests/abc182/tasks/abc182_f)

這題有兩種解法。

### 解法 1

題目相當於在問：「所有 $A$ 進制的 $N$ 位數中（允許 leading 0）有幾個數 $r$ 滿足 $r$ 與 $X + r$ 沒有共同不為 $0$ 的 digit」，即 $\forall_{0 \le i \lt N}, r_i = 0 \lor (X + r)_i = 0$。

而這個可以透過 digit dp 求解，因為我們在處理加法，會有進位的問題，所以讓我們從低位數往高位數填數字，而非從高位往低位。

下圖為直式加法示意圖，$c$ 是 carry，$x$ 是 $X$ 的 $A$ 進制，$y$ 是 $X+r$ 的 $A$ 進制。注意我們是在 $A$ 進制底下，當第 $i$ 位達到 $m_i = \frac{A_{i + 1}}{A_{i}}$ 時就會進位。

$$
\begin{array}{r}
&c_3 &c_2 &c_1 &0 \\
&x_3 &x_2 &x_1 &x_0 \\
+\quad
&r_3 &r_2 &r_1 &r_0 \\
\hline
&y_3 &y_2 &y_1 &y_0
\end{array}
$$

其中每一位 $i$ 都滿足：

$$
\begin{align}
y_i &= (c_i + x_i + r_i) \pmod {m_i} \\
c_{i + 1} &= \lfloor \frac{c_i + x_i + r_i}{m_i} \rfloor
\end{align}
$$

設 $dp[i, c]$ 代表填好 $[0, i)$ 這些位的數字時的答案，且第 $i$ 位的 carry 是 $c$。

枚舉 $r_i$ 所有的值（$0 \le r_i \lt m_i$），我們得到遞推轉移：

for i in range(N):
    for c in range(2):
        for r in range(mx[i]):
            val = c + x[i] + r
            y = val % mx[i]
            if r == 0 or y == 0:
                new_c = val // mx[i]
                dp[i + 1][new_c] += dp[i][c]

很可惜這個 dp 會 TLE，我們嘗試優化第三個迴圈，因為 $r_i = 0 \lor y_i = 0$ 的限制，不可能存在太多可行的情況。讓我們將 $r_i = 0 \lor y_i = 0$ 分解成 3 個 disjoint 的條件：

1. $r_i = 0 \land y_i = 0$
2. $r_i = 0 \land y_i \ne 0$
3. $r_i \ne 0 \land y_i = 0$

讓我們看看在什麼情況下各個條件會成立：

1. 將 $r_i = 0 \land y_i = 0$ 代入第 $i$ 位的公式，可以看出僅當 $(c_i + x_i) = 0 \pmod {m_i}$ 時，條件 1 能成立，此時我們轉移至 $dp[i + 1, c_{i+1}]$。
2. 將 $r_i = 0$ 代入第 $i$ 位的公式，可以發現僅當 $(c_i + x_i) \ne 0 \pmod {m_i}$ 時能讓 $y_i \ne 0$，此時我們轉移至 $dp[i + 1, c_{i+1}]$。
3. 將 $y_i = 0$ 代入第 $i$ 位的公式，可以發現僅當 $(c_i + x_i) \ne 0 \pmod {m_i}$ 時能讓 $r_i \ne 0$，且此時一定會有進位發生，我們轉移至 $dp[i + 1, 1]$。

因為條件之間是 disjoint 所以滿足加法原理，我們得到最終的程式：

N, X = map(int, input().split())
A = [int(x) for x in input().split()]

mx = []
for i in range(N - 1):
    mx.append(A[i + 1] // A[i])
mx.append(10 ** 18)

x = []
for a in reversed(A):
    q, X = divmod(X, a)
    x.append(q)
x = x[::-1]

dp = [[0, 0] for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N):
    for c in range(2):
        # r[i] = 0 and y[i] = 0
        if (c + x[i]) % mx[i] == 0:
            new_c = (c + x[i]) // mx[i]
            dp[i + 1][new_c] += dp[i][c]

        # r[i] = 0 and y[i] ≠ 0
        if (c + x[i]) % mx[i] != 0:
            new_c = (c + x[i]) // mx[i]
            dp[i + 1][new_c] += dp[i][c]
        
        # r[i] ≠ 0 and y[i] = 0
        if (c + x[i]) % mx[i] != 0:
            dp[i + 1][1] += dp[i][c]

print(dp[N][0])

### 解法 2

來源：[maspy 的題解](https://maspypy.com/atcoder-%e5%8f%82%e5%8a%a0%e6%84%9f%e6%83%b3-2020-11-08abc-182#toc3)

我們可以將任何 10 進制的非負整數 $n$ 表達成 $A$ 進制：$n_{10} = \vec b_{[A]} = [b_{N-1}, b_{N-2}, \cdots, b_{0}]_{[A]}$，例如第二筆範測：$198_{10} = \vec b_{[A]} = [1, 1, 4, 1, 3]_{[A]}$。

定義函式 $f(\vec b_{[A]}, i)$ 為購買 $\vec b_{[A]} = [b_{N-1}, b_{N-2}, \cdots, b_{0}]_{[A]} = p_{10}$ 元商品的可行花費方法數，且 $b_{i - 1}, b_{i-2}, \cdots, b_{0}$ 都是 $0$，則題目所求為 $f(X_{10}, 0)$。

首先我們考慮基底情況 $f(\vec b_{[A]}, N - 1)$，即商品價格是 $\vec b_{[A]} = [b_{N-1}, 0, \cdots, 0]_{[A]} = (b_{N-1} A_{N-1})_{10}$，此時可行的花費方法數只有一種：付剛剛好的錢，得到找零 0 元，因此 $\forall \vec b_{[A]}, f(\vec b_{[A]}, N - 1) = 1$。

接著考慮一般情況 $f(\vec b_{[A]}, i)$，即商品價格是 $\vec b_{[A]} = [b_{N-1}, b_{N-2}, \cdots, b_{i}, 0, 0, \cdots, 0]_{[A]}$。根據題意，我們花費的金額 $y_{10} = \vec y_{[A]} = [y_{N-1}, y_{N-2}, \cdots, y_0]_{[A]}$ 與找零 $c_{10} = \vec c_{[A]} = [c_{N-1}, c_{N-2}, \cdots, c_0]_{[A]}$ 不能有共同都不為 0 的 digit。

只看第 $i$ 個的 digit，即是 $y_i = 0 \lor c_i = 0$。同時在第 $i$ 位上我們也得滿足「找零 = 花費 - 價格」的關係：$c_i = y_i - b_i \pmod {A_{i + 1}}$。我們可以根據 $b_i$ 分情況討論。

若 $b_i = 0$，則 $y_i = c_i = 0$，$y_i, c_i$ 只有這一種可能，情況轉變成 $f([b_{N-1}, \cdots, b_{i + 1}, \color{orange}{0}, \cdots, 0], i + 1)$。

若 $b_i \ne 0$，則情況有兩種：$y_i = 0 \lor c_i = 0$。若 $c_i = 0$，說明 $y_i = b_i$，花費與價格在這一位上是相同的，可以視為 $b_i = 0$ 的情況，情況轉變成 $f([b_{N-1}, \cdots, b_{i + 1}, \color{orange}{0}, \cdots, 0], i + 1)$。若 $y_i = 0$，說明花費在這一位上是 0，但找零是非 0，這代表我們有向更高一位的數**借位**，因此情況轉變至 $f([b_{N-1}, \cdots, \color{red}{b_{i + 1} + 1}, \color{orange}{0}, \cdots, 0], i + 1)$。

至此整個 dp 就出來了，實作上不需要真的把 $\vec b_{[A]}$ 當成函式的參數，我們使用他的 10 進制，再搭配上 top down 的 dp，程式可以簡單的寫成：

from functools import lru_cache


@lru_cache(maxsize=None)
def f(p, i):
    if i == N - 1:
        return 1
    b_i = p % A[i + 1]
    if b_i == 0:
        return f(p, i + 1)
    else:
        cnt1 = f(p - b_i, i + 1)  # c_i = 0
        cnt2 = f(p - b_i + A[i + 1], i + 1)  # y_i = 0
        return cnt1 + cnt2


N, X = map(int, input().split())
A = [int(x) for x in input().split()]
print(f(X, 0))

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