# Meteor Coding Cup Round #4

臨時被抓去打的，給高中生的競賽程式用的比賽。
題目我覺得給高中競賽現役玩挺好的，不過我太久沒碰競賽程式了打得很爛。
(搞不好對高中現役來說過簡單，我就不知道了)

## Problem A. 快閃旋風
簡單實作題，看到數字範圍只有 10000 就知道開一條 boolean 陣列就十分充裕了。
> 最後會落在所有沒有障礙物的點中，離原目標點最近的點。

這行沒看到讓我吃了四個 penalty ...

不管實作效率的話，朋友有用 python set 運算來寫，寫起來可讀性還滿高，
果然沒競賽底子腦袋思考方式差很多？

## Problem B. Coins

巴斯卡三角形 梯形公式 簡單數學題。
注意一下\\(10^{10}\\)有 int 溢出問題就好。
輸入很不方便 很奇怪 不明白為什麼要這樣設計。

## Problem C. 帶權排序
這題跟 Google Code Jam Qualification Round 2018 Trouble Sort 有異曲同工的感覺。
那題大約是這樣的：
> 給定一個陣列，大小 \\(\leq 10^{5}\\) ，
> 對他進行變種的泡泡排序，即每次看相鄰三個的頭尾大小，若逆序則把它們顛倒。
> 求排序後的陣列模樣。

關鍵的觀察都是，此種三元數組交換會變成奇數項偶數項互不干擾，
所以將奇數項偶數項各自獨立排序好後合併即可。

回到本題，若已排序的陣列\\(A'\\)中的偶數項和\\(A\\)中的偶數項組成不同，
那一定需要花成本進行調換。
進一步發現由於三元數組交換不需要成本，只要計算兩邊偶數項的組成相差多少即可。

## Problem D. Pocker Card
沒寫完...
其實意外滿好寫。
對每個撲克牌 \\((c,n)\\) 以 \\(n\times100+26-\text{ord}(c)\\) 重標號後排序即可。
對於移動牌數，只要該撲克牌沒有比他前面所有牌還大就需要移動，也就是要簡單維持前綴極值。

## Problem E. 瑪雅金字塔
~~其實應該是馬雅吧~~
看到 \\(10^{18}\\) 就要想到矩陣快速冪。
但是我太久沒寫了，重新推了一遍，尷尬。
簡單講一下好了：

\\(\text{F}(i+3)=\text{F}(i+2)+\text{F}(i+1)+\text{F}(i)\\)
把連續三項寫出來

\\(\text{F}(i+3)=\text{F}(i+2)+\text{F}(i+1)+\text{F}(i)\\)
\\(\text{F}(i+2)=\text{F}(i+2)\\)
\\(\text{F}(i+1)=\text{F}(i+1)\\)

轉成轉移矩陣的樣子

$$
\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]
$$

所以有

$$
\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]
$$

## Problem F. 線段覆蓋問題
求最大覆蓋範圍的類似線段覆蓋問題。
資料離散化後DP即可。

大概是個

$$
\text{DP}[i] = \text{max}_{j, \text{exist segment [i,j]}}\{\text{DP}[j] + (i-j)\}
$$
這樣子的轉移方程。

## Problem G. 硬幣投擲

還沒想