相較於前三場 SRM，這場確實簡單太多了！簡單到我都為出題者感到不好意思了 >_<
而且聽說出題者還出了兩個包，這場比賽的出題者也太廢了吧！
點我連到官方題解(必須登入Topcoder帳號)
Div.2 250 --- CountryGroup
題意：有 $N$ 個人坐一排，每個人都恰屬於一個國家(沒有人有雙重國籍唷 >_<)，你對這群人有個猜想：同一個國家的人會坐在一起。你想要驗證這個猜想，於是你對每個人都問了這個問題："包括你，總共有多少人和你來自同一個國家？"。如果能從大家的回答推論出你的猜想是錯誤的，或是你能確定有人的回答是錯誤的，請回傳 -1，否則回傳根據你的猜想，這群人的國家個數。
數據範圍：小小的。
tag：[ adhoc ]
= = = = = = = = = = = = = = =不管難度，只看題意的話，這題還算有趣吧？解法很單純，先考慮最左邊的人，令他的回答為 $x$，則從他往右算起連續的 $x$ 個人回答也得是 $x$ 才會滿足你的猜想，並把國家數目加一。緊接著把這些人排除，繼續做一樣的事，直到不滿足你的猜想或全部人都排除。
這題以 Div.2 250 來說應該是偏難的，有很多潛在的 bug，但 Sample 非常和譪可親，應該可以幫忙抓出大家大多數的 bug 吧？
順便讓大家想想看這題的變化題：
1.若大家不是坐成一排，而是坐成一個圈，甚至是大家的座位是排列成二維的樣子呢？
2.若同國家不一定要坐在相鄰位置，要怎麼算國家數或判斷有沒有人回答錯誤？
這兩題頂多也只是個 Div.2 500 的題目吧。
Div.2 500 --- RockPaperScissorsMagicEasy
題意：Alice 和 Bob 玩一個紙牌遊戲，每張紙牌上有剪刀石頭布三種圖案中的一種，每種圖案的紙牌都是無限供應的。Bob 會先選一些紙牌排成一列且圖案那一面朝下不讓 Alice 看到，接著 Alice 也會選和 Bob 同樣張數的紙排排成一列，按照順序和 Bob 的紙牌比輸贏，贏的人可以得一分，輸或平手都不會得分。但 Alice 其實有在紙牌背面偷偷做記號，所以 Bob 擺完紙排後，Alice 其實是知道 Bob 擺了些什麼。Alice 想要裝神祕的向 Bob 宣告說：這場遊戲我將會得 $score$ 分！請問 Alice 有多少種不同的紙牌選法使他可以達成他的宣告呢？答案請 mod $10^9 + 7$。
數據範圍：Bob 排的紙牌總數($N$)不超過 $2000$。
tag：[ 數學 ]
= = = = = = = = = = = = = = =首先，雖然題目會依序給你 Bob 每個位置放的圖案是什麼，但實際上我們只關心每個圖案 Bob 共選了幾張。於是我們可以枚舉對於 Bob 的每個圖案，Alice 各贏了幾張去算排列組合，並且只要枚舉其中兩個圖案贏的張數(令其為 $x$ 和 $y$)，就可以推出第三個圖案贏的張數必須是 $score - x - y$。於是我們就有了 O(N^2) 的做法！
看了我以上列的解法應該會覺得我是笨蛋吧 XD 一個有 O(N) 做法的題目竟然被我說的那麼複雜。但說來慚愧，我第一眼見到這個題目後直覺得做法就是這樣 ...，之後看了別人的作法只能直呼小月是笨蛋 >_<
實際上，我們根本不在乎 Bob 選的圖案是什麼，我們只要在當中選 $score$ 張卡讓 Alice 能贏，剩下的卡讓 Alice 不能贏，所以答案是 $C_{score}^n * 2^{n-score}$
Div.2 1000 --- SingingEasy
題意： Alice 和 Bob 要合唱一首歌，方便起見，我們把所有音符的音高用 $1 \sim 1,000,000$ 間的數字表示，並依序給你這首歌每個音的音高。他們合唱的時候，每個音都恰由 Alice 或 Bob 其中一人唱。不難想像，若同一人要唱的兩個音差愈大難度愈高，所以他們想要安排一種唱法，使得兩個人個別唱的所有音依序排列後，相鄰兩個音音高差的絕對值和愈小愈好。例如說有一首歌只有四個音，音高依序為 $1,4,2,5$ ，那我們可以讓 Alice 唱音高為 $1,2$ 的兩個音，Bob 唱剩下的音，這樣的話所有相鄰兩個音絕對值和為 $abs(1-2) + abs(4-5) = 2$ 將是最佳解。
數據範圍：至多 $2000$ 個音符(以 $N$ 表示)。
tag： [ dp ]
= = = = = = = = = = = = = = =這題應該讀完題就會讓人想要用 dp 去解他吧？我在想這題的時候，瞬間就覺得自己會做了，可是實際上要寫的時候，狀態轉移的部分稍微卡了一下下，離開筆電走路繞圈圈讓自己靜下來後才把轉移搞出來。連兩題 Div. 2 都出了點糗 >_<，大概是因為我對 Div.2 太輕忽了吧...
(註：以下過程我並沒有仔細處理邊界的情況，會發生你完全按照 dp 是寫下去卻可能 WA 掉的情況... 請自行腦補不足的部分 >_<)
這題我 dp 的狀態採用如右：dp[$L$][$R$] 純的最佳解代表只考慮到第 $1$ 到第 $R$ 個音，且唱第 $R$ 個的那個人是從 第 $L$ 個音連續唱到第 $R$ 個音，第 $L-1$ 個音是由另一個人唱。
當然你若要把他想成唱完 $R$ 個音以後，兩個人最後唱的音各是 第 $L - 1$ 個音和第 $R$ 個音也是可以的。
選一個好的狀態去 dp 大概是這題的第一個困難點，下一個困難點就是怎麼轉移了。
轉移分兩種 case:
1. 當 $L = R$ 時：$dp[L][R] = min_{1 \leq i \leq L-1}(dp[i][L-1] + abs(pitch[L] - pitch[i-1]))$
2. 當 $L < R$ 時： $dp[L][R] = dp[L][R-1] + abs(pitch[R] - pitch[R-1])$
雖然第一種 case 的時間複雜度是 O(R)，可是這種 case 的狀態數至多只有 $N$。第二種的轉移時間複雜度是 $O(1)$，有 $O(N^2)$ 個狀態。故總時間複雜度是 $O(N^2)$。
至於這題能不能做到比 $O(N^2)$ 更快呢...咦？似乎可以做到 $O(N)$ 唷！難道說 $N$ 變更大就是 Singing 的題目嗎！？讓我們拭目以待 ^ ^
Div.1 250 --- CountryGroupHard
題意：有 $N$ 個人坐一排，每個人都恰屬於一個國家(沒有人有雙重國籍唷 >_<)，已知同個國家的人都坐在一起。有一個記著想要問每個人這個問題："包括你，總共有多少人和你來自同一個國家？"。這個記者已經問過一些人了(問過的人可以是任意子集)，他想知道他到底有沒有必要在繼續問下去，還是說其實已經可以推論剩下的所有人的答案呢？
數據範圍：小小的。
tag：[ dp ]
= = = = = = = = = = = = = = =看到 tag 的話這題就直接被雷爆了吧？看到這意題的第一眼，我大概想了一分鐘要怎麼去 greedy 判斷，一直想不出來，後來轉念一想，我們根本可以 dp 出所有人的回答的可能性的方法數吧...(諸如這樣，根本可以算出個數，但只問你Yes/No的題目還蠻常出現的)，於是就沒多想地隨便寫了個 $O(N^3)$ 的 dp 了。
可是我設的 dp 狀態頗蠢的，我竟然開了三維陣列 $dp[x][y][z]$，代表只考慮前面 $x$ 個人時，第 $x$ 個人是某群共 $y$ 個人的國家的第 $z$ 個人的方法數。總時間複雜度是 $O(n^3)$。
更多人 dp 狀態應該只會開一維 $dp[x]$ 代表只考慮前面 $x$ 個人時，第 $x$ 人恰好是同國家的某群人的最後一個人的方法數。可以輕鬆做到 $O(n^2)$。
而事實上，這題可以做到 $O(n)$！並不難，大家可以想想看～
Div.1 450 --- Singing
題意： Alice 和 Bob 要合唱一首歌，方便起見，我們把所有音符的音高用 $1 \sim N$ 間的數字表示，其中 Bob 的音域在 $[1,high]$，Alice 的音域在 $[low,N]$。依序給你這首歌每個音的音高。他們合唱的時候，每個音都恰由 Alice 或 Bob 其中一人唱(當然要符合唱的人的音域)。且相同音高的音符必須同一個人唱。為了使合唱的難度變低，他們希望唱的過程中，"換手"的次數最少，一次"換手"是指相鄰兩個音由不同人唱。
數據範圍：至多 $1000$ 個音符。
tag： [ min-cut ]
= = = = = = = = = = = = = = =咦，這題不是 SingingEasy 的範圍加強版啊...難道說 $O(N)$ 的做法是我想錯了嗎 >_< 這兩題還差蠻多的 Orz
SRM 偶爾會有像這樣子相當裸的 flow 類的題目，由其這題的 input 處理相當簡單，有經驗的選手讀題加寫題不需要 5 分鐘。但是對 flow 若不熟悉，這題或許會想歪吧？可是我身為一個曾經花時間研究過各類 flow 題的人，無法想像這題能想歪成什麼東西。(後來聽別人說有想歪到 dp 去。)
總之這題就是把每個音高都當成一個點，任兩個點會建一條 cost 為 "這兩個音高相鄰的次數" 的邊。我們就能把此問題轉換為：要把所有點都 label 成 Alice 或 Bob，並且已經知道某些點的 label，使得連結相異 label 的邊的總 cost 最小。
超有 min-cut problem 的感覺對吧！就好像要我們找一個最小 cost 的 cut，使得此 cut 的一邊被 label 成 Alice，另一邊被 label 成 Bob。
確切的建圖方法為：除了有出現的 pitches 當做點以外，在另外建出一個代表 Alice 的 source 和代表 Bob 的 sink，並且把 source 建 cost 為無窮大的有向邊到確定是 Alice 唱的音高的點，也把所有確定是 Bob 唱的點連一條 cost 為無窮大的邊到 sink，最後再把上一段所提到的邊必須兩個方向都建一條相同 cost 的邊，於是就大功告成了。可以想想看為什麼這樣建出的圗是對的。
如果擁有 2014 ioicamp 的講議的人，可以翻到例題 7-8，是比這題還更裸的問題 XD
最後再給一個相同概念但稍為複雜些的題目：SPOJ839 Optimal Marks 做為練習。
Div.1 900 --- RockPaperScissorsMagic
題意：Alice 和 Bob 玩一個紙牌遊戲，每張紙牌上有剪刀石頭布三種圖案中的一種，每種圖案的紙牌都是無限供應的。Bob 會先選一些紙牌排成一列且圖案那一面朝下不讓 Alice 看到，接著 Alice 也會選和 Bob 同樣張數的紙排排成一列，按照順序和 Bob 的紙牌比輸贏，贏的人可以得 $win$ 分，平手各得 $even$ 分，輸的人得 $lose$ 分。但 Alice 發現其實有人在 Bob 的紙牌背面偷偷做記號，相同圖案的紙牌都被標了相同的數字($0 \sim 2$)做為記號，但是 Alice 不知道哪個數字對應到哪個花色。Alice 想要根據這些記號來出牌，並向 Bob 如表演魔術般的宣告說，他知道最後自己會得幾分。請問 Alice 有多少種不同的表演方法？只要他宣告的分數不同或是出的牌的序列不同就算是不同表演方法。答案請 mod $10^9 + 7$。
數據範圍：Bob 排的紙牌總數($N$)不超過 $1000$。
tag：[ 數學 ]
= = = = = = = = = = = = = = =這題好像也和 RockPaperScissorsMagicEasy 差很多...(以解法而言)
實際上這題頗簡單的，會覺得他難的話大概只是題目敘述複雜了點？首先同樣的我們不關心 Bob 排的那些牌的順序，只關心每種記號的牌各有幾張，並令 $n_i$ 為被標記為 $i$ 的張數。
接著我們先想想看裸的做要怎麼做。應該會想到此做法：對於每個記號，都枚舉出各 Alice 各種圖案各出多少數量。也就是說，枚舉 Alice 對於標號 $0$ 的牌出了 $a$ 張剪刀，$b$ 張石頭，$n_0-a-b$ 張布；對於標號 $1$ 的牌出了 $c$ 張剪刀，$d$ 張石頭，$n_1-c-d$ 張布；對於標號 $2$ 的牌出了 $e$ 張剪刀，$f$ 張石頭，$n_2-e-f$ 張布。最後在枚舉 $3!$ 種標號和簡刀石頭布的配對方法，看看得分是否一樣。這樣的暴力做法複雜度約是 $O(N^6)$。
這做法能化簡嘛？還是要另闢出路呢？例如說根本就只有少數 special case 有可能使得 Alice 有宣告方法？不管怎樣，我們還是先列出對應的數學的式子如下：
等號左邊的變數意義都如同前面所述，而等號右邊 $A_{ij}$ 的意義為：在枚舉完後，若標為 $j$ 的卡片實際上是 $i$ ($i=0$：剪刀，$i=1$：石頭，$i=2$：布)，Alice 對抗所有此類卡片的總得分。
而所有 $3!$ 種可能標號配對方法都一樣意思就是矩陣 $A$ 中每行每列恰取一個數的和都要一樣。
列到這裡先停頓一下看看大家對做法是否有感覺了～
直覺敏銳的人應該就會注意到 "所有 $3!$ 種可能標號配對方法都一樣意思就是矩陣 $A$ 中每行每列恰取一個數的和都要一樣。" 這句話還有更和譪可親的形式！每行每列恰取一個數的和都一樣意即 "無論取哪個 column，相同的兩個 row 的值的差是固定的！"。也就是說對於任意 $i,j$，$A_{i0} - A_{j0} = A_{i1} - A_{j1} = A_{i2} - A_{j2}$。
提示到這裡應該有不少原本不會的人知道要怎麼做了吧？原本我們要同時枚舉 $a~f$，但我們也可以 $a,b$ 一組，$c,d$ 一組，$e,f$ 一組分開枚舉，每組個別枚舉完恰會對應到 $A$ 矩陣中的一個 column，我們的問題變成要求三組算出來的 row 的差值都一樣的組和有幾種，於是可以使用 hash 在 $O(N^2)$ 的時間做到。
= = = = = = = = = = = = = = =
這篇讀完應該能讓大家相信我說的這場 SRM 很簡單吧 XD 我覺得題目敘述本身會令人覺得還蠻有趣的啦，只是真的偏簡單就是了 0.0
沒有留言:
張貼留言