###### tags: `Competitive Programming`

<style>
.lv1 {
color: #e33d3d;
font-weight: bold;
}
.lv2 {
color: #e89a13;
font-weight: bold;
}
.lv3 {
color: #bfad0b;
font-weight: bold;
}
.lv4 {
color: #1ec93b;
font-weight: bold;
}
</style>

# 2021 全國賽模擬賽 賽後檢討

## 比賽資訊
- [**計分板**](https://contest.nhspc.cc/ranking/Ranking.html)


## 比賽結果

### Submissions


### Final Score／Rank


## 比賽過程

幾乎沒打過 5hr OI，於是直接沿用 3hr OI 的打法，先花時間把所有題目掃過一次。

大概讀了半個小時，後面幾題沒仔細研究就想開始寫 code 了。

對題目大致上的理解：

> **pA**：簽到題，4 次排序 + O(n) 掃過一次算答案，出到 $10^6$ 明顯就是要卡 map，結果真的一堆人被卡。
>
> **pB**：拓樸排序。
>
> **pC**：單調隊列 + 不難的數學。
>
> **pD**：沒想法，但看到 53 分的限制大概猜有 $O(n^2)$ 的作法。
>
> **pE**：感覺有點煩躁的實作，而且題敘似乎怪怪的，應該是「後面 $k$ 個人各自往前 $A_i$ 格」，題本寫 $A_i - k$。
>
> **pF**：從這題開始，後面的題目我就沒認真看了，這題搞懂題意後，發現還是沒想法。
>
> **pG**：題敘很短，但我不會數學。
>
> **pH**：tag 應該是 dp，但我沒認真想。
>
> **pI**：題目不難懂，但一點想法都沒有，看了一下暴力只有 7 分，22 分是序列的版本。

打好模板就開寫 pA，中途忘記棋子不能跨過障礙物，算答案的時候把 $k-1$ 寫成 $C^k_2$，抓蟲抓好一陣子才發現。

一發 AC。

<span class="lv4">00:59 pA 100</span>

之後確定 pB 想法是對的就開掉了。

<span class="lv4">01:08 pB 100</span>

去上個廁所，休息了 3 分鐘，回來就開始寫 pC。

最後推數學式的時候又花了不少時間，看來智力還沒恢復。

<span class="lv4">01:50 pC 100</span>

休息之後開始想 pD，在上廁所的時候想到 $m$ 個出拳方式是各自獨立的，轉化一下題目後，發現了 $O(nm)$ 的 DP 作法。

令 $dp[i][w]$ 為決定好前 $i$ 個位置的拳法，得分能否為 $w$（其中 $w$ 的值域介於 $-n \sim n$ 之間），標準的背包問題。

但我一直在想有沒有複雜度更優的做法，閃過二分搜答案的想法但馬上排掉這念頭，因為顯然沒有任何單調性。

最後決定先撈 53 分。

開開心心寫完 DP 後才發現，幹忘記還要回溯答案，於是又修修改改，前後寫了快一小時。又在耍智障 = ="。

<span class="lv1">02:44 pD 0</span>

無解的時候把 `return;` 寫成 `exit(0);`，改一下就 53 分了。

<span class="lv3">02:48 pD 53</span>

接下來是整場犯下最大的錯誤。

53 分拿到了，但我看到只有最後 4 筆 TLE 就一直告訴自己繼續拿滿，告訴自己再多壓一下常數會過。

反正又開始腦衝亂改 pD 的 code，也不管後面的題目有多少分可以撈。

<span class="lv3">03:18 pD 53</span>
<span class="lv2">03:22 pD 14</span>
<span class="lv2">03:25 pD 6</span>
<span class="lv1">03:28 pD 0</span>
<span class="lv1">03:33 pD 0</span>
<span class="lv1">03:35 pD 0</span>
<span class="lv3">03:37 pD 53</span>
<span class="lv3">03:39 pD 53</span>

我到底在幹嘛...

結論是 bitset 真的可以過，只是我現在覺得我沒過是因為回溯的常數沒有壓掉。

其實本來有想過可以開兩個 bitset 存回溯值（只有 `R/P/S` 三種），這八成也是對的，但我賽中不寫就是不寫，硬要跑去改一些無關緊要的地方，最後又浪費了快一個小時。

這時候才意識到剩不到 80 分鐘，馬上接回理智線，然後繼續往下想題目。

pE 總算看懂，但還是覺得有點煩，pF 依舊沒想法，pG 只會 5 分，pH 還是看不懂，pI 沒想法，而且暴力感覺有點難寫而且只有 7 分我連碰都不想碰。

這時候開始有點慌了，總覺得這樣下去會一分都拿不到，絕望之際突然靈光一閃，想到 pE 大概的作法，這時候我決定集中腦力思考 pE。

思考大概 20 分鐘後，發現前面有 team 被 pop 掉的時候，假設 pop 掉 $r$ 個人，後面所有 size 大於 $r$ 的人都會被旋轉 $r$ 次，其他人完全無影響。

所以可以用值域 BIT 維護「每次從隊伍中刪除的人數」的次數，大於 $max\{A_i\}$ 的可以忽略。

並且預處理前綴和，每次詢問第 $k$ 個人是誰就先對前綴二分搜，搜 $k$ 在哪個隊伍裡面，接著用 BIT 查詢這個隊伍被旋轉了幾次（`bit.query(a[team]-1)`），就可以知道 $k$ 是誰。

實作意外滿順的，雖然我還是寫了半小時 = ="

<span class="lv4">04:38 pE 100</span>

剩 20 分鐘只能撈最水最好寫的分數。

發現 pG 5 分語法分，馬上撈掉。

<span class="lv2">04:47 pG 5</span>

22 分感覺欠三分搜，沒有驗過就開寫，結果還真的是這樣。

<span class="lv2">04:56 pG 22</span>

:::info
**Score: 480/900, Rk: 15**
:::

## 賽後檢討

北市賽後都在搶救學分，段考完後發現已經兩個禮拜沒寫 code 了，所以我也不期望這場會打得多好。

賽中發現思考、實作都滿卡的，前面的水題不應該寫那麼久。

不過最可悲的應該是第 3 個小時了吧，一直想拿 pD 滿分還堅持不寫對的做法，腦袋不知道被什麼東西卡到，又是跟北市賽犯一樣的錯誤。

打完發現有 Rk.15，其實覺得還行，從高一 Rk.69 $\rightarrow$ 高二 Rk.27 $\rightarrow$ 高三 Rk.15，發現底力有在進步，還滿開心的。

不過這次一堆人裝弱／沒打，實際上可能 Rk.20~30 ，就算進了全國賽，大概也只能拿個四等獎吧。但我終究是沒進，終究沒辦法穿到全國賽的 T-shirt，終究沒辦法當個全職競賽選手。剩 47 天，還是認命去讀學測吧，這陣子應該不會再練競賽了。