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

• [solution] 2020-2021 ICPC Northwestern European Regional Programming Contest
  • pA - Atomic Energy
  • pE - Endgame
  • pF - Flight Collision
  • pG - Great Expectations
  • pH - Hot Springs
  • pI - Island Tour
  • pK - Keyboardd

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

pA - Atomic Energy

首先，可以發現到這道題在不考慮時間複雜度的情況下可以用 DP 解決。我們令

$d{p}_i$ 為當查詢為

$i$ 時的答案，

$d{p}_0=0$，可以這樣轉移，所有：

$$d{p}_i=\underset{j\le i,j\le n}{min}d{p}_{i-j}+a_j$$
這樣的時間複雜度是

$O(nC)$，其中

$C$ 為查詢的最大值，顯然無法通過此題。

性質 A1

設

$b$ 是

$1\le i\le n$ 中，使得

$\frac{a_i}{i}$ 最小的

$i$。若任意原子

$c$ 被使用了

$b$ 次，則改為讓

$b$ 原子使用

$c$ 次不會變得更差。

證明

因為

$\frac{a_b}{b}\le \frac{a_c}{c}$，因此

$a_b\times c\le a_c\times b$。

由 性質 A1 可知，每個非

$c$ 的原子至多只會被選到

$c-1$ 次，因此只需預處理前

$(\genfrac{}{}{0ex}{}{n-1}{2})\times (n-1)$ 個 dp 值，剩下的一定會由

$c$ 轉移。

因此對於每個查詢

$k_i$，若他在我們預處理的範圍內，則可以直接使用；否則我們可以找到最小的一個數

$x$ 不大於

$(\genfrac{}{}{0ex}{}{n-1}{2})\times (n-1)$，使得

$k_i-x\equiv 0(\mathrm{mod}m)$，則答案為

$d{p}_x+\frac{k_i-x}{m}\times a_m$。

這樣的時間複雜度為

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

性質 A2

若選擇了

$b$ 個非

$b$ 的原子，則必定可以從這

$b$ 個原子找到一種取法（也就是只選一些被選擇的原子），使得該取法中重量的總和為

$b$ 的倍數。

證明

假設有一個長度為

$b$ 的布林陣列

$z$，第

$z_i$ 項代表「是否有取法的總和

$modm$ 為

$i$」。

並令

$d=[d_1,d_2,\dots ,d_b]$ 代表我們取的任意

$b$ 個非

$b$ 的原子。

若所有的

$d$ 都能使

$z_0$ 為 true，則證畢。用反證法證明，假設存在一種

$d$ 使得

$z_0$ 不為 true，則

$[d_1,(d_1+d_2)\dots (d_1+d_2+\dots d_b)]$（裡面的每一項都要

$modb$） 都不為

$0$。

由鴿籠原理可知

$b-1$ 個格子放

$b$ 個數值，則必定有數值相同，假設

$d_1+d_2+\dots d_i\equiv d_1+d_2+\dots d_j(\mathrm{mod}b)$（

$i<j$） 的話，就代表

$d_{i+1}+d_{i+2}\dots d_j\equiv 0(\mathrm{mod}b)$，矛盾。

由 性質 A2 可知，只要選了不小於

$b$ 個非

$b$ 的原子，則必定可以湊出

$b$ 的倍數，但因為

$a_b$ 的每單位重量的價值一定比所有人都還要好，所以上述提到湊成

$b$ 的倍數的方法，應該全部都要換成

$a_b$。

在最糟的情況下

$b=n$，則只需要預處理

$(n-1)\times n$ 個 dp 值，接著用與前面相同的作法即可。

pE - Endgame

觀察 E1

可以在

$O(n\log n)$ 的時間內，檢查 Alice 是否能走到 Bob（或相反）。

說明

我們枚舉所有 Alice 走的位移，假設對於位移

$(x_i,y_i)$，Alice 走到的新位置是

$p_i=(a_x+x_i,a_y+y_i)$，那我們只要檢查是否存在能夠讓

$p_i$ 走到 Bob 的位移，後面這件事情可以用二分搜達成。

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

性質 E2

Bob 至多只能走到

$\frac{n^2}{2}+n$ 個座標。

證明

假設 Bob 需要走兩步，在最差的狀況中，所有可以走的位移是

$\mathrm{\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

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

觀察 F1

可以在

$O(1)$ 的時間內，計算一對無人機相撞時的時間。

說明

一對無人機

$(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$，那代表它們根本不會相撞。

觀察 F2

可以在

$O(1)$ 且僅用整數的方法，比較兩對無人機相撞時間的先後。

說明

如果我們想要使用整數比較兩對無人機

$(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{array}{rl}\frac{x_b-x_a}{v_a-v_b}& ⪌\frac{x_d-x_c}{v_c-v_d}\\ (x_b-x_a)(v_c-v_d)& ⪌(x_d-x_c)(v_a-v_b)\end{array}$$

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

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

將所有相鄰無人機對墜毀的時間點放入 set，因為 性質 F2 所以 set 動態更新時間複雜度仍然是

$O(n\log n)$。

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

pG - Great Expectations

我們可以在原題加上兩個特技，分別為「

$(t_0,p_0,d_0)=(0,1,0)$」、「

$(t_{m+1},p_{m+1},d_{m+1})=(n,1,0)$」。

令

$d{p}_{i,j}$ 為「從第

$i$ 開始（還沒完成

$i$ 的 trick）到終點，已經用了

$j$ 秒的 delay 的期望總時間」。顯然的，

$d{p}_{m+1,\ast }=0$。

依照題意，可以這樣轉移：

$$\begin{array}{rl}d{p}_{i,j}& =p_i\times ((t_{i+1}-t_i)+d{p}_{i+1,j})\\ & +\{\begin{array}{ll}(1-p_i)\times min(d{p}_{0,0},(t_{i+1}-t_i)+d_i+d{p}_{i+1,j+d_i})& \text{if }j+d_i\le r-n\\ (1-p_i)\times d{p}_{0,0}& \text{otherwise}\end{array}\end{array}$$

這樣的 dp 定義與轉移使得我們必須要從

$m+1$ 做到

$0$，但是中途卻又用到

$d{p}_{0,0}$，這樣的

$dp$ 順序難道是不好的嗎？

性質 G1

令

$x$ 算出來的

$d{p}_{0,0}$ 稱做

$f(x)$。若

$x>f(x)$，則

$x$ 應該要變的更大；若

$x<f(x)$，則

$x$ 應該要變的更小。

證明

先說結論，

$f(x)$ 的圖形應該要是非遞減的，而我們要找到它與

$y=x$ 的交點。

讓我們拆解

$f(x)$ 代表的遞迴式，它形如

$C_1+min(x,C_2+min(x,\dots ))$，這裡的

$C_i$ 是一些常數。

可以發現當

$x$ 變大時，

$f(x)$ 只會變大或不變；當

$x$ 變小時，

$f(x)$ 只會變小或不變。

有了 性質 G1，就可以二分搜這個

$x$，這樣就解決了這道問題。

pH - Hot Springs

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

pI - Island Tour

首先可以

$O(n^3)$ 枚舉所有可能，並在

$O(n)$ 的時間複雜度檢查三個人是否相撞，但這樣時間雜度太糟了。

觀察 I1

我們可以預處理「判斷兩個人

$a,b$ 分別站在

$x,y$ 是否相撞」，這件事可以在

$O(n^3)$ 的時間複雜度解決。

有了 觀察 I1，可以發現原先的

$O(n)$ 的檢查根本可以

$O(1)$ 做出來，只需檢查任一兩個人是否相撞即可。

pK - Keyboardd

如果一個字元

$c$ 的鍵壞掉了，則該字元在

$s$ 的出現次數一定比在

$t$ 的出現次數還要少，統計

$s$ 跟

$t$ 每個字元的數量，再比較即可。