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

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

2017年3月17日 星期五

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

由於現在是個忙碌的上班族...題解就隨便講一下吧...

Problem A --- Guess the Number


這題我似乎估太難了?似乎大部分的人都會做嘛!

由於對於一個數愛麗絲心中所想的數 $i$ ,隨著艾利斯的猜測可能的範圍下界會愈來愈大,上界會愈來愈小。所以我們從 $a_1$ 看到 $a_N$ ,若 $i = a_x$,我們去找到比 $i$ 小的數中,艾利斯最後猜的數字是哪個,記做 $low_i$,以及比 $i$ 大的數中,艾利斯最後猜的數字是 $high_i$,並令 $dp[i][0]$ 為猜到 $i$ 的過程中會猜到幾個比 $i$ 小的數,以及令 $dp[i][1]$ 為猜到 $i$ 的過程中會猜到幾個比 $i$ 大的數,於是我們有 $dp[i][0] = dp[low_i][0] + 1$ 及 $dp[i][1] = dp[high_i][1] + 1$,於是第 $i$ 行只要印出 $dp[i][0] + dp[i][1] + 1$ 就好啦!細節請自行想像囉(可能要用一些簡單的 STL或資料結構。)

Problem B --- Swap Color

這題我估太簡單了...? 

$k=1$ 的測資,只要去數相鄰的格子對有多少組是顏色相異的,並且看看是否存在一組相鄰格子對顏色相同,就可以算出答案了~

$k = 2$ 的測資呢 ...依照有多少格子與原本的格子顏色不同個別處理,不同的個數只可能為 $0$ 或 $2$ 或 $4$。

相差為 $0$ 的一定辦的到。

相差為 $2$  的,又可在分為兩種情況,第一種為兩格相鄰,第二種诶兩格距離為 $2$。實際上若相異的格子對距離為 $1$ 或 $2$,在 $n, m \ge 2$ 時,一定有辦法用恰兩步交換構造出來 (若 $n = 1$ 或 $m = 1$ 就不一定囉!原本想說我沒有考這種情況已經夠善良了 XD)

相差為 $4$ 的,一定可以用兩組相鄰為的異色格子湊出。所以我們就計算兩組的組合有幾個,在扣掉有重疊的部分,重疊的情形有兩種,一種是重疊在黑色個子,另一種是重疊在白色格子,最後還要要在扣掉形如 "WB\nBW\n" 或 "BW\nWB\n" 的情形,因為有兩種可能的組合都會算到他。我自認為很善良的把這種情形放在 範例測資裡,不知道大家有沒有看到呢 @@

像這種題目啊... 若是出在 TOI 這種長時間的比賽,不如寫個暴搜的程式碼,在隨機產生小測資,驗證自己的答案是否正確,通常你寫的若是錯的,大概 $2 x 3$ 的測資就會讓你錯掉,你就可以想想看你是否漏想了什麼。

Problem C --- Count Simple Cycles

小測資直接暴力搜索就行了,可以自己試著估估看複雜度,當 $n = 10$ 時,就算是完全圖,遞迴搜索的步數也不多,但要注意是否會算到重覆的 Cycle,例如 $1-2-3$, $2-3-1$ 這兩種情形會不會重複算到,要步重複算到也有多種處理方法,可以自己想想看~

大測資的話,首先要知道 Cycle Basis ~,有了這個東西你就會知道 Cycle 數目一定不超過 $2^{18}$,所以也可以暴搜啦!!!

對不起這是騙你的。

要暴搜,首先要把度數為 $1$ 的點都拔掉,他們一定不會對 Simple Cycle 有貢獻,接著要把度數 為 $2$ 的點也縮起來,反正他連那麼長也沒什麼用, 就算把 $10^5$ 個度數為 $2$ 的點連在一起縮成一條邊也不會影響 Simple Cycle 的個數。

所以做完這些步驟後,掐指一算,會剩不到 $40$ 個點也不足 $60$ 條邊~,這個時候暴搜就可以過啦,但我不知道怎麼估這時暴搜的複雜度... 但就算不暴搜,我們也可以使用 Cycle Basis 的性質,好好做個 $O(2^{19} \times 60 )$ 之類的事情來解出這題,這裡就不細講了。