[Virtual] BOI 2018

, ,

今年最後一天想起來要更新 Blog
好久沒更新了，慘

Day 1

忘記記開始時間，可能有些微偏差

Problem

  • pA polygon
    給你一張 $N$ 個點的有向圖，每個點都有剛好有一條出邊，
    每條邊可以改動他指向的點，問最少要改多少點使得圖都是兩個點的環。
    不可能輸出 -1。
    $ 2 \leq N \leq 10^5$
    [21] $N \leq 20$
    [25] 整張圖都是環
    [29] 整張圖除了自環以外沒有環
    [25] 無其他限制

  • pB dna
    給你一個長度是 $N$ 的陣列，數字介於 $[0,\,K - 1]$，
    現在有 $R$ 個限制，每個限制是數字是 $B_i$ 的至少要有 $Q_i$ 個，
    問最小滿足條件子陣列的長度。
    $1 \leq R \leq K \leq N \leq 2 \times 10^5$，$0 \leq B_i < K$ 且所有 $B_i$ 相異，$1 \leq Q_i \leq N$
    [16] $N \leq 100$，$R \leq 10$
    [24] $N \leq 4000$，$R \leq 10$
    [28] $R \leq 10$
    [32] 無其他限制

  • pC worm [互動題]
    給你一個大小是 $N \times M \times K$ 的三維陣列，要你找某個點他大於等於他相鄰六格。
    陣列裡的值介於 $[1,\,10^9]$，陣列外的值視同 $0$。
    你最多可以查詢 $Q$ 次。

    Score $N$ $M$ $K$ $Q$
    10 $10^6$ $1$ $1$ $10^4$
    22 $10^6$ $1$ $1$ $35$
    12 $200$ $200$ $1$ $4000$
    19 $1000$ $1000$ $1$ $3500$
    14 $100$ $100$ $100$ $10^5$
    23 $500$ $500$ $500$ $1.5 \times 10^5$

Virtual

0:00

Score: 0 / 0 / 0
看完題目之後，想了一下 A 應該跟 Planet Queries II 很像，推了一些可以 greedy 的性質，
B 看起來是很水的雙指標，
C 是 local minimum，之前遇過一維的但我只能做到 $40$ 次。

1:02

Score: 0 / 100 / 0
多想了一下 A，這時候決定開寫 B 滿分。

1:36

Score: 25 / 100 / 0
寫完 A 滿分之後傳上去 WA，打算先用子題 debug，把環的地方先搞定了。

1:49

Score: 100 / 100 / 0
環搞定就只剩反圖以環為根的樹上最大匹配了，發現是環為 $2$ 要先拿掉，
仔細 debug 後拿到另一個子題，merge 之後就 AC 了。

2:25

Score: 100 / 100 / 10 C 的 subtask 2 壓不下去，決定先開寫 10 分的 subtask 1。

3:35

Score: 100 / 100 / 22 突然發現可以用一列當作一個單位去做 subatsk 3，拿到 12 分。

5:00

Score: 100 / 100 / 22 在想 subatsk 5 的時候想到一個假解，丟上去拿到 WA 之後仔細想想發現爛掉了，
然後原來的做法也沒辦法做 subtask 5，燒雞。

Result

problem
pA polygon 21 25 29 25
pB dna 16 24 28 32
pC worm 10 22 12 19 14
Total 222

檢討

一開始讀題有點太久了，驗好 B 的滿分就該開寫了，
實作要再想清楚一點，A debug 的時間有點太久，
過程中沒什麼看錯題目，也有照著規劃去走，至少還算可以。

Day 2

Problem

  • pA alternating
    給你長為 $N$ 的環狀軌道，上面有 $M$ 條電線，
    問是否可以分成兩類使得各類的聯集是整個環，有則輸出解。
    $ 2 \leq N,\,M \leq 10^5$
    [13] $N \leq 15$
    [20] $N \leq 100$
    [22] $N \leq 1000$
    [19] 沒有跨越 $N \sim 1$ 這塊的電線
    [26] 無其他限制

  • pB genetics
    給你 $N$ 個長度是 $M$ 的字串，僅包含 ACGT。
    要你找出其中一個字串，他跟另外 $N - 1$ 個都相差恰好 $K$ 個字元，
    保證如果找的到就只有唯一一組解。
    $3 \leq N,\,M \leq 4100$
    [27] $N,\,M \leq 100$
    [19] $N,\,M \leq 1800$，字串僅包含 AC
    [28] 字串僅包含 AC
    [26] 無其他限制

  • pC paths
    給你一個 $N$ 個點，$M$ 條邊的簡單圖，每個點有 $K$ 種顏色的其中之一。
    問你有多少簡單路徑上的點顏色都不一樣。
    保證答案 $\leq 10^{18}$。
    $1 \leq N,\,M \leq 3 \times 10^5$，$1 \leq K \leq 5$。
    [23] $N,\,M \leq 100$，$K \leq 4$
    [20] $K \leq 3$
    [27] $K \leq 4$
    [30] $N,\,M \leq 10^5$

Virtual

0:00

Score: 0 / 0 / 0
看起來是三題難題，A 沒有觀察到可以用的性質複雜度隨便都是 $\mathcal O(N^2M^3)$ 左右，
B subtask 1 暴力，2 bitset，其他感覺要用到只有四種字元的性質，
C 不知道怎麼做，BFS 會爆掉。

1:47

Score: 0 / 0 / 70
讀完題之後覺得 A 因為有跨結尾到起頭的狀況不好處理所以先去看 C，
發現可以像做三元環一樣的做法，$K = 2$ 枚舉邊，$K = 3$ 枚舉點，$K = 4$ 枚舉中間那條邊，
前面 debug 了一小段時間，丟上去拿了一次 WA 因為沒開 long long，後來就拿到 70 分了。

1:59

Score: 0 / 0 / 100
接下來看到 $K = 5$ 就做 $K = 3$ 的動作兩次然後用 bitmask 合併就好，
debug 一下子就抓到自己不知道為什麼乘 2，拔掉就拿到 AC 了。

2:16

Score: 0 / 46 / 100
先去把 B 46 寫掉，過程中還忘記 XOR 出來是相異的數量，笨死

2:51

Score: 13 / 46 / 100
後來想到 B 如果把它看成一張圖，相差 $K$ 的連邊，直接透過互相比較數量得到的資訊有限，一定要在比較的時候嘗試得到更多東西，
想了一些跟 hash 有關的東西但沒什麼結論，就去看 A，
A 觀察了一些不知道可不可以 greedy 的性質，結果發現很多地方都有反例，
最後決定把 A 的 subtaks 1, 4 寫掉。

A 13 debug 有點久，結果是自己變數打錯= =

3:05

Score: 32 / 46 / 100
A 19 寫上去之後就過了，因為 A 的 greedy 我完全沒有任何結果， 就決定繼續觀察 B。

5:00

Score: 13 / 46 / 100
最後 B 也沒有做出來，燒雞。

Result

problem
pA alternating 13 20 22 19 26
pB genetics 27 19 28 26
pC path 23 20 27 30
Total 178

檢討

實作還是有點卡，要再練穩一點。
讀題還比上一場慢，要再快一點，但不要為了快而看錯題目。

Final Result

Total: 400
Rank: 9, Silver (Middle)

總檢討

兩場下來的問題主要就是實作還是容易出 bug，以及讀題的速度有點太慢
補了一下題目比較燒雞的就是 Day 2 alternating 的觀察沒有走到對的方向
其他看解除了 Day 1 worm 的 subtask 5 沒有注意到正確性然後做錯一點點
大致上打得還算可以
還有就是需要多加強 greedy 跟隨機的部分