2024 ICPC Asia Taichung Regional Programming Contest

連結：https://codeforces.com/contest/2041
時間：2024 Nov 17, 09:30-14:30
團隊：NYCU_MyGO!!! (SorahISA, ub33, nella17)
成績：10 / 14, Penalty 874, dirt 9% ( A B C D E F G H I J K L M N )

A. The Bento Box Adventure

Tags: N/A

輸入四個 $1 \sim 5$ 之間的相異正整數 $a, b, c, d$ ，請判斷 $1 \sim 5$ 哪個數字沒出現過

$1 \leq a, b, c, d \leq 5$

輸出 $15 - (a + b + c + d)$ 即可。

B. Bowling Frame

Tags: N/A

有 $w$ 個白色瓶子跟 $b$ 個黑色瓶子。你要排成 $n$ 排，滿足第 $i$ 排有 $i$ 個相同顏色的瓶子，請求出 $n$ 的最大值。

測資數量 $\leq 100$ 、 $0 \leq w, b \leq 1 0^{9}$

待補

C. Cube

Tags: `bitmask dp`

找到三個 $1, 2, \dots, n$ 的排列 $⟨ x ⟩, ⟨ y ⟩, ⟨ z ⟩$ 使 $\sum A_{x_{i}, y_{i}, z_{i}}$ 最大。

輸出該最大值就好。

$n \leq 12$ 、 $0 \leq A_{x, y, z} \leq 2 \cdot 1 0^{7}$

待補

D. Drunken Maze

Tags: `bfs`

給定一個 $n \times m$ 的矩陣，其中恰有一個起點跟一個終點，且有些位置是不能行走的牆壁。你每次可以朝著四方位相鄰的格子移動一步，但是你不能連續四步走同樣的方向，請求出起點到終點的最短路徑長度（不存在則輸出 $- 1$ ）。

$n, m \leq 10000$ 、 $nm \leq 200000$ 、邊界都是牆壁

一樣用 BFS 紀錄最短路即可，但狀態要多兩個維度紀錄走了哪個方向（大小為 $4$ ）跟走了幾步（大小為 $4$ ）。

$dis [r] [c] [d] [s]$ 代表抵達 $(r, c)$ 且此前 $s$ 步的方向都是 $d$ 的最短路徑長度。

只要從 queue 裡面 pop 出 $(r_{t}, c_{t}, *, *)$ 就能直接輸出答案。

時間複雜度： $O (nm \cdot 4 \cdot 4)$ 。

E. Beautiful Array

Tags: N/A

請構造一個長度介於 $[1, 1000]$ 、數值界於 $[- 1 0^{6}, 1 0^{6}]$ 的整數陣列滿足其平均值為 $a$ 且中位數為 $b$ 。

$∣ a ∣, ∣ b ∣ \leq 100$

輸出 $- 1000 - b$ 、 $b$ 、 $1000 + 3 a$ 即可。

F. Segmentation Folds

Tags: `top-down dp`, `prime sieve`

有一個區間 $[ℓ, r]$ 跟兩種摺疊操作 $LTR$ 、 $RTL$ ：

$LTR$ ：選擇最大的 $x$ 滿足 $ℓ < x \leq r$ 且 $ℓ + x$ 是質數，並將區間縮小為 $[(ℓ + x) /2, r]$ 。

$RTL$ ：選擇最小的 $x$ 滿足 $ℓ \leq x < r$ 且 $r + x$ 是質數，並將區間縮小為 $[ℓ, (r + x) /2]$ 。

請輸出有幾種摺疊操作的序列可以使最後的區間長度最小。請輸出答案模 $998244353$ 的值。

測資數量 $\leq 10$ 、 $1 \leq ℓ < r \leq 1 0^{12}$ 、 $r - ℓ \leq 100000$

觀察到新的端點 $\frac{ℓ + x}{2}$ 或 $\frac{r + x}{2}$ 乘以 $2$ 之後是質數，於是問題可以被變化為以下模樣：

初始區間是 $[2 ℓ, 2 r]$ 。
$LTR$ ：選擇 $\leq \frac{ℓ + r}{2}$ 的最大質數當作新的 $ℓ$ 。
$RTL$ ：選擇 $\geq \frac{ℓ + r}{2}$ 的最小質數當作新的 $r$ 。

於是可以先篩出區間 $[2 ℓ + 1, 2 r - 1]$ 內的質數。由於每個合數 $a$ 必定有一個 $\leq a$ 的質因數，所以透過預處理 $2 C$ 以下的質數再對區間進行篩選（就跟一般質數篩很像，除了左界要調整到第一個 $> p$ 的 $p$ 的倍數），就能在 $O ((r - ℓ) ln (r - ℓ))$ 時間篩出區間內所有質數。

考慮直接對其進行 top-down 的 DP。質數數量每一 fold 大約會變成一半，於是複雜度大約是 $O (r - ℓ)$ 。

還不會好好證明複雜度，待補。

G. Grid Game

Tags: `vbcc`, `implementation`

有一個 $n \times n$ 的白色棋盤，其中有 $q$ 個垂直的長條被塗成黑色的，保證白色的區塊四方位連通。請求出有多少個位置滿足該位置被塗黑之後白色的區塊不再四方位連通。

測資數量 $\leq 125$ 、 $n \leq 1 0^{9}$ 、 $\sum q \leq 100000$

假設所有格子都被建出來，那麼直接在上面找割點就是答案了。不過本題的格子數量太多，所以要想辦法減少重要點的數量。

待補

H. Sheet Music

Tags: `math`

定義兩個長度皆為 $n$ 個序列 $⟨ a ⟩, ⟨ b ⟩$ 本質相同，若且惟若對所有 $1 \leq i \leq n - 1$ 皆有以下其中一種情況成立：

$a_{i} < a_{i + 1}$ 且 $b_{i} < b_{i + 1}$

$a_{i} = a_{i + 1}$ 且 $b_{i} = b_{i + 1}$

$a_{i} > a_{i + 1}$ 且 $b_{i} > b_{i + 1}$

請問有多少個本質不同、長度為 $n$ 、且每個元素都是 $[1, k]$ 之間的正整數序列？

請輸出答案模 $998244353$ 。

$n \leq 1 0^{6}$ 、 $k \leq 1 0^{9}$

先假設沒有 $k$ 的限制，那麼答案就是 $3^{n - 1}$ 。

再假設沒有 $=$ 的狀況，那麼合法的序列就是所有沒有連續 $k$ 個 $>$ 或 $<$ 的序列，這個序列的數量可以透過 DP 求得。

$f_{ℓ} = i = 1 \sum m i n (k - 1, ℓ) f_{ℓ - i}$

初始狀態為 $f_{0} = 2$ 、目標答案就是 $f_{n - 1}$ ，可以用前綴和 $O (n)$ 計算。

現在考慮多出 $=$ 。顯然 $=$ 可以放在任何地方，所以如果有 $e$ 個 $=$ ，那麼答案就是 $f_{n - 1 - e} \cdot (e n - 1)$ 。

$an s = (e = 0 \sum n - 1 f_{n - 1 - e} \cdot (e n - 1)) - 1$

時間複雜度： $O (n)$ 。

I. Auto Complete

Tags: `trie`

meow

meow

待補

J. Bottle Arrangement

Tags:

給定 $⟨ a ⟩, ⟨ b ⟩$ ，你可以將 $⟨ b ⟩$ 的若干位置減一並將整個 $⟨ b ⟩$ 重新排序，使得

$b_{1} \leq \dots \geq b_{n}$ （ $b$ 是 bitonic sequence）

$b_{i} < a_{i}$ for all $1 \leq i \leq n$

請輸出最少要對多少位置減一，如果全部都減一仍不可能達成，則輸出 $- 1$ 。

$n \leq 500000$ 、 $1 \leq a_{i}, b_{i} \leq 1 0^{9}$ 、 $⟨ b ⟩$ 全部元素皆相異

待補

K. Trophic Balance Species

Tags:

給定一張簡單有向圖，定義一個集合 $S$ 是獨立集若且唯若 $S$ 中的點兩兩不可達。

定義 $a_{u}$ 是從點 $u$ 出發可以抵達的點的數量， $b_{u}$ 是可以抵達點 $u$ 的點的數量。請求出所有 $arg min_{u} ∣ a_{u} - b_{u} ∣$ 。

$n \leq 200000$ 、 $m \leq 400000$ 、最大獨立集大小 $\leq 16$

待補

L. Building Castle

Tags:

給定一個凸多邊形 $C$ ，請找到一個 $18 0^{\circ}$ 旋轉對稱的凸多邊形 $C^{'}$ 使得 $C \oplus C^{'}$ （對稱差）的面積最小。

輸出該對稱差的面積即可。

$n \leq 500$ 、 $∣ x_{i} ∣, ∣ y_{i} ∣ \leq 1 0^{4}$ 、座標皆是整數、沒有三點共線、誤差容許 $1 0^{- 4}$

待補

M. Selection Sort

Tags: N/A

給你一個長度為 $n$ 的序列 $⟨ s ⟩$ ，你可以對前綴跟後綴分別各做至多一次排序（哪個先都可以，也可以不做），對 $k$ 個元素排序的 cost 是 $k^{2}$ ，請求出最小的 cost 使陣列排好序。

$n \leq 1000000$ 、 $0 \leq s_{i} < 2^{31} - 1$

首先可以把 $⟨ s ⟩$ 離散化到 $[1, n]$ ，相同數字就以位置來排序。

先做前綴跟先做後綴的兩種狀況需要分開討論，不過先做後綴再做前綴剛好相當於對 $t_{i} = (n + 1) - s_{(n + 1) - i}$ 先做前綴再做後綴。以下只考慮先做前綴的情況。

假設想要一次排好數字 $[1, k]$ ，那麼前綴操作就要做到 $max_{1 \leq i \leq k} pos_{i}$ 的位置，而因為 $k + 1$ 並沒有保證排好，後綴就要從位置 $k + 1$ 開始排序來把數字 $k + 1$ 移到對的位置上。

不過想排好數字 $[1, k]$ 不一定要做到 $max_{1 \leq i \leq k} pos_{i}$ 的位置。舉例來說，如果 $max_{1 \leq i \leq k} pos_{i} = k = pos_{k}$ ，那麼就只要排到 $k - 1$ 也能保證排好 $[1, k]$ 的數字。

$[3, 2, 1, 4, 5, 7, 6]$ 想排好數字 $[1, 5]$ 可以只對前綴 $[1, 3]$ 排序，但想排好數字 $[1, 6]$ 就需要對前綴 $[1, 8]$ 排序。

實作上（submission）可以在由小到大枚舉 $k$ 時用另一個變數紀錄當前結尾有多少數字滿足前綴 $pos$ 最大值是自己且自己也在正確的位置上。

時間複雜度：一開始需要 $O (n lo g n)$ 離散化，計算過程只要 $O (n)$ 。

N. Railway Construction

Tags:

有一張 $n$ 個點的圖，其中有 $m$ 條邊 $(u_{i}, v_{i})$ 被丟掉了，沒被丟掉的邊 $(u, v)$ 的 cost 是 $a_{u} + a_{v}$ 。

請對 $i = 1, 2, \dots, n$ 求出：不使用點 $i$ 的情況下的最小生成樹 cost，無解則輸出 $- 1$ 。

$n \leq 100000$ 、 $m \leq 100000$ 、 $1 \leq a_{i} \leq 1 0^{9}$

待補

SorahISA's Contest Logs