# [solution] 2019-2020 ACM-ICPC Latin American Regional Programming Contest

> [TOC]

## [pB - Build the Perfect House](https://codeforces.com/gym/102428/problem/B)

:::info
#### 性質 B1

答案是否大於等於某個數值 $x$ 具有單調性。
:::

有了 ==性質 B1==，我們就可以二分搜某個 $mid$ 代表正方形的半邊長，並檢查該半邊長是否有辦法找到一種旋轉使得所有給定的點都不會被蓋到。

:::success
#### 觀察 B2

每個給定的點，都可以用一個開區間 $(\theta_l, \theta_r)$ 代表當正方形旋轉 $(\theta_l, \theta_r)$ 之間的角度時，會被覆蓋到。

:::spoiler 說明
以圖片為例，若正方形旋轉的角度嚴格大於紅線與橘線的夾角並嚴格小於紅線與綠線的夾角，則就會發生重疊。

若一個點與原點的長度 $L<mid$，則該點無論如何都會被覆蓋到；若 $L>\sqrt{2mid}$，則該點一定不會被覆蓋到。
:::

根據 ==觀察 B2==，我們只要檢查所有旋轉的區間是否都被覆蓋到。實作上，可能會將角度限制在 $[0, \frac{\pi}{2})$，這樣比較好處理。因為上面的區間都是開區間，可能要特判是否有覆蓋到 $0$ 或 $\frac{\pi}{2}$ 左邊一點。

筆者實作方法是對區間做差分，做完差分後前綴和，若某個非開頭結尾的時間點數值為 $0$，就代表不是所有旋轉的區間都被覆蓋到。特別的，差分的數值一樣，要讓右區間排在左區間前面，因為所有東西都是開區間。

## [pF - Fabricating Sculptures](https://codeforces.com/gym/102428/problem/F)

轉化一下題目從下到上一層一層疊方塊，最下面一層的大小必須為 $S$，上面一層用的方塊用的數量不能多於下面一層。

令 $dp_{i,j}$ 為「總共有 $i$ 堆，還可以用 $j$ 個方塊，**每一堆不一定要用完**」。因為最下面一層一定要取，所以我們的所求是 $dp_{S,B-S}$。

這樣的狀態會遇到三個狀況：
1. 最下面一列都是方塊，刪掉最下面一列，變成子問題。
2. 最左邊一行沒有方塊了，刪掉最左邊一行，變成子問題。
3. 最右邊一行沒有方塊了，刪掉最右邊一行，變成子問題。

但是 (2.) 跟 (3.) 形成的子問題有可能重複，又就是左右一行同時都沒有方塊，因此要用排容處理掉。

根據上面的狀況，可以列出這樣的轉移：
$$
dp_{i,j}=
\begin{cases}
0 & \text{if $i<0$ or $j<0$}\\
1 & \text{if $j=0$}\\
dp_{i,j-i} + 2dp_{i-1,j} - dp_{i-2,j} & \text{otherwise}\\
\end{cases}
$$

## pH

令 $dp_{a, b, c}$ 為當 Alice 是先手，且分數為 $a$，Bob 的分數為 $b$ 時，這回合 Alice 已經累計了 $c$ 點的加分時的勝率。

若 $a+c>75$，則 $dp_{a, b, c} = 0$；若 $a+c=75$，則 $dp_{a, b, c} = 1$；若 $a+c=74$，則 $dp_{a, b, c} = 0$。

$$
dp_{a, b, c} = \max(1-dp_{b,a+c ,0},\frac{1}{6} (1-dp_{b,a,0})+\frac{1}{6}\sum_{i=2}^{6}(dp_{a,b,i+c})
)
$$

---
---
---
---
---
---
---
---
---
---
---
---

<!-- ## [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}
$$

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