農場例行賽 #27 超不負責任快速講評

Problem A --- Longly Dreamoon 3

若沒有把非遞增或非遞減的序列排除，這題就超簡單的，所以就加上了把非遞增和非遞減序列排除的條件，但似乎這樣改後難度就高了很多...

首先，若 $N = 2$ 或全部的數都一樣，則輸出 -1。

接著，不妨假設題目給你的序列是非遞減數列，也就是 $a_1 \le a_2 \le \ldots \le a_N$，並令 $d_i$ = $a_{i+1} - a_i$。而我們想要輸出的序列必須滿足存在某相鄰兩數 $= \displaystyle\min_{i=1 \sim N-1} d_i$。

於是呢...我們就稍微修改一些原本的非遞減序列，把第一個數移到最後面或把最後一個數移到最前面。第一個序列相鄰兩數的差會保留 $d_2, d_3, \ldots, d_N$，第二個序列會保留 $d_1, d_2, \ldots, d_{N-1}$，所以這兩個序列一定有一個是我們要的答案。

P.S. 此篇故事純屬虛構， Dreamoon 沒有心儀的對象。

Problem B --- Dreamoon and MRT

有些人可能有發現，開賽沒多久時限突然從 1 秒調為 2 秒，這是因為快開始的時候，測題者寫了一個 1 秒執行不完的解答，我突然覺得這題時限設一秒可能對大家來說有點難...才改為兩秒。

但這題再怎麼說也只是個 $O(2^m)$ 的模擬題而已，寫個遞迴，對於第 $i$ 次搭捷運，模擬往左或往右兩個可能。由於 $d_i \le 10^5$，所以模擬過程離起點最遠的距離不會超過 $2.5 \times 10^6$ 我們只要開個陣列就可以記錄某個點有沒有走過。有些人會先寫個 for 迴圈讓 $i$ 從 $0$ 跑到 $2^N$，再用 $i$ 的每個 bit 的值代表要往左或右。這也是常見的寫法，但他的複雜度是 O(m * 2^m)，若時限只有一秒就很有機會 TLE。

Problem C --- Everyone look forward to high rating user 2

這題的重點是了解題目，並用 STL 的 set 模擬就行了，每次分數的改變都會對應到 set 的移除和插入的操作各一次。並且每場比賽結束後，就把 rating 低於 dreamoon 的人從 set 裡移除即可。

Problem D --- Lonely Dreamoon 4

這題是 DP 題。

先假設 Input 給的數是從小到大，也就是 $a_1 \le a_2 \le \ldots \le a_N$，並令 $d_i = a_{i+1} - a_i, s = \displaystyle\min_{i=1 \sim N-1} d_i$。

想像一下我們有個空序列，現在要依序把 $a_1, a_2, \ldots$ 插入序列裡，過程中，我們關心兩件事：有多少組相鄰兩數的差的絕對值為 $s$ (記做 $x$)，以及最新插入的數是否和他相鄰的某個數的差為 $s$ (記做 $t$，可能值為 true/false)。於是 dp 的狀態為 dp[插入了幾個數][$x$][$t$]，轉移就自己想像吧～

Problem E --- Guess the generator parameter

這題是怪題。

如果只從因數和公因數的角度去思考這題，大概很難想出什麼好作法(我是想不到啦)。有件重要的事情是：每個數的範圍介於 $a$ 和 $b \times 10^9$ 之間。

首先，先把 $1000$ 個數排序，重新編號為 $a_1, a_2, \ldots, a_{1000}$，我們拿比較大的一些數來兩兩曲最大公因數，可以相信， $b$ 會出現在這些最大公因數之間 (這是可以用很數學的方式出算出機率啦...但這裡略過)，於是我們就先把這些 $b$ 的候補列出來。接著，我們要把幾乎不可能是 $b$ 的數移除。

首先，若取最大公因數的兩數都是 $b$ 產生的，那他們的最大公因數 $g$ 若不是 $b$，就會是 $b$ 的倍數，但若他是 $b$ 的倍數，$a_{1000} / g$ 會不超過 $5 \times 10^8$，若 $g = b$，則 $a_{1000} / g$ 應該會很接近 $10^9$ 才是，故我們可以把這樣的數淘汰掉。

接著，若取最大公因數的兩數分別是由 $a$ 和 $b$ 產生的，且 $a \ne b$，則他們的最大公因數 $g$ 會和 $a_{1000} / 10^9$ 差距很大，要不然就是其實也是 $b$。

最後。若取最大公因數的兩數都是由 $a$ 產生的，若他們的最大公因數 $g$ 和 $a_{1000} / 10^9$ 差不多大，則這個數幾乎可以確定就是 $a$，且幾乎只發生在 $a, b$ 很接近且都很大的時候。

於是，我們得到了 $a$ 或 $b$ 的候補，若我們已經確定了一個數，就可以把 $a_1$ 至 $a_{1000}$ 中不可能由該數產生的數去取最大公因數，就能得到另一數了。

這題相信還有很多做法可解，大家可以分享看看自己的做法～