CodeForces #202 Div.1

比賽連結：http://codeforces.com/contest/348

Problem A - Mafia (by TreapKing)

有\(N\)個人要玩桌遊，由於規則的關係，每一場會有一個人當不到player，如果第\(i\)個人想要當\(a_i\)次player，請問最少要玩幾次遊戲。

題解：

題目的操作是「把除了某個\(i\)以外的人全部加一」，也就是每次會有\(N-1\)個人被加一。假設已經玩了\(k\)場，且\(k\ge max\{a_i\}\)，那麼滿足所有人的需求 \(\Longleftrightarrow k(n-1) \ge \sum{a_i}\)，所以答案就是\(max( \sum{\lceil \frac{a_i}{n-1} \rceil},  max\{a_i\} )\)。

code: http://codeforces.com/contest/348/submission/15881727

另解(by nkhg):
看完題目覺得應該不難算，結果亂寫一個WA掉，然後廢廢的我就只想到比較單純的二分搜。
因為太單純沒什麼好解釋的，就直接放code吧！

code: http://codeforces.com/contest/348/submission/15952902

Problem B - Apple Tree (by nkhg)

有一棵\(n\)個點的有根樹，編號\(i\)的點有\(a_i\)顆蘋果，但是非葉節點一定是\(0\)，問你至少要在整顆樹上減掉幾顆蘋果才能使得「對每個節點，它的每個子樹的蘋果數量都相同。」

題解：
稍微畫一下會發現，如果一個點連了\(3\)個葉子，那這個點代表的子樹的蘋果數量在處理完成之後一定是\(3\)的倍數（\(0\)是任何數的倍數）；更進一步，如果一個點有\(2\)個兒子，其中一個會變成\(4\)的倍數、另一個會變成\(6\)的倍數，那這個點最後一定會變成\(24\)的倍數（\(lcm(4,6)\times2\)），這樣想一下就不難想到要怎麼做了吧！
我們可以好好的算每個子樹最後應該是幾的倍數，然後進一步根據它真正有的數量，計算它最後能夠剩下多少（例如一個點有兩個兒子，分別是「必須是\(3\)的倍數，最多可以留\(9\)顆」、「必須是\(2\)的倍數，最多留\(20\)顆」，那它就會變成「必須是\(6\)的倍數，最多留\(6\)顆」）。
最後遇到的瓶頸就是...求LCM小心overflow，詳細作法直接看code吧，我跟Yanger的LCM都有寫獨立一個函數，方法都很單純。

code: http://codeforces.com/contest/348/submission/15985801
code(Yanger): http://codeforces.com/contest/348/submission/15891347

--
順帶提一下ioicamp學到的...注意go函數的定義跟呼叫
不過後來我還是決定不要固定這樣用，我常常寫遞迴DFS漏打幾個參數，原本的寫法compile會噴error，比較不會造成問題。

code: http://codeforces.com/contest/348/submission/15987793

Problem C - Subset Sums (by nkhg)

有\(n\)個數字、\(m\)個集合，每個集合包含那\(n\)個數字中某幾個的reference，請你實現\(q\)個操作，每個操作可能是：

1.指定一個集合，計算那些reference的和

2.指定一個集合跟一個數字\(x\)，把那個集合的reference通通加上\(x\)

其中\(n,q\)以及集合的大小總和都不超過\(10^5\)

題解：
題目讀到一半就有某種熟悉感，印象中是去年資芽認證考的題目，當時我們一群人有注意到這題。
那時候我已經讀過題解了（讀懂但沒去寫）......不過這次virtual的時候只記得是把集合按大小區分\(\le \sqrt{n}\)跟\(\gt \sqrt{n}\)，然後做出時間及空間複雜度都是\(O(n^{1.5})\) （\(n\)其實是指題目敘述中不超過\(10^5\)的一切東西）
然後拿起筆分一下，分類成大集合跟小集合之後，要處理「大/小集合詢問」、「大/小集合增值」，配對之下的四種狀況。

1.小集合增值 and 小集合詢問：小集合大小不超過\(\sqrt{n}\)，所以直接做。

第一種情況超級簡單，但是接下來涉及大集合不容易做，所以我們決定犧牲一些空間來換取時間。（關鍵是大集合的數量不超過\(\sqrt{n}\)）也就是預處理每個集合跟每個大集合的交集大小，用\(O(n^{1.5})\)的空間複雜度存起來。這樣就可以處理接下來的東西了。
至於這個預處理，應該有不少方法都可以做到時空\(O(n^{1.5})\)，例如Yanger跟官方題解都是對每個大集合開一條長度\(n\)的陣列處理，而我則是預先把每個元素出現在哪些集合存起來，然後掃過每個大集合的每個元素更新答案。其實我沒辦法好好的確定我的作法複雜度是對的......virtual的時候想幾個邊界情況覺得沒問題就寫了，之後想一想也舉不出反例。

2.小集合增值 and 大集合詢問：在小集合增值的時候，直接掃過每個大集合更新答案。
3.大集合增值 and 小集合詢問：大集合增值的時候放tag，小集合詢問的時候掃過每個大集合的tag取得答案。
4.大集合增值 and 大集合詢問：大集合增值的時候放tag，大集合詢問的時候掃過每個大集合的tag取得答案。

賽中寫的code: http://codeforces.com/contest/348/submission/15954049
--
這份code異常的緩慢，經過大量的實驗之後，才找到原來是cin/cout的IO優化的cin.tie();應該要打cin.tie(0); ......

Problem D - Turtles (by nkhg)

給一個網格圖，有些格子可以走、有些不行，只能往右或往下，求左上走到右下的方法數。（這樣的話是DP或排容的經典題）

這題一樣的規則，但是是問有多少對不相交的路徑能從左上到右下。

題解：

virtual的時候亂踹一通，顯然炸慘慘。

最後看了題解，看不太懂那個lemma，跟隊友討論之後決定先不管它，於是直接用題解寫的結論。

答案等於：（我座標用\([1,n],[1,m]\)）

\((1,2)\)走到\((n-1,m)\)的方法數\(~~\times~~\)\((2,1)\)走到\((n,m-1)\)的方法數\(~~-~~\)
\((1,2)\)走到\((n,m-1)\)的方法數\(~~\times~~\)\((2,1)\)走到\((n-1,m)\)的方法數

code: http://codeforces.com/contest/348/submission/16037510