---
title: Asia Seoul 2020-2021 紀錄
tags: solo, icpc
---
## Asia Seoul 2020-2021

[statement](https://codeforces.com/gym/102920/attachments/download/12834/20202021-acmicpc-asia-seoul-regional-contest-en.pdf)

## pA solved - 04:39

大模擬題, 實作上先預處理每對線段的相交情況和位置在模擬就好了

## pB solved - 00:10

枚舉兩個人投出的點數並算有幾種情況是贏的即可

## pC solved - 00:29

首先有apartment complex的點明顯是good place,而對於不是apartment complex的點$V$如果是good place必須要拔掉$V$之後至少有兩個連通塊有apartment complex, 因為對於一個和$V$相鄰的點$U$, 要存在一個apartment complex $X$滿足$d(V, X) < d(U, X)$, 那這個apartment complex不可能會在$U$所在的連通塊

實作上就用DFS算子樹的apartment complex數量就好了, 總體複雜度$O(n)$

## pE solved - 00:50

首先非相鄰數字的數對對difference sequence的貢獻是$0$, 而對於相鄰的數對, 我們可以從$(1, 2), (2, 3) ...$考慮到$(n - 1, n)$, 並維護目前的difference sequence $D$

在考慮數對$(i, i + 1)$時, 如果$D_i = 0$, 那我們可以讓兩次比較$(i, i + 1)$的結果相同/不同來使$D_i$保持不變/變成$1$

如果$D_i = 1$, 則可以變成$0, 1$或$2$(如果$(i - 1, i)$和$(i, i + 1)$的兩輪比較結果是相同的就會變成$0$, 反之是$2$)

## pG solved - 04:46

假設機器人的排列是$1, 2, 3, ..., n$的話, 假設機器人$1$的位置是$X$, 那麼機器人$i$的位置就要是$X + (i - 1)d$, 那麼答案就會是$max_{i = 1}^{n}|pos_i - (X + (i - 1)d)|$, 稍微改變一下式子會變成$max_{i = 1}^{n}|x - (pos_i - id + d)|$可以發現我們要做的其實就是對多個V形函數的max取min, 設$mn = min_{i = 1}^{n}(pos_i - id + d), mx = max_{i = 1}^{n}(pos_i - id + d)$, 可以發現min值一定會出現在$X = (mn + mx) / 2$的地方, 把這個值算出來並帶回去算答案就好了

記得要處理$n, n - 1, n - 2, ..., 1$的排列方式(賽中漏掉這個case吃了一堆penalty QQ)

## pH solved - 02:04

如果要穿過中間位置為$X$的洞的話, 一定要同時穿過上面位在$X - D$的洞和下面$X + D$的洞, 然後就可以發現這東西一臉捲積樣, 把FFT拿出來砸就AC了, 複雜度$O(ClgC)$

## pJ solved - 01:35

考慮一個$n$維向量$vec$, $vec_i$代表連接到第$i$個燈泡的switch有多少個是開的, 很明顯當我們在開第$j$個switch的時候就是把輸入中第$j$ row的向量加到$vec$上, 而我們只在乎$vec$每個component的奇偶性, 所以我們只需要知道模2下的結果, 因此可以維護一個xor basis, 並依序query是否能用這組basis構出$vec_k = 1, vec_l = 0(0 \le k < n, l \neq k)$就好了, 複雜度$O(\frac{n^3}{64})$

## pL upsolved

觀察1: 如果存在$i' < i$滿足$h_{i'} \ge h_{i}$的話, 那$i$是無用的, 對於$j$也有類似的結論, 所以我們要考慮的$h_i, h_j$都會是遞增的

接下來把問題變得直觀一點, 考慮一個平面, 如果對於所有"有用的"位置$k$在$(k, h_k), (k, -h_k)$畫一個點, 並把所有相鄰的點連起來, 可以發現問題可以變成在這個多邊形上找最大矩形

[sample1的圖](https://i.imgur.com/lnMi4tT.jpg)

觀察2: 考慮兩個右下頂點$j', j(j' < j)$, 當左上的頂點$i$上升時, 可以發現由頂點$i, j$構成的矩形面積上升量會比$i, j'$構成的矩形面積上升量多, 因此有轉移點單調的性質($i$上升時, 和$i$構成最大矩形的$j$會非嚴格遞增)

[直覺的證明](https://i.imgur.com/7zg3PYF.jpg)

所以只要套分治優化就可以在$O(nlgn)$的時間內做掉了

## 檢討

這場感覺最痛的地方應該就是pG了, 一開始發現函數圖形有凹性就把三分搜砸下去, 結果吃了一堆penalty, 沒看清楚題目又吃了一堆penalty, 下次吃WA的時候要記得確認一下題述阿...

至於三分搜的部份要記得只能在容許relative error的時候拿出來砸, 像pG這個求rounding的如果答案剛好在rounding的界線附近時很容易爆炸