# [2023.02.19] 2023 SWERC Mirror

> SWERC 2022-2023 - Online Mirror
> Contest link: https://codeforces.com/contest/1776

分工：
- 金刀：打模板
- 迺絜：？

> 今天的比賽比較不一樣，重諺代表 `NYCU_LoTaTea` 去比 PK 賽、迺絜大約遲到了 45 分鐘、我打完模板之後在廁所燒雞了 15 分鐘，所以理所當然的就沒打算顧 penalty 了。
> 我原本的打算是先把模板打完，讓迺絜到的時候能夠直接開題，於是我就先去把題本印出來，並在等待印題本的過程中打模板。不過因為太久沒打模板了（而且該剪指甲了），我花了 8 分鐘才敲完模板。
>
> [name=SorahISA]

> 敲完之後刷新記分板發現 AHLF 都有隊伍開出來了，於是就大概看著範測寫完 A，然後去廁所燒雞。
>
> [name=SorahISA]

- 0:15 pA Accepted (+0)

> 因為本來想著迺絜會回來，所以我就從後面到著看回來，直到上完廁所才發現隊友還沒到。
>
> - N：很 ARC 的 DP 題，但是輸出是方案數取 $\log$ 感覺有點怪。
> - M：給一棵樹，輪流拔葉子，先手想最大化拔的 index 最大值。
> - L：給定 $p_a + p_b$、$m_a + m_b$、$a$、$b$，問 $p_a \cdot a + p_b \cdot b = m_a \cdot a + m_b \cdot b$ 有沒有非負整數解。
>
> 回來之後因為 H 的人數最多所以先看 H，本來想說是跟 LIS 有關，不過範例畫不出來所以覺得是讀題出了問題。重看了幾次之後其實還是不太理解給的順序，但是看著範測理解出答案的 pattern 就寫掉了。
>
> [name=SorahISA]

- 0:47 pH Accepted (+0)

> 迺絜來了之後我把 L 丟給他解，我去看 F。
>
> - F：給定一張無向連通圖，請把邊著色使得只取任意一色的邊都不連通，但任取兩種顏色的邊都連通。
>
> 直覺上就是把其中一個點孤立出來看，這樣就被分成是不是完全圖的 case 了。把構造方法寫下來跟迺絜講過確定是好的之後就直接開寫。
>
> [name=SorahISA]

- 1:06 pF Accepted (+0)

> 接下來因為在台灣 ICPC List 裡面只剩 GL 有人開，所以我去看 G。
>
> - G：給定一個長度 $2n-1$ 的 $\texttt{WB}$-字串，請找到任意一個 $x$ 使得至少有 $n$ 個 substring 包含恰 $x$ 個 $\texttt{W}$。
>
> 直接 claim 答案是所有長度 $n$ 的 substring 中的最大值，不過被迺絜丟回來叫我先證明一下。
> 證明時一度以為自己在唬爛，不過最後發現最大值右邊的每個位置都可以當作右界，左邊的每個位置都可以當左界，所以至少可以找到 $n$ 個區間。
> 確定證明沒問題之後就快速的寫完上傳，順利的拿到 AC。
>
> [name=SorahISA]

- 1:20 pG Accepted (+0)

> 迺絜也推出了 L 的判斷式，我在實作時少判斷了整除的條件，還好範測夠強才避免吃 penalty。
>
> [name=SorahISA]

> 基本上把 L 的題目看成垂直直線的焦點，把點斜式列出來找整數解就做完了。
>
> [name=迺絜]

- 1:37 pL Accepted (+0)

> 之後，我去看了互動題 C、迺絜則是在想 B。
> 其中，迺絜的想法寫出來之後會變成區間 DP，不過因為每個位置的狀態都是 $(x, y, cost)$，我們一直卡在怎麼確定兩個狀態會可以直接被比較出來優劣性。
> 互動題我們嘗試構造先手跟後手的策略，先手的策略直觀上是取長到短，但還不確定選什麼區間會最好；後手的策略直觀上是讓剩下的區間長的越短越好。
>
> [name=SorahISA]

- 2:20 嘗試模擬 pC

> 於是我們讓先手每次都取最長的區間的最左邊，直接寫 code 模擬之後發現反而是後手的策略在範例 2 就會爛掉，燒雞。
>
> [name=SorahISA]

- 3:05 開始寫 pB

> 迺絜把式子推的差不多了之後就開始寫 B，我就去開剩下的題目來看。>
> - J：會有 $100 \cdot 2^{100}$ 的點的大圖論題。
> - I：每次輪流取凸包上的三角形，目標是取的面積 $\le$ 一半，互動 game 題。
> - D：某種排程題。
> - K：期望值數學題。
>
> DK 一點想法都沒有，我就從更多人開的 J 開始想。
>
> [name=SorahISA]

> 把 J 的圖畫出來之後，會發現如果是樹，或是在只有兩種顏色的情況下答案都會很簡單，但是有三種顏色圖就會變的很混亂。
> 畫了許久之後發現我可以利用到 hypercube graph 的性質，也就是 $(v_x, v_y) \in E \implies |\text{popcnt}(x) - \text{popcnt}(y)| = 1$ 來縮減圖的大小。
> 做法是把所有相同 $\text{popcnt}(v_s) = cnt$ 的點縮成一個新點 $v_{cnt}$ 來一起 bfs，因為同色顯然 $(v_{cnt}, u_{cnt})$ 一一相鄰，而異色也會有 $(v_{cnt}, u_{k-cnt})$ 一一相鄰。這樣就可以對原圖的每個點建出 $k+1$ 個點再從所有 $v_0$ 出發找圖的直徑。
> 跟迺絜確認了想法沒問題之後就花了 13 分鐘收掉。
>
> [name=SorahISA]

- 3:57 pJ Accepted (+0)

> 基本上因為我們推出來的狀態很複雜，所以好好小心實作花了一些時間。中間還有因為沒有好好把高度截掉導致範測出了一點狀況。後來好好把正確的高度還有 cost 算對以後就做完了。
>
> [name=迺絜]

- 4:37 pB Accepted (+0)

> 最後輪流想著 C 跟 I，我在 4:43 的時候 claim 說「每次切最小的感覺就會讓對手只能吃更大的」，在紙上畫了一些都感覺正確，但是證明不出來。
> 嘗試證明到一半，我發現已經 4:51，剩下不到 10 分鐘了，就決定先上去寫看看。
> 可惜的是因為對環狀的東西實作不熟，直到 5:01 才把 code 寫出來 .\_.
> 賽後上傳因為沒有改 `endl` 吃了一個 IDLE，改掉就拿到 AC 了 .\_.
>
> [name=SorahISA]

- 5:01 pI Too Late (Idleness Limit Exceeded)
- 5:02 pI Too Late (Accepted (+1))

## 結果

- Rank: 92 / 1933
- AC: 7 / 14 (`AB...FGH.J.L..`)
- Penalty: 819

## 燒雞

- 最後一小時如果有 AC 題目又沒有累積著有想法還沒寫的題目，就應該要去積極的唬爛。
- 高中隊伍開了 `ABCD.FGHIJ.L..`，感覺到了強烈的實力差距。感覺就算加上重諺也只會讓我們開 B 更快，然後除了 I 可能還可以多過 C (?)
- B 的官解合併只有一行，我們少考慮了（或是考慮太多了）導致轉移式寫了三個超長的函式。實際上因為兩坨東西的最左跟最右一定是兩個斜直線，所以根本不用管合併的點，只要好好算 cost 並且透過最左最右的積木位置來判斷高度是否要截掉就好。