R1A 直接睡死忘了打
只能打這場有夠不友善ㄉ時間
好久沒在這種CF時段打比賽了，打起來其實滿快樂ㄉ
Results
85 / 100 Pen. Time 00:49:29 Rank 269
| pA | pB | pC |
|---|---|---|
| 25 | 35 | 25 |
| 0:03:24+0 | 0:21:08+0 | 0:49:29+0 |
pA
7/8/10
題敘
給一個 deque<int> ，求每次從左或右取一個數字出來能形成的最大Longest Non-Decreasing Subsequence
Subtask:
- $n \leq 20$ (7)
- $n \leq 100$ (8)
- $n \leq 10^5$ (10)
想法
水題一枚，反正每次抓比較小的取就好了
pB
題敘
有 $n$ 個人，每個人有 $p$ 個值 $a_{ij}$
你有一個值 $x$，初始設為 $0$，你每次操作可以使 $x := x +1$ 或 $x := x-1$
對於第 $i$ 個人，你要讓 $\forall 1 \leq j \leq p, x = a_{ij}$ 至少一次
接著才能執行第 $i+1$ 個人
求完成整個程序需要至少幾次操作
Subtask:
- $n \leq 10, p \leq 3$ (14)
- $n \leq 1000, p \leq 100$ (21)
想法
一個重要的觀察是每執行完一個人， $x$ 一定停留在 $\max\limits_{1 \leq j \leq p}(a_{ij})$ 或 $\min\limits_{1 \leq j \leq p}(a_{ij})$
因此我們只需要對第 $i$ 個人維護 $dp1_i$ 和 $dp2_i$ 分別表示停留在最大值及最小值的狀況就好了
pC
25/15
題敘
互動題
judge端有一個長度為8的01字串 $S$
你每次操作可以給一個長度為8的01字串 $V$，接著judge會將這個01字串任意的環狀位移
位移完後令judge端的字串 $S := S \text{ XOR } V$
接著再回傳目前 $S$ 內 $1$ 的數量
你的目標是在300次操作內讓這個字串變為 00000000
Subtask:
- Judge端的操作是隨機 (25)
- Judge is adaptive (15)
想法
賽中對滿分解沒什麼想法
不過意識到在隨機下，讓字串內 1 的數量減少的機率其實滿高的
像有1個1的情況下，字串 1000000有$\frac18$的機率消掉
2個1的話一個隨機包含2個1的字串會有$\frac1{28}$的機率直接清空，$\frac3{14}$的機率消一個
其實機率好像還不錯，而且1的數量大於4時，直接丟11111111可以保證減少
賽中懶得求確切的機率就丟上去
然後就過ㄌ
滿分解好像會用到環狀平移之後實際上相異的字串很少的性質
不過賽中這時候已經超晚了，也沒有往下想就去睡ㄌ
小結
在去年忘了打Qualification Round之後，今年終於記得ㄌ
結果R1A直接睡過頭沒打到，只打R1C又很危險
就只好打這種半夜場了
結果還是一大堆台灣人???(前1500名有64個)
總之希望今年R2好好打能拿到衣服><