相較於前三場 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
沒有留言:
張貼留言