臨時被抓去打的，給高中生的競賽程式用的比賽。
題目我覺得給高中競賽現役玩挺好的，不過我太久沒碰競賽程式寫得亂七八糟。
(搞不好對高中現役來說過簡單，我就不知道了)
Problem A. 快閃旋風
簡單實作題，看到數字範圍只有 10000 就知道開一條 boolean 陣列就十分充裕了。
最後會落在所有沒有障礙物的點中，離原目標點最近的點。
這行沒看到讓我吃了四個 penalty …
不管實作效率的話，有看到利用 python set 運算來判斷，其實寫起來也很乾淨。
Problem B. Coins
巴斯卡三角形 梯形公式 簡單數學題。
注意一下
輸入很不方便 很奇怪 不明白為什麼要這樣設計。
Problem C. 帶權排序
這題跟 Google Code Jam Qualification Round 2018 Trouble Sort 有異曲同工的感覺。
那題大約是這樣的：
給定一個陣列，大小
，
對他進行變種的氣泡排序：
每次檢查相鄰三個數形成的數組，若尾比頭大則顛倒整個數組。
問陣列排序後的樣子。
關鍵的觀察都是，此種三元數組交換會變成奇數項偶數項互不干擾，
所以將奇數項偶數項各自獨立排序好後合併即可。
回到本題，若已排序的陣列
那一定需要花成本進行調換，也就是
由於三元數組交換不需要成本，我們一定可以找到一種交換方式使得多出來的數字兩兩相鄰。
只要計算兩邊偶數項的組成相差多少即可。
Problem D. Pocker Card
沒寫完…
其實意外滿好寫，本來還以為又要寫什麼德州撲克判斷。
每個撲克牌
對每個以 
重點是要保存 原始牌面/重標號數字/大小順序 彼此的互相對應，我是直接開好幾個 map 維護。
對於移動牌數，只要該撲克牌沒有比他前面所有牌還大就需要移動，也就是要維持前綴極值。
Problem E. 瑪雅金字塔
其實應該是馬雅吧
看到 
但是我太久沒寫了，重新推了一遍，尷尬。
簡單講一下好了：
這題是個範圍超級大的 DP 題目， DP 公式就是：
把連續三項寫出來
轉成轉移矩陣的樣子
![\left[ \begin{matrix} \text{F}(i+3) \\ \text{F}(i+2) \\ \text{F}(i+1) \end{matrix} \right]= \left[ \begin{matrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} \right] \left[ \begin{matrix} \text{F}(i+2) \\ \text{F}(i+1) \\ \text{F}(i) \end{matrix} \right]](https://s0.wp.com/latex.php?latex=%5Cleft%5B+%5Cbegin%7Bmatrix%7D+%5Ctext%7BF%7D%28i%2B3%29+%5C%5C+%5Ctext%7BF%7D%28i%2B2%29+%5C%5C+%5Ctext%7BF%7D%28i%2B1%29+%5Cend%7Bmatrix%7D+%5Cright%5D%3D+%5Cleft%5B+%5Cbegin%7Bmatrix%7D+1+%26+1+%26+1+%5C%5C+1+%26+0+%26+0+%5C%5C+0+%26+1+%26+0+%5Cend%7Bmatrix%7D+%5Cright%5D+%5Cleft%5B+%5Cbegin%7Bmatrix%7D+%5Ctext%7BF%7D%28i%2B2%29+%5C%5C+%5Ctext%7BF%7D%28i%2B1%29+%5C%5C+%5Ctext%7BF%7D%28i%29+%5Cend%7Bmatrix%7D+%5Cright%5D+&bg=ffffff&fg=000000&s=0&c=20201002)
所以有
![\left[ \begin{matrix} \text{F}(N) \\ \text{F}(N-1) \\ \text{F}(N-2) \end{matrix} \right]= \left[ \begin{matrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} \right]^N \left[ \begin{matrix} 1 \\ 0 \\ 0 \end{matrix} \right]](https://s0.wp.com/latex.php?latex=%5Cleft%5B+%5Cbegin%7Bmatrix%7D+%5Ctext%7BF%7D%28N%29+%5C%5C+%5Ctext%7BF%7D%28N-1%29+%5C%5C+%5Ctext%7BF%7D%28N-2%29+%5Cend%7Bmatrix%7D+%5Cright%5D%3D+%5Cleft%5B+%5Cbegin%7Bmatrix%7D+1+%26+1+%26+1+%5C%5C+1+%26+0+%26+0+%5C%5C+0+%26+1+%26+0+%5Cend%7Bmatrix%7D+%5Cright%5D%5EN+%5Cleft%5B+%5Cbegin%7Bmatrix%7D+1+%5C%5C+0+%5C%5C+0+%5Cend%7Bmatrix%7D+%5Cright%5D+&bg=ffffff&fg=000000&s=0&c=20201002)
Problem F. 線段覆蓋問題
求最大覆蓋範圍的類似線段覆蓋問題。
一開始花了一點時間往 greedy 想，想一想發現沒有道理，因為每條線段權重不一樣。
先不管數字範圍會發現他明顯可以 DP ，然後發現有效點數量頂多 
先資料離散化將每個點重標號後作 DP。
大概是個
這樣子的轉移方程。
![\text{DP}[i] = \text{max}_{j, \text{exist segment [i,j]}}\{\text{DP}[j] + (i-j)\}](https://s0.wp.com/latex.php?latex=%5Ctext%7BDP%7D%5Bi%5D+%3D+%5Ctext%7Bmax%7D_%7Bj%2C+%5Ctext%7Bexist+segment+%5Bi%2Cj%5D%7D%7D%5C%7B%5Ctext%7BDP%7D%5Bj%5D+%2B+%28i-j%29%5C%7D+&bg=ffffff&fg=000000&s=0&c=20201002)
Problem G. 硬幣投擲
還沒想。
我數學不好有沒有人要直接教我。
比賽紀錄
| 時間 | 錯誤 | 題號 | 其他 |
|---|---|---|---|
| +6min | +2bug | A | 看錯題目 |
| +10min | B | 基本上都在處理輸入 | |
| +5min | +1bug | A | 還是看錯題目 |
| +23min | +2bug | F | 看到很多人先過就先寫這個了，陣列開太小爆兩次 |
| +20min | +1bug | A | 終於發現自己哪裡看錯題目 |
| +8min | C | ||
| +29min | E | 快速幂早就忘光了，從矩陣重新推 | |
| +25min | D | 寫不完 |
A Coding E. Coli 