# [solution] 2020-2021 ICPC Northwestern European Regional Programming Contest

> [TOC]

> 沒有寫的題目都是隊友寫的
> CodeForces Handle: `temmieowo`
> Email: `[e-mail]`

## [pA - Atomic Energy](https://codeforces.com/gym/103049/problem/A)

首先，可以發現到這道題在不考慮時間複雜度的情況下可以用 DP 解決。我們令 $dp_i$ 為當查詢為 $i$ 時的答案，$dp_0 = 0$，可以這樣轉移，所有：
$$
dp_i = \min_{j \le i,\ j \le n} dp_{i-j}+a_j
$$
這樣的時間複雜度是 $O(n C)$，其中 $C$ 為查詢的最大值，顯然無法通過此題。

:::info
#### 性質 A1

設 $b$ 是 $1 \le i \le n$ 中，使得 $\frac{a_i}{i}$ 最小的 $i$。若任意原子 $c$ 被使用了 $b$ 次，則改為讓 $b$ 原子使用 $c$ 次不會變得更差。

:::spoiler 證明
因為 $\frac{a_b}{b} \le \frac{a_c}{c}$，因此 $a_b \times c \le a_c \times b$。
:::

由 ==性質 A1== 可知，每個非 $c$ 的原子至多只會被選到 $c-1$ 次，因此只需預處理前 $\binom{n-1}{2} \times (n-1)$ 個 dp 值，剩下的一定會由 $c$ 轉移。

因此對於每個查詢 $k_i$，若他在我們預處理的範圍內，則可以直接使用；否則我們可以找到最小的一個數 $x$ 不大於 $\binom{n-1}{2} \times (n-1)$，使得 $k_i-x \equiv 0 \pmod{m}$，則答案為 $dp_x+\frac{k_i-x}{m} \times a_m$。

這樣的時間複雜度為 $O(n^3+q)$ 的時間複雜度解決。但實際上，可以做到比這個時間複雜度更好。

:::info
#### 性質 A2
若選擇了 $b$ 個非 $b$ 的原子，則必定可以從這 $b$ 個原子找到一種取法（也就是只選一些被選擇的原子），使得該取法中重量的總和為 $b$ 的倍數。

:::spoiler 證明
假設有一個長度為 $b$ 的布林陣列 $z$，第 $z_i$ 項代表「是否有取法的總和 $\bmod m$ 為 $i$」。


並令 $d = [d_1, d_2, \ldots, d_b]$ 代表我們取的任意 $b$ 個非 $b$ 的原子。

若所有的 $d$ 都能使 $z_0$ 為 `true`，則證畢。用反證法證明，假設存在一種 $d$ 使得 $z_0$ 不為 `true`，則 $[d_1, (d_1+d_2) \ldots (d_1+d_2+\ldots d_b)]$（裡面的每一項都要 $\bmod b$） 都不為 $0$。

由鴿籠原理可知 $b-1$ 個格子放 $b$ 個數值，則必定有數值相同，假設 $d_1+d_2+\ldots d_i \equiv d_1+d_2+\ldots d_j \pmod b$（$i<j$） 的話，就代表 $d_{i+1}+d_{i+2} \ldots d_j \equiv 0\pmod{b}$，矛盾。
:::

由 ==性質 A2== 可知，只要選了不小於 $b$ 個非 $b$ 的原子，則必定可以湊出 $b$ 的倍數，但因為 $a_b$ 的每單位重量的價值一定比所有人都還要好，所以上述提到湊成 $b$ 的倍數的方法，應該全部都要換成 $a_b$。

在最糟的情況下 $b = n$，則只需要預處理 $(n-1) \times n$ 個 dp 值，接著用與前面相同的作法即可。

## [pE - Endgame](https://codeforces.com/gym/103049/problem/E)

:::success
#### 觀察 E1
可以在 $O(n \log n)$ 的時間內，檢查 Alice 是否能走到 Bob（或相反）。

:::spoiler 說明
我們枚舉所有 Alice 走的位移，假設對於位移 $(x_i, y_i)$，Alice 走到的新位置是 $p_i = (a_x+x_i, a_y+y_i)$，那我們只要檢查是否存在能夠讓 $p_i$ 走到 Bob 的位移，後面這件事情可以用二分搜達成。
:::

根據 ==性質 E1==，我們可以先判斷 Alice 是否能贏。否則 Alice 應該要走到一個 Bob 走不到的地方，然而 ==性質 E1== 並不能做到這件事。

:::info
#### 性質 E2
Bob 至多只能走到 $\frac{n^2}{2} + n$ 個座標。

:::spoiler 證明
假設 Bob 需要走兩步，在最差的狀況中，所有可以走的位移是 $\forall 1 \le i, j \le n, (x_i+x_j, y_i+y_j)$，總共有 $n^2$ 對，但 $(x_i+x_j, y_i+y_j)$ 跟 $(x_j+x_i, y_j+y_i)$ 根本就一樣，因此至多 $\frac{n^2}{2}$ 個可能。

如果只走一步，就有 $n$ 個可能。

至多只能走到 $\frac{n^2}{2}+n$ 種不同的座標。
:::

這代表了我們任意選棋盤上的一格，大概有 $\frac{1}{2}$ 可以選到 Bob 走不到的點，檢查該格是否為 Bob 能走到的點可以用 ==性質 E1== 的方法。

隨機選取 $30$ 格就有 $1 - (\frac{1}{2})^{30}$ 的機率可以選到 Bob 走不到的點，這個機率足夠小。若到最後仍找不到 Bob 走不到的點，就代表 Bob 獲勝，否則可以找到 Alice 走到平手的座標。

## [pF - Flight Collision](https://codeforces.com/gym/103049/problem/F)

這道題我們將直接模擬題目的要求，這裡提醒一下題目有提到「每次相撞只會有恰好兩台無人機」，很好證明每次相撞的一定是相鄰的兩個無人機。

:::success
#### 觀察 F1
可以在 $O(1)$ 的時間內，計算一對無人機相撞時的時間。

:::spoiler 說明
一對無人機 $(a, b)$（假設 $x_a<x_b$）的相撞時間取即為 $\frac{x_{b}-x_{a}}{v_{a}-v_{b}}$。若 $v_a \le v_b$，也就是 $v_a - v_b \le 0$，那代表它們根本不會相撞。
:::

:::success
#### 觀察 F2
可以在 $O(1)$ 且僅用整數的方法，比較兩對無人機相撞時間的先後。

:::spoiler 說明
如果我們想要使用整數比較兩對無人機 $(a, b)$ 跟 $(c, d)$（假設 $x_a<x_b$ 且 $x_c<x_d$）相撞時間的先後，根據 ==觀察 F1==，代表在比較 $\frac{x_{b}-x_{a}}{v_{a}-v_{b}}$ 跟 $\frac{x_{d}-x_{c}}{v_{c}-v_{d}}$ 的大小關係。

如果 $v_a-v_b \le 0$ 或 $v_c-v_d \le 0$，畢竟它們永遠不會相撞，時間記為 $\inf$，可以直接使用條件判斷。

否則若 $v_a-v_b > 0$ 且 $v_c-v_d > 0$，則：

$$
\begin{aligned}
\frac{x_{b}-x_{a}}{v_{a}-v_{b}} &\gtreqqless \frac{x_{d}-x_{c}}{v_{c}-v_{d}} \\
(x_{b}-x_{a})(v_{c}-v_{d}) &\gtreqqless (x_{d}-x_{c})(v_{a}-v_{b}) \\
\end{aligned}
$$

這個不等式可以用整數判斷。
:::

為了模擬題目內容，我們希望可以達到動態更新（因為無人機會相撞）找到相撞時間點最小的相鄰無人機對，這不難想到用 `set` 維護。

將所有相鄰無人機對墜毀的時間點放入 `set`，因為 ==性質 F2== 所以 `set` 動態更新時間複雜度仍然是 $O(n \log n)$。

每次都要找到墜毀時間點最小的無人機對，直到無人機全部都墜毀，或是剩下的無人機對都不會相撞。接著把它刪除，並修復 `set` 維護的狀態，如下圖：


## [pG - Great Expectations](https://codeforces.com/gym/103049/problem/G)

我們可以在原題加上兩個特技，分別為「$(t_0, p_0, d_0) = (0, 1, 0)$」、「$(t_{m+1}, p_{m+1}, d_{m+1}) = (n, 1, 0)$」。

令 $dp_{i, j}$ 為「從第 $i$ 開始（還沒完成 $i$ 的 trick）到終點，已經用了 $j$ 秒的 delay 的期望總時間」。顯然的，$dp_{m+1,*} = 0$。

依照題意，可以這樣轉移：
$$
\begin{aligned}
dp_{i,j}
&= p_i \times ((t_{i+1}-t_i)+dp_{i+1,j})\\
&+
\begin{cases}
(1-p_i) \times \min(dp_{0,0}, (t_{i+1}-t_i)+d_i+dp_{i+1,j+d_i}) & \text{if $j+d_i \le r-n$}\\
(1-p_i) \times dp_{0,0} & \text{otherwise}\\
\end{cases}
\end{aligned}
$$

這樣的 dp 定義與轉移使得我們必須要從 $m+1$ 做到 $0$，但是中途卻又用到 $dp_{0,0}$，這樣的 $dp$ 順序難道是不好的嗎？

:::info
#### 性質 G1
令 $x$ 算出來的 $dp_{0,0}$ 稱做 $f(x)$。若 $x>f(x)$，則 $x$ 應該要變的更大；若 $x<f(x)$，則 $x$ 應該要變的更小。

:::spoiler 證明
先說結論，$f(x)$ 的圖形應該要是**非遞減**的，而我們要找到它與 $y=x$ 的交點。

讓我們拆解 $f(x)$ 代表的遞迴式，它形如 $C_1+\min(x, C_2+\min(x, \ldots))$，這裡的 $C_i$ 是一些常數。

可以發現當 $x$ 變大時，$f(x)$ 只會變大或不變；當 $x$ 變小時，$f(x)$ 只會變小或不變。
:::

有了 ==性質 G1==，就可以二分搜這個 $x$，這樣就解決了這道問題。

## [pH - Hot Springs](https://codeforces.com/gym/103049/problem/H)

陣列排序後可以這樣構造，偶數的情況要注意方向

## [pI - Island Tour](https://codeforces.com/gym/103049/problem/I)

首先可以 $O(n^3)$ 枚舉所有可能，並在 $O(n)$ 的時間複雜度檢查三個人是否相撞，但這樣時間雜度太糟了。

:::success
#### 觀察 I1
我們可以預處理「判斷兩個人 $a, b$ 分別站在 $x, y$ 是否相撞」，這件事可以在 $O(n^3)$ 的時間複雜度解決。
:::

有了 ==觀察 I1==，可以發現原先的 $O(n)$ 的檢查根本可以 $O(1)$ 做出來，只需檢查任一兩個人是否相撞即可。

## [pK - Keyboardd](https://codeforces.com/gym/103049/problem/K)

如果一個字元 $c$ 的鍵壞掉了，則該字元在 $s$ 的出現次數一定比在 $t$ 的出現次數還要少，統計 $s$ 跟 $t$ 每個字元的數量，再比較即可。