SRM 512 Div1 Easy + Medium

因為這次SRM是$2$的冪，所以題目分數也別出心裁的改為$2$的冪。

Easy: 假設某餐店只開$N$日，每日也賣出$M$款菜式。每日每款菜式的價格都有所不同。這餐廳有點古怪，要求你必須一天只買一款菜式；第$i$天買了第$j$款菜式的話必須在$i+7$天買第$j$款菜式；一旦你在第$i$天沒有光顧的話以後都不可以光顧該餐廳。你有$K$元在手，問最多能光顧這餐廳多少天。

算是比較容易的題。首先問題可以轉化為：能不能連續光顧$k$天？設這函數是$f(k)$的話我們就是求最大的$k$使得$f(k) = true$。當然由於$k$很小，線性枚舉所有$f(k)$即可。那麼判斷答案實在是很容易的–設$v_{i, j}^k$是在這連續$k$天內每星期$i$都買菜式$j$的總支出。判斷$f(k)$則只需檢查\[\sum_{i=1}^7 \min_{1\le j\le M}v_{i,j}^k \le K\]即可。

Medium: 一個泛費波那契數列是指任意正整數$f_0, f_1$為數列的首兩個元素，並且其數列遵從遞迴式$f_k = f_{k-1} + f_{k-2}, k > 1$。任何其子序列則稱為泛費波那契子數列。假設有一個正整數集$S$，當中有$N$個各不相同的整數。題目要求從$S$中取出兩個不相交的子集$A$和$B$，使得$A$和$B$皆為泛費波那契子數列，並且$A$的最大值必須少於$B$的最小值，而且$A$和$B$皆為上升序列。

乍看起來有點難。首先可以想到的是﹕能不能把$S$排序，然後劃分兩個子集$S_{1\cdots p}$、$S_{p+1\cdots N}$並分別在其中找出$A$和$B$？基於$N$不太大的關係，似乎有點可行，而且問題會簡化為從一個集合中找出最長的泛費波那契子數列。這個如何找呢？現在假設在$S$中找出$A$，可以試著想想枚舉。現在從$S$選出$S_i$和$S_j$，$i < j$，找出所在$S$中最長的泛費波那契子數列且必需包含$S_i$和$S_j$。不過包含$S_i$和$S_j$的子數列並非唯一，例如$\{1, 1, \mathbf 3, 5, \mathbf 8, 13\}$和$\{1, \mathbf 3, \mathbf 8, 11, 19\}$。但是可以留意兩件事﹕(1) $S_i$是數列的第幾個數並沒關係，只需要假定它是第一個就行；(2) 如果假定$S_j$是第$k$個數，則這個數列的存在性是唯一的，而且其唯一性是基於$S_i$之後的那個數。那麼我每只需枚舉$S_i$、$S_j$和$k$基本上憑求得序列的第二個數便可以確定序列。記得費波那契數的矩陣公式嗎？其實我們可以用同樣公式求得答案﹕
\[ \begin{bmatrix}F_k \\ F_{k-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}^{k-1} \begin{bmatrix}F_1 \\ F_0\end{bmatrix}\]
其中$F_k = S_j$，$F_0=S_i$而且$F_1$就是要求的答案。假設該式寫成
\[ \begin{bmatrix}S_j \\ F_{k-1} \end{bmatrix} = \begin{bmatrix} a & b \\ c & d\end{bmatrix} \begin{bmatrix}F_1 \\ S_i\end{bmatrix}\]
則可以得到
\[ S_j = aF_1 + bS_i \]
然後可得$F_1 = \frac{S_j - bS_i}{a}$。於是若$F_1$有整數解，並且$F_1 > 0$，則可以憑$S_i, F_1, S_j$求得整條數列，然後利用set找出$S$內包含的所有序列元素，並從出找出最長的子序列。需留意的是不要重覆計算元素，例如$S_i = 1, S_j = 8, k = 4$(假設$k$是以$0$開始)，$F_1=1$。另外枚舉子序列時若$F_1 < S_i$，就算$F_1\in S$也不應算為答案之一，因為題目要求答案序列是上升的。
在預計算$\begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}^k$的情況下，這算法是$\tilde{O}(N^5)$的，但是也能足夠通過System test。至於$k$應該是多少？因為$S_i \le 10^8$，所以$k \le 50$足夠了。