---
tags: Programming Contest
---

# AtCoder Beginner Contest 178 題解

[題目連結](https://atcoder.jp/contests/abc178/tasks)

## 心得

第三題卡了我好久好久，最後跑去先解第四題，10 分鐘 AC，才又回來想第三題。高中就知道我排列組合不好，現在還是不會，我真是太失敗了 ੨( ･᷄ ︵･᷅ )ｼ，我到底該正著算呢？還是反著算呢？這樣算到底會不會重覆算呢？是不是要枚舉 0 的數量，用重複組合？第五題沒解出來，聽說是經典題，讓我好好研究研究。

## A, B

ʘ‿ʘ

## C. Ubiquity

一開始的想法是正著算：在 N 個位置中任取兩個位置，放 0 與 9，其他位置數字任填，所以方法數是 ${N \choose 2} \cdot 2! \cdot 10^{N-2}$，然後範測一直過不了，換了各種方式都還是不行。

等到第四題解完回來，決定看看 N=3, N=4, N=5 時的答案是多少，寫了個程式爆開，答案分別是 54, 974, 140670 就知道正著算會錯，上述式子在 N = 5 時會產出 3 個 0。也想到了在 N = 3 時，pattern [0, 9, x] 與 [0, x, 9] 會重覆算到相同序列。

反著解，即用扣的，再應用排容：

答案
= 有出現 0 **且** 有出現 9 的序列個數
= 全部序列個數 - 「沒出現 0 **或** 9 的序列個數」
= 全部序列個數 - 「沒出現 0 的序列個數 」- 「沒出現 9 的序列個數」+ 「沒出現 0 **且** 沒出現 9 的序列個數」

數學式即為：

$$
(10^N) - (9^N) - (9^N) + (8^N)
$$

N = int(input())
M = 10**9 + 7
ans = pow(10, N, M)
ans = ans + M - pow(9, N, M)
ans = ans + M - pow(9, N, M)
ans = ans + pow(8, N, M)
ans = ans % M
print(ans)

## D. Redistribution

我的解法跟其他人似乎不太一樣。

把 S = 1~9 的所有序列畫出來，會發現數字 `i` 的那些序列，以序列首項來分類會有規律：

1. 首項為 `3`，剩餘序列是數字 `i - 3` 的那些序列
2. 首項為 `4`，剩餘序列是數字 `i - 4` 的那些序列
3. ...
4. 首項為 `i - 3`，剩餘序列是數字 `3` 的那些序列
5. 序列 `[i]`

於是，令數字 $i$ 的序列個數為 $f(i)$，那 $f(i) = f(i - 3) + f(i - 4) + ... + f(3) + 1$，其中 $f(3) = f(4) = f(5) = 1$。建個 dp 表格求出 $f(S)$ 即可，時間複雜度為 $O(S^2)$，雖然可以另外維護 dp 的前綴和來取代加總部份的計算，讓整體時間變成 $O(S)$，但這題 $S$ 很小直接寫下去即可。實作上，記得特判 $S < 6$ 的那些情況。

$O(S^2)$: 76ms, pypy

N = int(input())
M = 10**9 + 7

if N < 3:
    print(0)
elif N < 6:
    print(1)
else:
    dp = [0] * (N + 1)
    dp[3] = 1
    dp[4] = 1
    dp[5] = 1
    for i in range(6, N + 1):
        dp[i] = sum(dp[3:i - 3 + 1]) + 1
        dp[i] %= M
    print(dp[-1] % M)

$O(S)$: 63 ms, pypy

N = int(input())
M = 10**9 + 7

if N < 3:
    print(0)
elif N < 6:
    print(1)
else:
    dp = [0] * (N + 1)
    dp[3] = 1
    dp[4] = 1
    dp[5] = 1
    P = dp[3]
    for i in range(6, N + 1):
        dp[i] = (P + 1) % M
        P = (P + dp[i - 2]) % M
    print(dp[-1] % M)

## E. Dist Max

網上各種題解都想不通，我理解點對 $(x_1, y_1), (x_2, y_2)$ 的曼哈頓距離**在 $x_1 \ge x_2, y_1 \ge y_2$ 的情況下**可以簡化成 $max(x_1 + y_1) - min(x_2 + y_2)$，但怎麼可以拿**所有點對**的 $x+y$ 的最大值減最小值（看到題解的程式都是這樣寫的），就說是一組可能的答案呢？該推論是有條件的，點對必須滿足 $x_1 \ge x_2, y_1 \ge y_2$！這中間一定少了什麼。

直到剛剛，我看到 [lucifer1004](https://codeforces.com/blog/entry/82566?#comment-695506) 的[題解](https://cp-wiki.vercel.app/tutorial/atcoder/ABC178/)，才恍然大悟，是因為可以將絕對值函數轉成 max 函數。

知道這個事實上，透過一些代數運算，我得到我可以理解的題解：

### 引理 1

$|a| = max(-a, +a)$

### 引理 2

平面上任兩點 $(x_i, y_i), (x_j, y_j)$ 的曼哈頓距離 $|x_i - x_j| + |y_i - y_j|$ 是 $max(u_i - u_j, v_i - v_j, v_j - v_i, u_j - u_i)$，其中 $u_i = x_i + y_i, v_i = x_i - y_i$。

$$
\begin{align}
&|x_i - x_j| + |y_i - y_j| \\
&= max(x_i - x_j, x_j - x_i) + max(y_i - y_j, y_j - y_i) \\
&= max(
(x_i - x_j + y_i - y_j),
(x_i - x_j + y_j - y_i),
(x_j - x_i + y_i - y_j),
(x_j - x_i + y_j - y_i)
) \\
&= max(
((x_i + y_i) - (x_j + y_j)),
((x_i - y_i) - (x_j - y_j)),
((x_j - y_j) - (x_i - y_i)),
((x_j + y_j) - (x_i + y_j))
) \\
&= max(u_i - u_j, v_i - v_j, v_j - v_i, u_j - u_i)
\end{align}
$$

### 推導

題目所求是要找出點對的最大距離，寫成最佳化的型式：

$$
\begin{align}
&\max_{0 \le i \lt N, 0 \le j \lt N} |x_i - x_j| + | y_i - y_j| \\
&= \max_{0 \le i \lt N, 0 \le j \lt N} max(u_i - u_j, v_i - v_j, v_j - v_i, u_j - u_i) \\
&= max(
\max_{0 \le i \lt N, 0 \le j \lt N} (u_i - u_j),
\max_{0 \le i \lt N, 0 \le j \lt N} (v_i - v_j),
\max_{0 \le i \lt N, 0 \le j \lt N} (v_j - v_i),
\max_{0 \le i \lt N, 0 \le j \lt N} (u_j - u_i)) \\
&= max(
(\max_{0 \le i \lt N} u_i - \min_{0 \le j \lt N} u_j),
(\max_{0 \le i \lt N} v_i - \min_{0 \le j \lt N} v_j),
(\max_{0 \le j \lt N} v_j - \min_{0 \le i \lt N} v_i),
(\max_{0 \le j \lt N} u_j - \min_{0 \le i \lt N} u_i))
\end{align}
$$

其中 $\max_{0 \le i \lt N} u_i$ 與 $\max_{0 \le j \lt N} u_j$ 是同一個東西，$\max_{0 \le i \lt N} v_i$ 與 $\max_{0 \le j \lt N} v_j$ 是同一個東西，以此類推。我們可以把 $j$ 完全換成 $i$，最後得到：

$$
max(
(\max_{0 \le i \lt N} u_i - \min_{0 \le i \lt N} u_i),
(\max_{0 \le i \lt N} v_i - \min_{0 \le i \lt N} v_i)
)
$$

這個式子可以在 $O(N)$ 時間求出。佩服自己想出把最佳化的 $\max$ 往內移、把斜體的 $max$ 往外提！哇哈哈哈 ─=≡Σ((( つ•̀ω•́)つ 網上都沒人說到這個部份。但我認為有了這個，整個推導才是合理的，才會變成求 $u, v$ 的最大值與最小值。

N = int(input())
xs, ys = [], []
for _ in range(N):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
U = [x + y for x, y in zip(xs, ys)]
V = [x - y for x, y in zip(xs, ys)]
ans = max([max(U) - min(U), max(V) - min(V)])
print(ans)

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