2015年3月17日 星期二

SRM653 --- 由於題目太過簡單,一不小心比賽結束時也就把解題報告寫完了!

//不知道長標題對搜尋引擎是否會有影響 0.0

相較於前三場 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