2017年3月19日 星期日

農場例行賽 #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}$ 中不可能由該數產生的數去取最大公因數,就能得到另一數了。

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