UVa12907-12915

緩慢更新中...感謝 morris821028 幫忙寫 code 驗證我理解是否有誤 m(_ _)m

12907 Toby the adventurer 

題意：有一塊大陸，有 $N$ 個城市，以及 $M$ 條單向道路，每條道路有對應的通行費，有一個人要在這塊大路上冒險，最初他在邊號 $R$ 的城市，他可以付一條路所對應的費用，延著該條路的方向，到一個新的城市，此外，他可以不用付任何費用就回到任何一個他已去過的城市，請問他至少要花多少錢才能逛完所有城市？並輸出旅行的方案。若無解則輸出 impossible。

數據範圍： $測資組數 \leq 100， 3 < N \leq 10000，3 < M \leq N，0 \leq R < N$。

tag：[ 圖論 ]

　　乍看之下這題就只是個 DMST (Directed Minimum Spanning Tree) 問題 (一般情況可使用 Edmond's algorithm 解之)，且是一個要輸出解的 DMST。但大家應該有發現他有一個超怪的條件： $M \leq N$ ！事一定有蹊蹺！？

　　首先有件很理所當然的事： $N$ 個點的 DMST 恰有 $N-1$ 條邊。所以我們可以藉此聯想到一個 $O(N^2)$ 的演算法：考慮 $N=M$ 的 case，我們可以枚舉要刪除哪條邊，並 $O(N)$ check 剩下的邊是否為一個合法的 DMST。若 $M<N$ ，答案應該蠻顯然的。

　　接下來可以想想看，我們真的要枚舉那麼多種可能性嗎？首先注意到，合法的 DMST 中，每個點的 in degree 幾乎都是 $1$，但 $n$ 條邊 in degree 的總合只有 $n$ 的 ，實際上，除起點外，若有哪個非起點的點在原圖中的 in degree 是 $0$，就沒有解；若 in degree 是 $1$ 則非得選不可。所以可選可不選的邊至多只有兩條！找出那兩條，然後枚舉哪兩種可能看看哪個比較好，就解決這題了。

　　若真的遇到 DMST 找解的問題，可是非常痛苦的 ...，我比賽中在解 DMST 問題時，總是直接從 codebook 複製貼上。但是現今大部分的人所使用的 codebook 都沒有包含構造出一組 DMST 解這件事，所以就必須好好重新想想 Edmond's algorithm。實際上，2013-2014 NEERC 就有一題要構造出解的 DMST 問題： UVa 1681 Dictionary，大家可以試著去挑戰他 XD 挑戰完把他加進 codebook XD

　　若有在 UVa 找最經典的 DMST 問題：則請看 UVa 11183 - Teen Girl Squad

12908 The book thief

題意：有一個小偷把一本書的所有頁數數字加起來，但漏加了一個數字，告訴你小偷算出的總和的值，請求出該本書有幾頁以及漏加的是哪個數字。

tag：[ 數學 ]

嗯...可以 O(1) 快速得知至少需要幾頁 (1加至總頁數必須大於 input 值)，再 check 是否能減掉某個數字就得到 input。實際上你總是能得到一個合法的漏掉的頁數唷！

12909 Numeric Center

題意：給定 $n$，請問 ${1}$， ${1,2}$，${1,2,3}$， ... ， ${1,2, \dots , n}$ 的集合中，有多少個集合，能在集合中恰找到一個數 $x$ ，使得集合中小於 $x$ 的數的總和和大於 $x$ 的數的總和相等。例如說，集合 ${1,2,3,4,5,6,7,8}$ 可選 $6$ 為 $x$，使得 $1+2+ \dots + 5 = 7+8$。

tag：[ 數學 ]

關鍵字： Pell's Eaquation

　　據說這題只要把最小的幾個數搜出來再拿去 google 就能 google 到數學公式了。

　　若要自己解，可以先列出關係式，據說化簡後會得到 $8*x^2 + 1$ 必須是完全平方數，也就是說 $x$ 式所有 $y^2-8*x^2 = 1$的整數解。這東西叫做 佩爾方程，可以 google 到很多關於這東西的資訊，他可以使你用手算一算後很快的得到所有 $x$ 的解的遞推公式。

12910 Snakes and Ladders

題意：蛇梯棋遊戲，使用公平的六面骰，問結束遊戲時的步數期望值。

tag：[ 數學 ]

關鍵字：高斯消去

　　就...一臉高斯消去樣，把期望值的關係式列出來後解聯立方程式。

12911 Subset sum

題意：給 $N$ 個數的集合，請問有多少非空子集的集合內數字總合等於給定的值 $T$。

數據範圍：$1\leq N \leq 40$。

tag：[ 小品 ]

關鍵字：分兩半

　　通常看到 $N = 40$ 附近的問題... 就會值接兩響到把數據切成兩半的做法。這題的類題不勝枚舉，把集合拆成兩半，每半部的集合都枚舉所有 $2^{N/2}$ 種subset，枚舉其中一半部時 hash 每個總合的值出現多少次，而枚舉另外一半部時，就可以根據hash值得知他有多少種和前一半部的組合加總可以湊成 $T$。

12912 Josephus lottery

題意：有 $N$ 個人圍一圈，由順時針分別從 $1$ 號編號到 $N$ 號，由 $1$ 號開始數，第一輪順時針數 $K$ 個人，並把被數到 $K$ 的人移除，下一輪從被移除的下一個人開始數，但這次是逆時針數 $K$ 個人，一樣把第 $K$ 個人移除，如此反覆順時針逆時針交互的數，直到只剩下一個人，請問剩下的人編號是多少？

數據範圍：$1 \leq \leq K \leq N \leq 10^6$。

　　就約瑟夫問題變形。雖然 $N$ 很大，但 $O(N log N)$ 做法就可以 AC 了。與一般的約瑟夫問題一樣，可以倒著用 $O(n)$的時間複雜度 dp 回來。

12913 Grounded

題意：給定 $N$、$K$，$S$ 為包含 $0 \sim 2^N - 1$ 間所有整數的集合，請問 $S$ 有多少子集合滿足集合內所有數的 xor 結果，轉乘二進位後恰有 $K$ 個 bit 是 1。

數據範圍：$1 \leq K \leq N \leq 10^6$
tag：[ 數學 ]
關鍵字：集合

和 Hackerrank 上的 Ad Infinitum 10 - Math Programming Contest Number of zero-xor subsets 概念一模一樣，差別只在於 Hackerrank 那題只問 $K = 0$ 的 case，所以去參考Hackerrank 上的 Editorial 理解後應該也能做出這題。

我來用我自己的方法解釋 $K = 0$ 的 case。 $K = 0$ 意即該集合所有數的 xor 結果為 $0$。先隨便亂抓一個集合，例如說 $N = 3$ 時，我們任取一個集合：{2,3,5,6}，這四個數 xor 結果為 $2$，並不是 $0$，現在我們想要把這個集合稍做修改，讓他變成 $0$，要怎麼做呢？應該會很直覺的把集合內的 $2$ 去掉吧？那若現在取的集合是 {4,6} 呢？ 此集合 xor 後的結果也是 $2$，那我們就可以把 $2$ 加進這個集合裡，能使集合的 xor 值也變成 $0$。

於是我們可以發現，任取一個 $S$ 的子集，我們都有辦法恰對集合新增或移除一個數，讓集合內所有數 xor 結果為 $0$ (注意我們新增或移除的數可能是 $0$)，且方法恰只有一種。所以說，總共有 $2^{2^N}$ 種子集合，我們就能變出 $2^{2^N}$ 個 xor 值為 0 的集合嗎！？當然不可能啦 XD 實際上，會有好多個集合改變後會對應到同一個集合，那麼一個 xor 值為 $0$ 的集合，會被幾個集合對應到呢？例如 $N = 2$ 時，{1,2,3} 集合內所有數 xor 值為 $0$，而會對應到他的集合有 {0,1,2,3}、{2,3}、{1,3}、{1,2} 共四種。到這裡應該能看出點頭緒了吧？對於每一種集合內所有數 xor 值為 $0$ 的集合，都恰有 $2^N$ 個集合能經過加減一個元素的操作對應到它。所以全部 $S$ 的子集合，每 $2^N$ 個集合會對應到一個 xor 值為 $0$ 的集合，故全部共有 $(2^{2^N})/(2^N)$ 個 xor 值為 $0$ 的集合！這也就是 hackerrank 那提的答案。

至於 $K$ 不為 $0$ 要怎麼辦呢？剛才我們解的是 xor 值為 $0$ 的集合數，那 xor 值為 $1$ 呢？ xor 值為 $2$ 呢？能如法炮製嗎？

12914 Sum of all permutation

根本 Hackerrank 上的  Ad Infinitum 8 - Math Programming Contest Value of all Permutations。

12915 TripleCorn

正常的 dp 優化題？

Codeforces Round #300 參賽記錄

比賽連結
Editorial 連結

　　這場比賽我除了解題順序不認真以外，其他部分我可是非常認真的！在賽中完全沒有想過要去 challenge 別人！有人在賽中敲我 g+ 我也沒回應！但是名次好慘呵，我花了一個小時左右寫完了 C、D、F 後，直接打開 G，剩下的一個半小時都栽在上面了，賽中剩下 20 分鐘才想到解法，賽後一個小時左右才 AC。最後 rank 371，連抽 T-shirt 的機會都沒有。還有人問我是否想要再一次變成藍色，聽到別人這樣問我我好傷心喔 XDDD，我這幾場都有好好的比耶 XDDD 只是最近的比賽不小心把我的實力揭露出來讓我連掉五場 rating XDDD 最近的幾場比賽大都是比較大型的比賽諸如 VK cup、ZeptoLab Code Rush 之類的，每次遇到大型比賽我的名次就會變糟糕 ... 這是心理壓力的關係嗎？

　　最近總是直接寫題目的解答，這篇來回覆一下我以前在 BBS 使用的方式紀錄比賽，把比賽過程中我在思考什麼，在哪些地方卡住等資訊近可能的保留下來。

　　這場比賽，我想要犧牲一些解簡單題的時間，來換取更高的賽中 AC 難題的可能性，所以開場就直接從 pC 看起，看完後我就立刻連想到了 CF534 B - Covered Path，都是類似的概念，相鄰兩個時間點直不能超過給定值的題目。可是我的思緒很混亂，寫出了比較複雜的做法，明明就寫一個 for 迴圈就能解決，我卻寫了兩個，順的跑一次逆的也跑一次，還出了點 bug，結果13分鐘才 AC，這時候已經有不少人前三題都寫完了 =口= 結果我先寫 C也沒省到多少時間嘛 = =

　　接著我直接看 pD 也是個還算直覺但要把他寫成 code 無法立刻想到好寫的做法，但我還是憑直覺寫下去了。總之就是先簡查哪些向量若可以選就一定要選他，在檢查看看使用這些所有選的向量是否能攻擊到所有得被攻擊到的位置。是說這題 Sample Output很心機，硬是要和大家直覺寫出來的 Output長的不一樣...。我原本漏考慮了有可能會攻擊到盤面外部的 case，使得 Output 總是輸出 NO，我大概花了兩三分鐘才 de 出這個問題，後來修正後 output 還是和 Sample Output不一樣 = =，check 了一下才確定我的 output 確實也是正確的。

　　我寫完兩題後已經有人寫了五題了！挫敗感很高耶，我決定跳過 pE，直接看也有人在短時間 AC 的 pF。pF看完我立刻往複雜度 $O(n \sqrt{n})$ 的方向去想，因為讀完題目後立刻從我腦海裡浮現的知識是：每個 node 當 $k$ 的值從 $1 \sim n-1$，在改變時，他的父節點可能只會改變 $O(\sqrt{n})$ 次，這就和 $n$ 固定，$k$ 會改變時 $\lfloor n/k \rfloor$ 的可能值至多只有 $O(\sqrt{n})$ 很像，因為父節點的編號實際上就是 $\lfloor (x-2)/k \rfloor + 1$，所以要解這題，我們只需要把每個節點的的可能的父節點都各別求出來，以及會對應到該父節點的 $k$ 值個數也求出來就行了。於是讀完題想不到一分鐘我就立刻開始寫 code，但是寫到剩最後一部分 --- 記算父節點的編號以及有多少 $k$ 值會對應到該編號，我卻卡住了，我腦袋轉不過來 ... 每次我在認真比賽的時候，都不太能進行這類比較複雜的計算 ... 團體賽的時候我還可以秤隊友還在 coding 時，在旁邊深呼吸，想辦法靜下心然後在開始動筆計算，可是在個人賽的時候我幾乎無法靜下心做這件事，啊啊啊該怎麼辦 >_<

　　這時我想法亂成一團，在思考要不要靜下心好好動筆算的時候，有想到了令一種思考此題的方式 --- 上段所述的方法是固定子節點，思考父節點的變化。但我們可以從另外一個角度：考慮每個父節點，看看他有哪些子節點，我們可以發現，當 $k$ 愈大的時候擁有子節點的節點數量為 $O(n/k)$ ，所以若先把所有父節點所擁有的子節點區間都離線存下來，就可以 $O(n \log^2{n})$  (因為總共有 $O(n \log{n})$ 個區間) 配合 BIT 掃過求出每個父節點有多少子節點的值比自己大。原本我有點擔心這樣會不會花太多記憶體儲存，但你若有仔細看這題的記憶體限制，會發現這題的限制是 $512$ MB，比預設的 $256$ MB 還大，就會發現 author 預設的解法大概就是這個做法吧？要不然上一段的做法根本不需要什麼記憶體 XD 這個做法想清楚後，我就把原本寫的 code 果斷砍掉了 ... 重寫新的做法，寫完 Sample 對了之後我還自己生了最大的測資測了我的 code 的速度，看來是沒什麼問題後才 submit。我寫完三題時，已經有不少人把前六題都寫完啦！！！

　　隨便點了幾份 pF 的 code，兩種做法都有了寫，第一種做法的程式碼可以參考 rng_58 的 code，寫的非常精簡，而賽中14分鐘就 AC 的人則是使用第二種方法，他沒有離線預處理，而是使有了比較複雜的資料結構 (WaveletTree?這什麼東西@@) 使得可以 online 快速知道一個區間內有多少數小於給定值。

　　上傳 pF 後，我鐵了心直接挑戰 pG。 pG 題目非常簡短如下：

有一個長度為 $l$ 由 ULRD 所組成的上下左右的移動指令，你並不知道指令的 pattern 長怎樣。有一個機器人起點在 (0,0)，每一單位時間依序按照這串指令直性移步並移動一單位距離，若這串指令都執行過，會再從頭開始用同樣的 pattern 繼續移動。告訴你這個機起人某些時間點的位置，請找出一種可能的 pattern 或輸出無解。

 　　這題感覺起來有點數學，又有點差分約數的感覺？我覺得我一定能解出來！但是想了許久就是沒什麼想到什麼明確的起手步，是因為有一點點精神不濟想睡覺的關係嗎？先把題目化簡移下好了，這題是二維的，如果變成一維的話我要怎麼做？想到這裡，我就發現，若會做一維，也就是說只有LR兩種指令的版本那麼我們就可以解二維的了！因為我們可以把U, R以及 L,D 分別是為同意種指令，若是 U,R 的指令那麼機器人所在的座標 $(x,y)$ 中 $x+y$ 的值就會加 $1$，若是 L,D 則會減 $1$。固解出一維的 case，我們就能月定pattern的每個指令會是L,D兩者之一或是 U,R 兩者之一。接著我們在改成把 L,U 和 D,R 個別綁在一起，做出來後就能就能得所有指令了！

　　轉換成一維(只有 L,R 兩種指令) 後我仍舊卡了很久，要按照時間序考慮問題嗎？還是按照時間 mod $l$ 的值由小到大考慮問題呢？如果有出現兩個時間 mod $l$ 的值相同又會怎樣？我們就可以得到整串指令移動完的為移會是多少，知道這件事後又怎樣？知道這件事後我們就可以按照時間 mod $l$ 的值由小到大考慮所有已知機器人的位置，做一些運算後，得知很多諸如 (前 $i$ 個指令移動完位移將是 $d_i$ ) 的資訊，如果 $d_i < 0$ 或 $d_i > i$ 或 $d_i$ 和 $i$ 的奇偶性不同就不合法，否則就可以貪心的填入 $(d_i + i)/2$ 個 R 進去之類的。所以若有兩個已知機器人位置的時間點 mod $l$ 結果相同，我們就可以得到正確的 pattern！所以我解決的其中一種 special case！但這要怎麼推廣？完全想不到啊 >_<

　　這種 special case 我們能確定 pattern 的主因是我們知道了整個指令群移動完的位移的值(令其為 $ds$)，所以我們若能確定該值，就解決了吧？ $ds$ 的值的可能性有 $0 \sim l$ 那麼多種，有辦法縮小其範圍嗎？有沒有可能同一組測資擁有不同的 $ds$ 值的合法解呢？這麼說來剛剛我們確定了 $ds$ 就能知道每個區間內有多少個 R 指令，所以說我們若把每個區間內的 R 指令個數當成變數，稱其為 $r_i$ 之類的，那就可以把 $ds$ 和 $r_i$ 列出線性等式吧？而且我們擁有 $ds$ 和所有 $r_i$ 的上下界( $ds$ 的上下界是 $0$ 和 $l$， $r_i$的上下界是 $0$ 和 該區間大小)，那是否存在某種快速枚舉這些變數的值的並判定有無合法解的演算法呢？嗯... 若枚舉了任何一個變數的值那麼就可以 $O(n)$ 判斷是否有合法解了，若枚舉 $ds$ 的 $O(l)$ 種可能值，那複雜度最高就是 $O(ln)$ 有點大耶？嗯... 某種程度上這些區間是型成環狀的... 環狀？枚舉！？這件是好像有印象！那不就是 CF526 E 的其中一種算法嗎？因為有 $n$ 個區間，所以至少有一個區間 size $\leq l/n$，所以就會至少存在有某個變數要枚舉的可能性 $\leq l/n$ 於是找出該變數並枚舉的複雜度會是 $O(l)$！於是我就解出來啦！想到這裡的時候，比賽已經剩不到 $30$ 分鐘了 0.0

　　最後寫 code 時發現使用這種做法還有好多好多 special case 要處理 ...  那些 $ds$ 在等式中係數可能是 $0$ 之類的問題，或是所有時間點剛好 mod $l$ 都是 $0$ 的問題(我覺得這個 bug 思考時不會漏掉的一定都是怪人！)。

　　AC 候我就在想，我使用了一個那麼奇怪的技巧來 AC 這題，想必不是 author 所用的解吧？而且這個技巧不久前才出現過耶？後來看了其他所有 AC 的 code，果然只有我使用這個方法 ...，我忽略了一件很重要的事：所有聯立等式中 $r_i$ 的細數都是 $1$ ！所以對於每個 $q+i * ds + r_i = v_i$ 的等式，我們可以根據 $r_i$ 的上下界來更新 $ds$ 的上下界，若全部等式更新完後 $ds$仍有整數解，那麼代入任一個 $ds$ 的整數解給所有式子後一定能得到在合法範圍裡的 $r_i$ 的整數解。於是 $code$ 應該能變成更簡單一些，根本不必枚舉某個變數的所有可能值啊！若...我在看到這題時，碼上就把所有該列的變數該列的等式列出來在紙上，是否能快一點想到呢？但我相信拿麼做的話就不會產生我這種奇葩的解法了 0.0

　　呵呵在最後一步採用了有點多餘且非常獵奇的方法，我該為此感到自豪還哀傷呢？

　　賽後看了剩下的題目， pA直接暴力枚舉即可。pB 就是一個很直覺的 greedy。 pE 就普通的 tree dp，記算可能要小心一點。 pH，嗯... 感覺起來不太難，要歸類為 greedy 吧？想了一下細節，覺得應該就是那樣了。不過 pH 目前 最短的AC code 值得研究研究，他的解題步驟和我的思考順序並不一樣，我還不知道怎麼證他的做法的正確性 ... 證出來並覺得很有意思的話再分享吧？

　　如果我這篇相較於過去的解題報告，寫的讓大家完全看不懂，想必是很正常的一件事...

TLX Open Contest Beta Round #1

昨天心血來潮就寫了一下這個據說是APIO熱身賽的東西 (Invitation from Codeforces)

題目感覺上都蠻普通的，APIO 應該會比這些題目難很多吧？題目品質也有點問題，pB、pC都有嚴重的 issue ，賽中才被更正。

是說 SRM656 的解題報告寫了一半覺得好難寫，先跑來寫這個簡單的東西 wwwwww

題目連結(必須登入)

Problem --- Social Inequality

題意：給 $N$ 個點，問有多少任兩個點所圍出的矩形的面積總合。

數據範圍：$1 \leq N \leq 10^5$，所有點座標介於 $0 \sim 10^4$

關鍵字：[ D&C ]

tag：分治法

= = = = = = = = = = = = = = =
這題正好可以看出我在解題時會怎樣去聯想以做過的題目。它給了平面上好多點，又問了關於所有矩形的某些資訊，於是我就聯想到了  ZeptoLab Code Rush 2015 pF，是我過去寫過題解的東西！(我每次列的關鍵字終於用到了 XD 輕鬆搜到這題 )，於是我就開始思考要怎樣用Divide and Conquer 來解這題。

使用的 D&C 來解這題的話，大制概念就是每次把點群都分兩半，把兩對角恰在兩半各一個的矩行面積總和先算出來，再遞回下去。

這題時限只有 0.3 秒，看來一定得用 $O(n log n)$ 的解法才能 AC，所以在每次解一個 subproblem 時，只能用 O(n) 去解決 (這裡的 $n$ 是該 subproblem 的點數)。

仔細描述一下我們要解的 subproblem：
　　平面上有很多點，以及一條水平線，請把所有水平線上及水平線下各曲一點的所有組合，每個組合所圍成的矩行面積總合計算出來。

不防假設我們已經把所有點由左到右排序好了。接著我們由左到右一個點一個點依序加入，每加入一個點時，我們希望能以 $O(1)$ 的時間，把該點與所有在另外一半的已加入點所圍成的矩形面積總合算出來。

如下圖所示，假設現在加入的是在下半部的藍點，而在上半部已存在的點是三個紅點。要一次行算出所有的面積似乎有點困難，但我們若再把每個舉行細分為上半部和下半部，就會發現要一次把所有矩行的下半部面積總合算出來(或是上半部)，都沒有很困難。

例如說我要算下半部的部分，我們可以發現所有下半部的矩形高都一樣，在新增藍點時才會決定(令其為 $h$)。所以我們若能知道所有矩行寬的總和($\sum w_i$)，就可以算出所有下半部的矩形面積總合($\sum{w_i*h}$)，以下圖為例，令藍點 $x$ 座標為 $x_b$，紅點座標為 $x_1, x_2, x_3$，則 $\sum{w_i} = \sum{(x_b - x_i)} = 3*x_b - \sum{x_i}$。所以實際上我們只要記錄每一半部已經加入多少點，加進去的點的 $x$ 座標和，就可以快速算出加入的點所在的那半部矩形面積總合。

而另外一半部也能使用某些累加的概念去算出面積總和，詳情請參考我所付的程式碼 >_<

若要認真考慮 Divide and Conquer 中的 Conquer 到底有沒有在這個解法起作用...其實我覺得並沒有 ... 所以還是稱它為分治法好了 Orz

我的程式碼如下：

Problem --- Jump!

題意：有無窮多的個石頭，並把它們用正整數編號。每個石頭都有個對應的值 $a_i$。有多個詢問。詢問過程中要維護一個數 $N$。第一種詢問：給定 $N$ 的新的值。第二種詢問：更新給定編號的石頭的值。第三種詢問：你可以選擇一個數 $P$ ($2 \leq P \leq N-2$ 或 $P = 0$)，最初會先把石頭 $1$ 標記，接著會把石頭 $(P$ mod $N) + 1$,  $(P*2$ mod $N) + 1$, $\dots$ 也標記，直到再遇到石頭 $1$ 為止，請問選哪個 $P$ 值，能使得被標記的石頭所對應到的值總和最大($P$ 若選 $0$ 代表指標記邊號 $1$ 的石頭)？請輸出最大的總和值。

數據範圍：$1 \leq N \leq 2000$，詢問數 $\leq 50,000$。

關鍵字：[ 資料結構 ]

= = = = = = = = = = = = = = =
這題題目敘述很複雜... 而且一剛開始 $P$ 的範圍還給錯使我 WA 了好多次。

首先要注意到雖然我們選的 $P$ 值可能不同，但若 $gcd (P, N)$ 相同的話，標記到的石頭們會是同一群，也就是所有邊號為 $gcd(P, N)$ 的倍數加 $1$ 的石頭。方便起見，值接把所有石頭邊號減一會比較好寫 code。

注意到這件事後，我們就知道對於每個第二種詢問，只需要考慮是 $N$ 的因數的 $P$ 值 (當 $N \leq 6$ 時，有可能不存在合法的 $P$ 使得 $gcd(P,N) = 1$，要特別處理)。並且在枚舉這些值時，可以用一些資料結構如樹狀數組(Binary Index Tree, BIT)去算加總。

詳情參考我的程式碼：

Problem --- Fowl Scupltures

題意：平面上有好多個點，以及一條通過原點的直線，這些點是兩兩成對的，也就是說所有點對於該直線的隊稱位置也會有一個點。但現在某些點消失了，並且我們也不知道直線在哪(只知道它通過原點)，問至少消失幾個點，以及直線可能的位置(若有多種可能位置請選取最離 $x$ 軸政像逆時針角度最大的位置)

數據範圍：點數 $\leq 2000$，所有座標絕對值 $\leq 10^9$。

關鍵字：[ 計算幾何 ] [ 枚舉 ]

= = = = = = = = = = = = = = =
這題其實有個很大的癥結點：題目沒說明點若恰好在那條直線上會發生什麼事，若造測資條件所述："No two or more sculptures are located on the same coordinate." 那麼點應該不能出現在直線上，可是沒有判這件事也會 AC (判了說不定會變成 WA？)，總之先無視這個問題...

要使得消失的點最少，也就是要使得配對到的點對最多。並且每個點對若能配對，也都會有個配對時會對應到的角度。於是我們枚舉任兩點能夠配對時的角度，只留下角度的資訊，可哪個角度出現最多次，那個角度就是答案了。至於對稱軸的角度，在這題裡可以使用向量取代，於是不會有浮點數誤差。細節請看程式碼註解。

我的程式碼：

論台灣的數學競賽對資訊競賽的直接影響

我在問卷裡面收到了非常非常多各式各樣的問題，諸如問某些參考書推不推薦，codebook 如何準備等，有些問題我還在想要怎麼回答，或到底要不要回答 ... 但有一個問題是這樣的：

　　玩資訊競賽的人，有不少人是由練習數奧的人轉進來(似乎是越來越多，不知是否為錯覺)，感覺能力都很強，能否談談先練數奧的人有哪些優缺點，還是根本差不多。

這問題一直以來我都很感興趣，畢竟我自己就是個從數奧轉進來的例子，所以想談談我的看法。

先列一下我所知道的一些資料。

　　　　　　　　　數學　　　　　　　　資訊

95級

蔡政江          　　多年數奧金牌　　　　　高中時期或更以前就有接觸，大學時代表台大去 　　　　　　　　　　　　　　　　　　  World Final 兩次

96級

tmt514           　　2007數奧候補國手2          資奧金牌，ACM ICPC World Final 金牌
gloompisces　　  2006年數奧二階選訓營     參加多年台大培訓班97級
kelvin            　　國中有玩不少數學競賽　 資奧金牌，ACM ICPC World Final 金牌
takaramono   　　2008數奧金牌                      ACM ICPC World Final 金牌
johnathan79717    2008數奧銀牌                      大學畢業後時常玩 online competition
dreamoon              2008數奧候補國手2           大學時代表台大去 World Final 一次

98級
peter50216            2008數奧銀牌                      資奧金牌，ACM ICPC World Final 金牌

99級
shik            2010亞太數學榮譽獎(台灣 top10) 資奧金牌，ACM ICPC World Final 金牌
surwdkgo              2008數奧金牌                       資奧金牌
demipenguin         2009數奧銀牌                       有參加台大培訓班 (在隊伍中角色定位似乎是幫忙                                                                               想題目，比較少 coding)
b92paul                 2010數奧銀牌                       有 World Final 資格




離2008數奧愈遠的我就愈不熟了，似乎還有不少在玩資訊的人也都有盡過數奧選訓營？而再更年輕的人我就完全不知道了 0.0

並且，在早期 Codeforces Red Coder 還不到一百多人的時候，台灣的 Red Coder 根本就全都是有玩過數學的人！當中大概只有 shik 的數學和資訊程度是同時並進，其他人最初數學的程度都遠遠超過資訊的程度。

以上是數據資料，接下來是我個人的感想：

1. 實際上 ... 有很多人根本就每一科都很強嘛！去玩物理或化學也都能拿到金牌。但為什麼數       學轉資訊的人特別多呢？我覺得這是因為喜歡數學的人容易喜歡玩資訊，這兩科給人的感       覺比較像吧。

2. 在資訊競賽上，所需要的很多能力，都是強化數學能力過的人都具有的，甚至有些資訊競       賽的題目和數學競賽的題目有重疊。

3. 高中以前由於學校根本沒有資訊相關科目。電腦課不就只是個讓大家打電動的課嘛？甚至連不少資訊科系相關大學生也都視資料結構與演算法只是天才在讀的東西，普通的人不知道大概也能活的好好的。於是演算法的教育資源相對少，教育資源少，直接資訊競賽起家就變的不如從數學競賽起家。建立好完整的邏輯數學能力後在接觸資訊，反而變的直接從資訊入手還容易(？這只是我的猜想，因為實際上學數學的人其實也都花了大量的時間耶，沒有數學基礎而從國高中才接觸資訊怎麼可能和從國小就培養好數學能力的人比呀？)

甚至我覺得，數學和演算法真能分開嘛？或許把眼算法教育的部分內容直接納入數學教育也是不錯？


最後說說自己為什麼數學轉資訊。

實際上...，我不只玩資訊，我高中也玩物理也玩化學，但由於我並沒有像某些人那麼強能夠把奧林匹亞玩過一輪，所以我高中以前把心力幾乎放在數學上，其他科目大概就是打打小比賽吧？資訊我有打 NPSC，物理我也去參加過兩岸力學競賽，化學去玩玩清華盃化學競賽也是有得到銀牌接近金牌的成績。我就只是個很愛玩理科的學術比賽的人罷了 Orz (我也要嘗試接觸生物，但是覺得太過需要大量記憶，相關比賽也很少，就放棄了... ) 所以，真要說為什麼我從數學轉資訊，答案大概是：大學以後還有很多比賽可以繼續玩 ...。另外一個理由或許是因為覺得參加資訊競賽的有趣程度遠高於其他科目競賽，但我有確切的這種感覺也已經是上大學之後的事了。

想認真參與資訊競賽的小朋友們啊～你們真的覺得數學不好能放著不管嘛～由其是離散數學的部分包括排列組合可是非常重要哪。

小月的出題之路

開始寫這樣的文章，就好像我不再打算出題的感覺 XD
啊啊啊但最近覺得我生出來的題目都落入俗套好不開心喔。乾脆退休好了 OAQ

以下正文 ( 含有某些題目的提示，請小心服用 )

前言

關於我的出題的相關訪談， Topcoder 曾經簡單的訪問過我 (連結在此)。但現在我改成使用中文，可以聊的更多 :P

　　演算法競賽非常有趣的一點就是：任何人都可以輕易出題，題目俯拾皆是，生活上遇到的大大小小問題，都可以經過一些化簡或聯想就變出一道題目，只不過大多數變出來且你自己會解的題目大都很簡單就是了。舉例來說，我現在要拿衛生紙來當題目好了 (剛好看到桌上擺著一包衛生紙 XD)，現在臨場想一題，我會怎麼想呢？首先，我會先想想有什麼和衛生紙有關的事件，於是我想到了：有時候我們在抽衛生紙，會不小心一抽起來就是兩三張。那麼我就根據這樣的事件隨便亂編一個題目如下：
　　
　　我有一包全新的衛生紙，共有 $n$ 張，每次抽的時候可能會抽到 $1 \sim 3$ 張，若把整包衛生只每次抽的張數記錄下來，直到整包抽完，請問記錄下來的序列有多少不同的可能？

　　這樣儼然就生出了一道題目，雖然這題其實就只是非常普通的矩陣冪的題目而已 XD

　　所以我會說，出題是一種藝術，當你聯想能力愈高，就愈能變出樣貌豐富的題目。但大部分的人應該並不希望只能生出一蘿筐的簡單題。

 　　但直至今日，我從來不覺得我能生出困難的題目，畢竟所有我生出來的題目都是我自己在短時間 (只想了一天也會被我歸為短時間) 內就解的出來的題目，而且至今我出的題目，除了程式碼或邏輯過複雜的題目外，都有人能夠在僅僅幾個小時的比賽內就解出來，所以客觀的來看都不算太難。以上當然是由我自己的標準來評判的，或許對很多人來說還是覺得我有出了不少難題。所以我有種感覺：當我本身的程度到哪，我能出的題目難度就到哪。

當上培訓班助教與出題

我大量出題是從大學四年級時當了台大培訓班的助教開始，那時我的程度和現在相比差多了，那年我出的題目相較最近出的題目都簡單上許多，甚至當時有些題目我只是想了題目敘述 (idea)，但我自己並不會做，解法則是由另外一位助教 kelvin 和我討論幫我解法的。

　　此時我就已時常使用我前言所述的方式出題目。例如，那時我很愛玩 Facebook 的 Tetris，我就用 Tetris 的方塊出了一個 bfs 題。又例如，我一直對台大 7-Eleven 九折折扣方式是五捨六入感到興趣，就以這個當作主題出了另一道題。那時出了很多題目的感覺真的很開心。

　　我和 kelvin 是學校住宿同房間的室友，我們時常在宿舍房間內一起討論出題，你說一句，我補充一句如此這般地把一些題目建構起來。我們也會有思緒不周或卡住的時候，這時會由另一個人來補足。所以我覺得，在出題時和別人討論是很有幫助的。

　　除了用聯想的方式出題外，我也會設定某個演算法主題來出題，例如說：我為了要出一個二分圖配對類形的 flow 題，就聯想到了學校排課表，已知每個老師有空的時間和需要上課的時數，請給出一種排課表方法。不過此時我用此方法生出來的題目都很裸。

解題與出題的連鎖效應

　　有時出了較難的題目是因為我在解題時，讀錯題目意思。例如：Codeforces 516D。若歸納我以前至今出過的題目就會發現，這題的解法結構有些複雜、題目敘述有點硬拗，其原因就是這題是我三年前左右看錯題目而生出來的題目，可惜原題以不可考。

　　有時出的新題目是運用其他題目來當成起點做聯想而成的。例如：Codeforces 515C。這題就是我為了生這場 Codeforces Round，於是大量刷 UVa 水題尋找出題靈感，並看到了 UVa12765 後生出了該題。這樣的變化應該不會有人稱之為抄襲吧？

玩遊戲中的腦力激盪

　　在我生的題目當中，一些讓我最覺得得意的題目幾乎都是在玩遊戲的過程中生出來的。我在玩遊戲時常常會自己設定一些遊戲目標，或追求遊戲效率，而這些東西常常可以變成競賽題目。例如說 SRM 628 Div1 Hard ，這是我在玩 Candy Crush，想要達成每關都拿到三顆星的目標時聯想道的題目。再例如 SRM 639 Div1 Hard，這是我在玩 Criminal case 時，從遊戲中的餵小狗環節而聯想到的題目 (話說我第一次自發性寫非競賽解題類的程式就是用按鍵精靈寫餵寵物的功能...雖然我懷疑這種程度的東西能否稱為程式就是了 XD)。

　　其他令我連想到題目的遊戲還有猴子射氣球 (Bloons TD5)、神魔之塔等，而且我常常玩遊戲會玩到我把它們出成題目後才把該遊戲戒掉 Orz (當初在玩神魔之塔的時候我完全瘋掉了 Orz 曾以為我就會這樣永遠停不下來。但就在某天我把神魔之塔變成題目後，以那天為分界點，我從一天玩好幾個小時轉變成完全沒在玩 )

　　我以上舉的兩個 SRM 的題目都不算簡單，但為什麼我能生出它們呢？講白一點就是我本身的解題能力有到達這樣的程度吧，並且我也覺得大四以前的我解不出這些題目，所以若在大四時就有這些題目的 idea 或許也無法出成題目。但當自己程度也許不夠時，事情也許沒那麼糟糕，就如同前面所說，我大四剛開始出題時，有些題目我只有 idea，但解法是 kelvin 幫忙想到的。所以多找別人討論，或許能合力想出好題目。

出題的滾雪球效應

　　有在參加 Topcoder SRM 的人也許有發現，Div 1 和 Div 2 的題目常常長得很像，但其實問的是兩回事，這就好像，你在編故事時，讓它產生兩種不同路線。我也常在 SRM 上出題，我在產生那些題目時，幾乎都是先有了 Div.1 的題目，然後再把它改編成 Div.2。但也有少數時候，是先有 Div.2，再變成 Div. 1。要把題目改簡單或改難都是很有可能的。若想要看看世界上的大家都是怎麼改編題目的，可以從 Topcoder SRM 的考古題得到大量參考資料。

如何出好題或難題？

　　有人問我該如何出好題或難題？並覺得若先思考要考什麼演算法，而再去出題目，時常會被一眼就看穿題目是在考什麼。這該怎麼改進？

　　我談一下這個問題讓我想到什麼。(讀者回饋第一彈 XD )

　　大家可以先想想看，究竟是怎樣的題目會讓你一看到就知道在考什麼？這個問題大概很難歸納出所以然吧 XD 所以我們從反方向的角度思考看看，怎樣的題目會讓我們很難聯想到他在考什麼？

Dijkstra 三部曲

我拿 Dijkstra 這個最短路演算法來作舉例，大部分的 Dijkstra 問題就是題目告訴你一些點和一些邊，直接要你計算最短路，在多一點變化就是點的狀態避不是單純的一個點，邊也不是題目就給你一個邊的權重，你要好好的求出來，但大部分這類的題目你還是一看就知道是最短路問題，只是要好好的思考點和邊怎麼定。

　　首先我們來看一題：有至多 $n$ 個 $1 \sim 9$ 的整數，請問他們的乘積 mod $m$ 的可能值有多少？其中 $n,m \leq 10^5$。(source: TCO14 pickup match 某一題750，確切題目我忘記了，我找不到原題)

　　這題我第一眼以為它是數論題，可是再多想幾分鐘，發現它其時只是個 bfs。把每個數字都當成一個點，並把所有 $x$ 至 $kx$ 連一條邊 ($1 \leq k \leq 9$)，BFS n 步以內就行了。(若覺得困惑標題為何標題是 Dijkstra，做法卻是 bfs？請把這股疑問藏在心裡就好... )

　　再看看第二題：SRM 615 Div.1 Level 2。給一個圖，至多 $50$ 個點，每條邊的 cost 介於 $1 \sim 10^4$，問點 $0$ 至點 $1$ 有沒有長度恰為 $T$ ($\leq 10^{18}$) 的 path (可以非 simple)。

　　這題我想了幾乎整場 round，以為它是某種矩陣冪的題目，結果它竟然是 dijkstra ！

　　最後看第三題：NPSC 2014 高中組決賽 pH。有 $n$ 種不同的錢幣，告訴你每種錢幣的幣值，現在有 $q$ 個問題，問你有沒有辦法剛好用這些錢幣附價值為 $K$ 商品？ ($n \leq 50$，所有錢幣的幣值不超過$10^6$，商品價值不超過 $10^9$)

　　這題我想了十幾分鐘吧？想了十幾分鐘後突然就連想到第二題那題 SRM 的題目，之後我就會做了。所以這題也是個 dijkstra！難以置信吧！

　　大家覺得，這些題目是因為想要考 bfs 或 dijkstra，才生出了這些題目，還是因為先有題面，才剛好想到可以用 dijkstra 做呢？我不是出題者所以我無法回答，但我會猜答案是後者。我個人預設演算法才出的所有題目精巧度大概都比不上這些題，所以我覺得，先想好要考什麼，再出題目，要出的非常好可能有點困難...，但你們大可以反駁我我舉的例子太極端了 XD

　　但我們可以觀察一下這些例子有什麼特性： 1. 看到題目的第一眼，會誤會成是在考其他種類的算法。2. 一般最短路的問題形式被拿掉了，例如說：一般最短路是問 xxx 最小是多少？可是第二第三題都是在問：有沒有剛剛好湊成 xxx 的方法。

　　於是我覺得，要根據一個演算法出一個好問題，就要打破一般我們對該演算法的常見問題的既定印象，至少要把他改到你自己都不覺得自己看完題目能立刻想到該演算法，或是在該演算法上再疊加一些其他演算法來混淆視聽。

　　我覺得人腦在解題就是一個類似 machine learning 的過程，大部分的人腦構造應該差不多吧？如果你自己都覺得你看到這樣的題目敘述能直接聯想到演算法，那大部分的人應該也會有這樣的感覺吧？所以出題要出的好，要盡量把題目變成你會覺得過了幾天你再重看這題可能就無法立刻想到做法了。

對不起我也是個抄襲別人 idea 的人...

其實我沒要道歉的意思(誤)。接下來我要以自己出的題目舉例，當我想考某個演算法或其他題目的 idea，我是怎麼對題目加工來讓別人感覺不出我在抄襲。

　　首先請看 NWERC 2011 Piece it together。當初我解這題是使用 2-SAT 解的 (這題也有其他做法)，且我覺得這題的 2-SAT 的運用方式非常好，於是想把它變成擷取精華變成其他題，於是就生出了這題：2014 TCO Algorithm Celebrity Match, Level Three。把它加入平面座標，以及 binary search 等元素。應該很難和我 idea 的來源題目聯想在一起吧 ...？

　　再另外一個例子是 Codeforces 515 E。這題實際上我是從 IOI 2008 Islands 改編的，但它整個模樣都被我破壞掉了，從一個徹底的圖論題變成一個徹底的資料結構題，大家能找到這兩題的相似之處嘛 XD

　　再回到有人問我的問題：如何針對一個演算法，創造出一個難題或好題？

　　由我自己的例子來當做答案，那答案就是：去尋找該演算法你所認為的好題，然後去進行大規模的改造。

出題的傷心事

　　出題還是會預到很多挫折的，例如說自己覺得題目出的很好很難，可是在別人眼裡看來卻是相當直覺相當簡單，或是被認為和某些已存在的題目太像。有一場 SRM 我出的 Div.1 Hard，比賽結束後，有人在 Codeforces 說他以前在其他地方出過一模一樣的題目。我看到後整個崩潰。現今全球性和地方性的比賽加總起來，我相信一年全世界的題目產出量應該有幾萬題吧？若真的有相同的題目由不同的人想出，也是很有可能的。

　　出題出太多時也容易自我感覺良好，可能會讓自己對題目的難度失焦，這個時候或許就要多和其他人討論，多問問看其他人的意見，來平衡一下自己的感覺。最近我就覺得我對題目的直覺與否的感覺完全跑掉了 Orz

前人種樹，後人乘涼

　　為什麼我卸下培訓班助教後還是一直出題呢？我覺得我是受黃上恩 (卡恩, aka tmt514) 學長的影響吧，當初我在當助教時，學長就主動的幫我們出了好多題目，而且好多題目都超難的！就覺得學長能出這麼多難題好厲害。並且學長也私底下辦了飲料盃比賽，還自掏腰包買獎品，雖然參賽人數有點少，可是相信有參加的人都玩的很盡興。有人這麼做，而且成功了，那我何不也來玩玩看呢？

第二屆飲料盃要來囉～

　　這篇就以宣傳 tmt514 下個月要辦的飲料盃做結吧～請參考 FB活動，沒有 NTUJ 帳號的人也可以向 tmt514 聯絡取得臨時帳號～一起來共襄盛舉吧！

Codeforces Round #299 (Div. 1)

這場官方 Editorial 賽後馬上就公佈了，而且寫非常仔細。

點我連到官方 Editorial

比完這場我有一個關於閱讀題目的小感想：當題目敘述裡面出現我沒見過的名字時(如：Tavas、Karafs)，會使我讀題目讀得很不順，每看到那些名字就會卡一下...

Problem A --- Tavas and Karafs

題意：有一個無限長的等差數列，首項為 $A$，公差為 $B$。共有 $n$ 組詢問，每組詢問包含三個正整數 $l, t, m$ 。對於每個詢問，請找出最大的 $r$，使得我們能執行至多 $t$ 次中括號內操作 --- [ 在數列裡把至多 $m$ 個相異數減 $1$ ]，使得數列第 $l$ 至第 $r$ 個數都不超過 $0$。

數據範圍：$1 \leq A, B \leq 10^6$ ， $1 \leq n \leq 10^5$

tag：[ 貪心 ] [數學]

關鍵字：度序列
= = = = = = = = = = = = = = =
引理：無論是否為等差序列，一個序列 $h_1, h_2, ... , h_n$ 能滿足題目的條件的衝要條件為：$\max (h_1, h_2, ... , h_n) \leq t$ 以及 $\sum{h_i} \leq  m * t$。

由於對於任意詢問，若把 index $x$ 選為右界能滿足題目條件，則對於所有 index $i$ 滿足 $l \leq i \leq x$，也一定能滿足條件。所以就可以使用 binary search 了。
數據範圍有特別設計，讓你 binary search 時的運算不會超過 long long，不過你還是得小心一點，binary search 時的右界不能設太大。

關於這個引理的證明，可以使用數學歸納法，請直接參考 tutorial 吧。

我覺得這題的概念和簡單二分圗的度序列判別很像，證明也很像。我們可以把引理的問題想像成這樣：
　　有一個二分圗，已知二分圗其中一邊有 $t$ 個點，每個點的度數 (degree) 都是 $m$；令一邊則有 $n + m*t - \sum{h_i}$ 個點，當中的 $n$ 個點度數分別是 $h_1 \sim h_n$ ，剩下的點度數都是 $1$。而這樣的圗會是簡單圗的充要條件就是 $\max (h_1, h_2, ... , h_n) \leq t$。

給定二分圗或一般圗的度序列問是否否存在一個簡單圗滿足這樣的度序列，是可以很有效率解決的問題，有興趣的話可以 google 看看可參考 wiki：degree sequence、Havel - Hakimi algorithm。

二分圗度序列判定的題目：CEOI 2010 Bodyguards

Problem B --- Tavas and Malekas

題意：有兩個字串 $s$ 和 $p$ ，已知 $s$ 字串的 index $y_1$ , $y_2$ , ... , $y_m$ 開始長度和 $p$ 字串一樣長的 substring 和 $p$ 一樣 (有可能還有其他一樣的位置，不一定全列給你)，問 $s$ 有多少種可能？

數據範圍：字串長度皆不超過 $10^6$。

tag： [ 字串比對 ]

= = = = = = = = = = = = = = =
這題就只是個字串比對的練習題，我覺得沒有比較特別的地方。

除了某些位置的字母題目已給定，其他位置都可以'a' ~ 'z' 隨便填，答案會是 $26^K$，$K$ 是無法從題目得知字元是什麼的位置數。

所以這題的解題分成兩部分： 1. 快速的填入所有已知的位置 (要填下一個子字串時，直接忽略已經填過字母的位置) 2. 重新驗證所有 $y_i$ 開始的子字串是否和 $p$  一樣，這部分可以用任意字串比對的方法做到。

Problem C --- Tavas and Pashmaks

題意：有一個競賽包含游泳 $x$ 距離和跑步 $y$ 距離，有 $n$ 位參賽者，給定這 $n$ 位參賽者的泳速和跑步速度，請問在我們不知道 $x$ 和 $y$ 的實際值的狀況下，有哪些人可能第一名 (和其他人同時到達算是並列第一)，輸出請按照所有人的邊號輸出。

數據範圍： $1 \leq n \leq 10^5$，所有速度為不大於 $10^4$ 的正整數。

tag：[ 計算幾合 ]

關鍵字：三項鐵人

= = = = = = = = = = = = = = =
這題...我以前見過更複雜的版本(POJ 1755 Triathlon，有三項運動，可以輕鬆搜到一堆題解)，兩項運動的也有見過其他類題但找不到了。我想這題題解講的非常仔細我就不說了。

是說賽中我想都沒想，只憑記憶覺得似乎和凸包有關，就亂猜了一個做法結果 WA 了 OAQ。

Problem D --- Tavas in Kansas

題意：有一個無向圗，每個點有一個整數權重， Tavas 和 Nafas 用這個圖玩一個遊戲。Tavas位於 $s$ ， Nafas 位於 $v$。遊戲如下：兩人輪流， Tavas 先，輪到的人要選一個值 $x$，並標記所有與自己的點距離不超過 $x$ 且尚未標記的點，並獲得所標記的所有點的權重和當做分數，至少要標記一個點。直到所有點都被標記後遊戲結束。在所有人採最佳策略下，誰會嬴(或平手)。

數據範圍：圖的點數不超過 $2000$，邊數不超過 $10^5$，圖是連通的。點的權重絕對值不超過 $10^9$。

tag： [ 最短路 ] [ dp ]

= = = = = = = = = = = = = = =
這題的圖啊根本是多餘資訊，我們只要保留每個點的到 $s$ 、 $t$ 的最短路距離的值就夠了，把這些距離離散化後，就可以開二為記憶體來 dp 。最直覺得 dp 是 O(n^3)，當可以改進成 O(n^2)，細節請參考官方 Editorial 吧，還蠻詳細的。

我有一個建議：當不知道要怎麼改進複雜度時，把 dp 時的轉移式寫下來用眼睛觀察可能就嘿知道要怎麼改進了。(雖然說這題我讀完題就知道怎麼改進複雜度了，但最後有些地方要開 long long但我只用 int 就爆炸了 OAQ。)

Problem E --- Tavas on the Path

題意：給一個樹，每個邊都有個值。定義一個 fuction $T$，input 為一個 01 字串 $s$，$s$ 有 $m$ 個連續的 $1$ 的區塊，第 $i$ 個區塊有 $e_i$ 個 $1$，則 T 的 output 為 $\sum_i{f_{e_i}}$ ($f_i$ 是給定的值)。現在有 $q$ 個 query，每個 query包含三個樹 $v, u, l$，請回答兩端點為 $v, u$ 的路徑上，若邊的值 $\geq l$ 則視為 '1'，否則視為 '0'，把這些字元按照路徑上的順序接起來，代入 function $T$，請輸出 output。

數據範圍：$1 \leq q \leq 10^5$，$2 \leq n \leq 10^5$，$| f_i | \leq 1000$，$1 \leq$ 邊的長度 $\leq 10^9$。

關鍵字：[ 樹鍊剖分 ]

= = = = = = = = = = = = = = =

這題看完大概就知道他是樹鍊剖分的題目，英文叫做 heavy-light decomposition。請 google 可以查到非常多資訊。

簡單來說，就是把 tree 拆成很多 path，讓每個詢問都只會通過 O( log n ) 個 path，並在每個 path 上用線段樹解決部分問題。也就是說，你如果會用線段樹解決 Tree 退化成 Path 的狀況，就可以用樹鍊剖分來多一個 $log$ $n$ 解決問題了。細節請參考官方 Editorial。

針對本BLOG的問卷調查

我自認是演算法競賽的愛好者，也許「愛好者」這個詞太好聽了，大概要說成「成癮者」吧...對我來說，參加線上演算法競賽的感覺，就如同普遍的人在打 LOL、魔獸之類的遊戲的感覺吧。

但自從動畫不起眼女主角培育法在一月撥出後，我深受其內容感動，覺得自己都當了那麼久的消費者了，不如當一下生產者吧！希望能對台灣的演算法競賽界能有所貢獻。於是就心血來潮，決定寫下自己所參加的每場 SRM 和 Codeforces 比賽的解題報告。

寫 BLOG 至今已經過了三個月了，只有漏掉兩三場左右吧，效率還算蠻高的。但有時會這樣想：「我寫這些題解能對大家有所幫助嗎？比起寫這些題解，是否有其他方式能給予台灣的演算法競賽的愛好者們更多幫助呢？畢竟這些題目的題解官網都有了。」大家有和我類似的感覺嗎？

現在覺得，與其閉門造車，不如問問大家的意見吧，我建立了以下的問卷調查，希望大家能把自己期待在 BLOG 裡看到什麼和我說說，甚至歡迎提供一些很瘋狂的主意(請參考問卷解說)，預先謝謝大家 m(_ _)m。

問卷連結在此：http://goo.gl/forms/QlXF0zEz48

Codeforces Round #298 (Div. 2)

這場的題目敘述偏長有些題目都是閱讀題 ( 要自己根據題目發生的事件來判斷有哪些限制，如 pB 和 pD )，對英文不好的人大概很吃力吧 ...

Problem A --- Exam

題意：給找出正整數 $1 \sim N$ 的最大的 subset，使得可以把這個 subset 的所有數排成一列，使得相鄰兩個數的差的絕對值都不是 1，並給出任一種排列方法。
數據範圍：$N \leq 5000$。

tag：[構造]

= = = = = = = = = = = = = = =
身為 Div 2 A 的構造題，應該就是個隨便亂構造都構造的出來的東西吧？合理猜測大部分的 $N$ 值都有辦法找到一個 $1 \sim N$ 的排列滿題目條件，只有 $N = 2, 3$ 時例外。

我除了特例以外的構造方法可直接參考我的 code 。

Problem B --- Covered Path

題意：有一台車共行駛 $t$ 秒，第 $1$ 秒的速度是 $v_1$，第 $t$ 秒的速度是 $v_2$。每一秒內的速度都是等速，相鄰兩秒的速度差至多為 $d$，請問這 $t$ 秒鐘最長的可能行駛距離是多少？

數據範圍： $1 \leq v_1, v_2 \leq 100$，$2 \leq t \leq 100$，$1 \leq d \leq 10$

tag：[ 數學 ] [ 物理 ]

關鍵字：斜率
= = = = = = = = = = = = = = =
某種程度這題算是閱讀題吧？要確實理解題目所說的物理意義。若把此題的物理意義移除，則會變成：有 $t$ 個數 $a_1, a_2, \cdots , a_n$，已知$a_1 = v_1$，$a_t = t_2$，任相鄰兩數差都不超過 $d$，請問所有數的總合最大是多少？ (你若問要是速度出現負數也能這樣轉變題目嗎？我並不清楚，題目關於速度是負的似乎沒寫清楚要怎麼考慮這樣的狀況。)

轉換完題目後就比較好思考了。我們會希望每個數愈大愈好，考慮 $a_1$ 及 $a_t$ 對所有其他數產生的限制會得到不等式： $a_i \leq a_1 + d * (i-1)$ 以及 $a_i \leq a_t + d * (t-i)$。並且直接令 $a_i = \min(a_i + d * (i-1), a_t + d * (t-i))$會滿足題目條件，於是得到能使這 $t$ 個數總合最大的序列了。

這個解法其實是很常見的概念，我印象中 SRM中 Div1 Easy 裡根本有簡化後一模一樣的題目。

另外，由於這題的數據很小，所以也可以使用 dp 來做，$dp[x][y]$ 用來儲存 時間 $x$ 速度為 $v$ 時從時間 $1$ 至時間 $x$ 所能行駛的最長距離。

Problem C --- Polycarpus' Dice

題意：有 $n$ 個骰子，第 $i$ 個骰子的可能結果為 $1 \sim d_i$ ，已知擲出來的骰子結果為 $A$，請對每個骰子輸出一定不可能骰出的點數有幾種。

數據範圍： $n \leq 200,000$，$1 \leq d_i \leq 10^6$，$n \leq A \leq d_1 + d_2 + \cdots + d_n$。

tag：[ 貪心 ]

= = = = = = = = = = = = = = =
個人覺得這題比 B 還要簡單耶？可是 B 的 AC人數還是多很多。這題 pretest沒有會爆 int 的測資，所以可以 hack 到大量只開 int 的解。

對於一個骰子，不難想像他可能骰出的值的範圍是連續的，所以只要求出他最低可能值和最高的可能值就結束了。最高的可能值就是其他骰子的值盡可能小的時候，也就是 $\min (d_i, A-(n-1))$，而最低的可能值則是其他骰子的值盡可能大時，也就是 $\max (1, A-(\sum_{x=1}^n{d_x}) + d_i)$

Problem D --- Handshakes

題意：有一個資訊競賽活動，每個新進場的人都要和在場的所有沒有正在比賽的人握手，且任何時刻在場的任三個人都有可能組成隊伍並開始比賽，直到活動結束，在活動結束前不會有任何人離開會場。給你每個人進場時各和多少數量的人握手，請判斷給你的資訊是否有某種符合的所有人進場順序，若有，請給出一組解。

數據範圍：人數不超過 $2*10^5$。

tag：[ 貪心 ]
= = = = = = = = = = = = = = =
這題我看了大家的 code 後發現有各種做法，我就講一下最多人使用同時也是我使用的方法。

一樣先簡化一下題目，把他變成比較正統的數學描述方法。
若把這些人的握手數按照進場順序寫下來($d_1 \sim d_n$)，必須滿足以下三個條件：

1. $d_1 = 0$
2. $d_i % 3 = (i-1) % 3$
3. $d_{i+1} \leq d_i + 1$

我想了一下下後直覺告訴我這題是貪心的題目，若要使用貪心，一個很常見的方法就是，每次決定下一個數時，直接選擇最大的可以用的數，而在這題這樣子做會是對的，而且將有很好的複雜度。

實作方式如下：
1. 設一變數 $v$ 代表我們想要取的值，初始值為 $0$。
2. 若存在握手數為 $v$ 的人，則把他當作下一個進場的人，並且把 $v$ 值加一。
3. 否則把 $v$ 值減 $3$ 並回到步驟 2，若還沒取到 $n$ 個人 $v$ 值就變為負，則答案為 Impossible。
 可參考第一名的 code。

我們不需要擔心步驟 3 執行太多次，因為所有過程 $v$ 的減少量不會超過 $v$ 的增加量加二，而會增加 $v$ 值的步驟 2只會執行至多 $n$ 次，且每次只加一。

至於此方法的正確性嘛 ...有一類的貪心法證明是長這樣：若存在某個解答長的和我們構造出來的的不一樣，一定有辦法經過一些變換變成和我們構造出來的一樣，於是若存在解則我們的構造法一定也能找到解！

於是我們先假設，我們若找出的解答，則會是 $d_1, d_2, \cdots, d_n$，以及現在存在另外一組解答為 $a_1, a_2, \cdots, a_n$。
若序列 a 和序列 d 不同，必有一最小的 index $i$ 使得 $d_i \neq a_i$，並且由於 $d_i$ 是可以挑的最大的數，所以我們可確定 $d_i > a_i$，接著我們令 $j$ 為大於 $i$ 的最小的 index 使得 $a_j = d_i$，接下來我們想要選一個 index $k$，使得我們能把序列 $a$ 的第 $i$ 個數至第 $i+k-j$個數整段能無痛的和 第 $j$ 個數至第 $k$ 個數交換。舉個實例：

$d$ 序列為 0,1,2,3,4,5,6,1,2,3,1
$a$ 序列為 0,1,2,3,1,2,3,4,5,6,1

則 $a$ 序列和 $d$ 序列第一個不同的數的位置是 4，並且在 $a$ 序列中 $d_4 = 4$ 這個數下一次出現的位置是 $a_7$，而我們發現我麼可以把藍色這段和紅色這段交換就變成 $d$序列了！分 case 討論後可以證明，令交換的子序列為最長的子序列，滿足 紅色子序列的所有數比對應到的藍色子序列的數都還要來的大(嚴格)，則一定可以交換。(我覺得兩個子序列緊接在一起的 case 並不太好證。但總之我確實把所有 case 都證過了。)

實際上並無法總是只交換一次就把 $a$ 序列變成 $d$ 序列，必須交換數次才能讓同樣的 prefix長度增加為序列長度。

徵求精減的證明 >_<。

Problem E --- Berland Local Positioning System

題意：公車站共有 $n$ 站，公車會從第 $1$ 站出發直到第 $n$ 站，再折返回第 $1$ 站，並一直反覆。有一個人他把上車到下車時所經過的所有站的編號記下來 (包括首尾站，並且他可能繞了好幾圈才下車)，但你只知道這些邊號排序後的結果，給你每站之間的距離，請問你是否能確定這個人搭了多長距離的公車？

數據範圍： $n \leq 2*10^5$，給的編號序列一定合法，序列長度為 $m$ ($1 \leq m \leq 4*10^5$)

tag：[ 模擬 ] [ 兩個指標 ]

= = = = = = = = = = = = = = =
賽中我花在 hack 的時間太久，回來寫這題時已經來不及寫不完了＠＠賽後也懶的寫完...

我想到的方法如下：

令 $d_i$ 為數字 $i$ 在序列中出現幾次，則任意合法路段，把序列 $d$ 按照連續相同的數字分段，一定不會太多段。於是我們可以用一些 tuple $(L ,R ,num)$ 來代表邊號 $L \sim R$ 的公車站都個別出現 $num$ 次。

所以我們就枚舉搭公車的起點，在枚舉開始方像為左或右，由於我們知道他搭公車的站數為 $m$，所以可以快速求出上一段所說的行式，就可以比對看看和這個人所搭的公車有沒有一樣。一樣的話就可以檢驗此種公車路線長度是否和至今合法的路線長度都一樣。

這個做法細節想起來有點複雜，會令人不想寫下去,,,

現在我們再多想一點點。

若先隨便選個點當起點，並經過 $m$個站，我們就得到了其中一種經過 $m$ 佔的公車路線。接著，我們只要把此路線的起點向前移一站，同時也把終點向前移一站，就得到另外一個公車路線了！共移 $2n-3$ 次就可以把所有可能的公車路線都試過了 =口=

於是我們可以輕鬆的使用 map 等資料結構來記錄路線的狀態有沒有和題目所給的序列一樣。

以上第二個方法是我看了第一名的 code 才發現的。

Problem F ---  Simplified Nonogram

題意：Nonogram是個類似數讀的遊戲，以一個 $n*m$的表格，請你把每一個都塗成黑色或白色，使得每一行及每一列連續的黑格段數都和測資指定的一樣。任一種填法皆可。

數據範圍：$1 \leq n \leq 5$，$1 \leq m \leq 20$。

tag：[ DP ]

= = = = = = = = = = = = = = =
我看到這題就立刻聯想到我在 SRM655 出的 Div.2 Hard，畢竟數據範圍長的那麼像...，於是我就直接從 dp 的方向去思考了。這題比我出的那題麻煩，還要輸出解...，很難讓不同層的 dp 共用記憶體。我用來儲存代表每一列的狀態數有 $21$ 那麼大，記憶體若要開 $21^5 * 20 * 2$ 不知道是否開的起來...，但我想說應該亂寫都會過吧，就不開陣列來 dp 而直接使用 STL 的 map。但寫完後使用 Codeforces 的 Custem Invocation 測了一下發現會 TLE ... 最後靠著 "用非常多map代替一個 map" 以及 "一定沒有必要走到的 status 都不要塞到 map裡" 就 AC 了。其實應該只需要靠第二個方法，因為它能減少大量的狀態數。

賽後開了別人的 code 發現，直接開陣列記憶體其實有辦法開的起來,,, (只是要想辦法只使用bool 或 char)。

我 dp 的方式是以 column 的順序 dp，每加一個 column 就更新每一個 row 的狀態，每個 row 的狀態有：已有幾條連續的黑格，以及最後一個是黑的還白的。應該算是平淡無奇吧？就狀態維度有點多令人感到有點煩而已。

而我所位的一定沒有必要走到的狀態是指：若存在某一個 row ，後面無論如何塗黑白格都無法達成目標的狀態。

ZeptoLab Code Rush 2015

這場比賽是 Div.1 和 Div. 2 一起比的，而且共有七題，比 2.5 個小時。

賽中我只寫了前四題 OAQ 賽後賭氣似的把所有題目都寫了一遍，所以這算是近期頭一場我真的有親自寫過所有題目的Div. 1 Codeforces Round。

點我連到官方 Editorial

problem A --- King of Thieves

題意：給一個僅包含 '*' 和 '.' 的字串，請問是否存在恰 $5$ 個 '*'，他們的位置是成等差數列。

數據範圍：字串長度不超過 $100$。

tag：[ 模擬 ]

= = = = = = = = = = = = = = =
有各種做法，我的做法是枚舉等差數列的開頭位置和公差，逐一判斷。

Problem B --- Om Nom and Dark Park

題意：給一個完全二元樹，每個邊上都有一個正整數的權重，現在你要把一些邊的權重加上一個正數，使得所有 root 到 leaf 上的的路徑權重合都相同，請問所有邊要增加的值至少多要多少？

數據範圍：樹的深度至多為 $11$。

tag：[ 貪心 ]

= = = = = = = = = = = = = = =
tag 設為 [貪心] 可能有點怪怪的，還是要把他當作數學啊？

從 root 到每個 leaf 的路徑上權重合都一樣，可推得給定任一點 $x$，則 $x$ 到所有在他 subtree 下的 leaf 的路徑上的權重合也都一樣。所以我們難免想要從比較小的 subtree 先考慮。

使用數學歸納法的方式去思考：
現在我們先考慮只有三個點的完全二元樹，他只有兩個邊，根據條件這兩個邊值必須相同，那顯然最好的情況就是把比較小的那個邊加上兩個邊的權重差的絕對值。

接著我們考慮有 $2^n-1$ 個點的完全二元樹，我們先個別把 root 的左子樹和右子樹(也就是大小為 $2^{n-1}-1$)用遞推的方式各別解決，然後把 左/右 子樹的 root 到 leaf 的路徑權重合加進 root 連到 左/右 子樹的邊裡，把他想像成只有三個點的完全二元樹去解決就行了。

所以這題的時間複雜度是 $O(n)$。

Problem C --- Om Nom and Candies

題意：給五個正整數 $C，x1，v1，x2，v2$ ，請求出非負整數 $a，b$ 滿足 $a*x1+b*x2 \leq C$ 且 $a*v1 + b*v2$ 最大。

數據範圍：所有數不超過 $10^9$。

tag：[ 數學 ]

關鍵字：根號
= = = = = = = = = = = = = = =
這是個很常見的題目，例如說曾出現在 2011年上海的 ICPC regional，所以應該是一堆人都見過的題目，我也曾經很仔細的想過這題，印象中實際上可以做到 O(log(數據範圍))。我隨意找了一個 Blog大家參考看看根號數據範圍的做法吧。

而且 code 可以寫的非常簡短：rng_58 的 code (rng_58的說明)

Problem D --- Om Nom and Necklace

題意：給一個字串和一個正整數 $k$，問有哪些長度的 prefix 是形如 $A_0B_1A_1B_2A_2..A_k$，其中所有 $A_i$都是相同字串，所有 $B_i$ 也是相同字串，且 $A_i$ 和 $B_i$都可以是空字串。

數據範圍：字串長度不超過 $1,000,000$。

tag：[ 字串匹配 ]

= = = = = = = = = = = = = = =
賽中我看完題目後，列了一些字串就直接猜到結論了。所是用猜的，但也並不難證明。

結論：所有滿足題間的 prefix，都是某個基本的字串 $s$ 重覆貼個 $k \sim k+1$ 次貼出來的，貼的第 $k+1$ 次可以只貼 $s$ 的 prefix，例如說 $s = "abc"，k = 2$ ，那麼貼出來的字串可以是 $abcabc$、$abcabca$、$abcabcab$、$abcabcabc$ 四種。

證明分兩個方向，首先，若把 $A_iB_{i+1}$ 視為 $s$，則可推論所有滿足題目條件的 prefix 都一定由某個字串貼出來。接著令一個方向，設 $s$ 長度為 $L$，且貼的第 $k+1$ 次貼的長度為 $r$ ，則令 $A_i$ 為 $s$ 長度為 $r$ 的 prefix， $B_i$ 為剩餘部分，就能證出所有由 $s$ 貼出來的字串都會是滿足題目條件的 prefix。

知道了這件事後要怎麼做呢？

作法大至上分為 Hash 派、kmp 派、Z algorithm 派。
我不喜歡 Hash，因為 Hash有可能會被像我一樣的邪惡人士構造測資而被 hack，我也不喜歡 kmp，我覺得 kmp 很深奧 0.0 所以這類的題目我都使用 z algorithm。

使用 Z algorithm 後可以知道對於字串 $S$ 的每個 index $i$ ($0$ - base)，都能求出最大的 $Z_i$ 使得 $S[0...Z_i-1] = S[i...i+Z_i-1]$。
如此一來我們就可以知道當 $s$ 長度選作 $i$ 時，可以貼出的長度有哪些了。

Problem E --- Transmitting Levels

題意：給 $n$ 個正整數 $a_1, a_2, ... , a_n$，這 $n$ 個正整數是環狀排列的。有 $q$ 個詢問，每次詢問會給一個 值 $b$，問要如何把這 $n$ 個數切成盡量少段，使得每一段數字和都不超過 $b$。

數據範圍： $n \leq 1,000,000$，$q \leq 50$，$a_i \leq 10^9$，$b \leq 10^15$。

tag： [ 貪心 ]

關鍵字：環狀貪心
= = = = = = = = = = = = = = =

如果不是環狀，這題大概只有 Div.2 pB 的程度而已，只要從最左邊開始，每一段都取盡可能的長，不能再取時就把下個樹當作下一段的開頭。

變成環狀後要怎麼處理呢？直覺的方法就是枚舉開頭位置，然後作和非環狀一樣的事，但這樣顯然太慢了。

首先，至少我們都能夠 $O(n)$ 預處理求出，由每個 index $i$ 當開頭，最長的一段能多長(暢度記為 $l_i$ )。

接著，以下提供三種思路：

1.
無論從哪個位置開始，總是有一個時候會跨過第 $n$ 個數和第一個數之間 (我們把某一段恰結束在第 $n$個位置也列入考慮)，並且，我們就直接把跨過去的那一段當作最後一段。

若這樣想的話，我們就可以從後面 dp 回來了！dp 時要記錄兩個值，分別是，由某個位置當作開頭貪心去分段，要分段直到跨過去時，共分了幾段，以及最後一段結尾的位置。如果某個位置至結尾位置長度為 $n$ 以上，那我們就更新答案。此做法應該是相當好想好寫的一種。

關於這個做法，我覺得正確性並不明顯，有人和我相同感覺嗎＠＠？

2.
把 $l_i$ 最小的那一段挑出來(記長度為 $L$ )，那麼無論從哪裡當作起點 greedy，一定會跨過該段，所以我們就不妨直接枚舉那一段每個位置當作起點 greedy 去劃分段落，由於每一段長度都至少為 $L$，所以至多只需要 $O(n/L)$ 就可以知道由某個位至當作起點答案是多少，總共枚舉 $L$ 次，故每個詢問時間複雜度都是 $O(n)$ 。

這是Editorial 給的方法。

3.
若現在不是問你最小的環狀分段法，而是問你從所有位置切下去變成不是環狀後，最小的分段法個是如何。那麼以上兩個方法都不能用了。而這個方法仍可解決，但多了 union find 的時間複雜度。

首先把這 $n$ 個數字重複共貼 $3$ 遍，例如說 $1, 2, 3$ 就會變成 $1, 2, 3, 1, 2, 3, 1, 2, 3$。

以 $b = 4$ 作舉例，我們把所有 index 都當成是一個點，並且每個點都會向右連出去一條邊，連到以該 index 為起點，最長的段落能到達的右界的點，如下圗：

若一直把 $n$ 個數貼下去，將會是個無限大的有向森林。

我們若有知道從某個數當開頭，至少要幾要切成幾個段落，就等於在這張圖上問，從某個點當起點，至少要經過幾條邊才會跨過至少 $n$ 個點。

現在問們要使用 Union Find 來解決這個問題。在 Union Find 的過程中，我們還得記錄每個點到其所在 group 最遠的點的用通過的邊數。

Union Find的順序就由左到右一個一個加把邊兩個端點 Union 起來，以上圗來說，就是綠邊 => 藍邊 => 紅邊 => 綠邊 => 紅邊 => 藍邊的順序。我們只須考慮前 $2n$ 條邊。並且當我們union完第 $k$ 條邊時，我們就會發現第 $k-n+1$ 個點所記錄的到該 group 最遠的那個點所需的邊數，就會是由該點所代表的數開始當第一段，greedy 出來的答案。

Problem F --- Pudding Monsters

題意：在 $n*n$ 的表格中，每行每列都恰有一個擺有布丁，問有多少 $k*k$ 的子表格，也是每行每列恰有一個布丁($k$ 可以是任意數)？

數據範圍： $1 \leq n \leq 3*10^5$。

關鍵字：[ D&C ] [ 資料結構 ]

= = = = = = = = = = = = = = =

唔... 關於這題的解法我沒有特別想講什麼...，我賽後寫的方法完全參考 Editorial。

我賽中一直往資料結構的方向去想，可是我的腦袋對稍微複雜的資料結構實在是沒轍，但賽後看到了另外一個關鍵字：[ Divide and Conquer ] 就如同吸血鬼被打樁一樣... 因為我連想到了這題： sgu 512 Friendly Points，以 D&C 的做法而言這兩題超像啊....，同時 friendly Points 的類題也是日本 JOI 2013/2014 三模的題目かかし (日文解答)。過去雖然我知道有這麼一題存在，可是從來沒有寫過 Orz。

Problem G --- Spiders Evil Plan

題意：給一個每邊都有給長度的 Tree，有好多個詢問，每個詢問有兩個數 $x, y$，你必須回答，至多 $y$ 條 path 所覆蓋的聯通的邊集，且包含點 $x$，則邊集的總長度最大為多少？每個詢問回答玩才能得知下個詢問是什麼。

數據範圍：點數、詢問數不超過 $10^5$。

tag：[ 貪心 ]

= = = = = = = = = = = = = = =
我賽後才看了這題的題目，看完題目後的感想：這題不就是 POI 的題目在稍微變化一下而以嘛 = = 如果我在賽中看了這題而且 pretest 夠強的話應該能在賽中 AC 吧 @@
POI的相關題目是 POI 13th  stage 2 Subway，也可以參考 HOJ 101 捷運路線，和這題的差別就是沒有多組詢問，也沒有一定要包含某個點 $x$ 的條件。

有沒有做過 POI 那題真的對思考這題的時間差很多，另外 POI那題也和 Codeforces gym100020裡的 pH --- Tree 大有關係。Tree 這題問的是，給一個有根數，每次可以從root問某個葉子走下去並把所有邊塗色，問塗 $k$ 次至多能讓多少邊被塗上顏色。我會說 Tree 這題是 POI subway 的簡化版。

關於捷運路線這題可參考 這裡。

接下來我要說的是我解這題的方法的概念，實作細節我就不提了...

首先，把樹的中心求出來當作根，接著從找出離跟最遠的葉子，並把根連到葉子的路徑拔掉，之後會變成森林，在一值重複把森林中跟到葉子最遠的路徑拔掉，直到所有邊都拔完為止。如右圖，整張圖就被分成了 $8$ 條路徑。

對於每個詢問 $x, y$，如果點 $x$ 包含在最長的前 $2y$ 條路徑裡面，那麼答案就是前 $2y$條的路徑和。
否則我們就強制在最長的前 $2y$條路徑中，在多連一條與前 $2y$ 條路徑包括 $x$ 的最長路徑，如下圖， $y = 2$，最長的四條為非黑色的路徑，點$x$是圖上標記的紅色的點。顧我們把紅點連到綠點的綠色路徑也加進去，於是目前就滿足了包括點 $x$ 的條件，但是現在多了一條路徑，於是我們必須要刪除一條路徑，而刪除的路徑我們只須考慮兩種選擇，第一種是藍色路徑綠點一下的半截，第二種事原本 $2y$ 條路徑中最短的那條(紫色路徑)。

我想這個做法是非常直覺的，但證明和實作上就必須加把努力囉。

比賽debug側記---把自己的思緒說給別人聽的好處

這篇也是紀錄有關某場比賽的事，不過只特別記錄其中一件插曲。

應該有不少人都聽過黃色小鴨除錯法吧？我個人相信這招對 debug 真的很有用，由其是在正式比賽中心浮氣躁的情況下用這招效果更是顯著 (把隊友當成黃色小鴨之類的)，常參加團隊比賽的人或許多少都有這種經驗：當自己debug許久但都找不到bug，於是就要把自己的作法說給隊友聽，請隊友幫忙debug，但說著說著忽然自己就發現 bug 了！這個時候，其實你的隊友的地位就和黃色小鴨一樣而已XD畢竟他什麼都還沒做，只是在用耳朵聽你說。

3/29(日) 受人邀請組隊參加了 UTPC，是個主要給日本人參加的比賽(題目都用日語)，不過藉由翻譯功能，多少還是能看得懂題目，並且真的讀不懂的地方可以向日本人的隊友確認。

但這場比賽我的表現實在欠佳，不知是太久沒比團隊比賽還是對第一次組的隊伍不習慣，總之這場我只寫了兩題 pD，和 pH，不過隊友們很罩就是了，最後還使勉強上了記分版上的第三名，唉唉不過大家看到我們這隊的組成應該還是會覺得比的不夠好吧 XD

這場比賽題目共分成 100 分、200 分、300 分三種，照記分版來看 pD 應該是 200 分以下最麻煩的一題，但實際上難度頂多只有 SRM Div.1 500或Codeforces Div.1 pC 左右吧，這裡就不提他了，我要談的題目是 pH --- 回すだけ，是個互動題。整場比賽我花了將近兩個半小時在上面 ...

題意：平面座標上有一個凸多邊行，其中一個頂點座標是 (0, 0)，其他頂點座標你都不知道，你只確定它至多 $10$ 個頂點，每個頂點座標皆為整數，並且所有內角都在 170 度以下。現在你可以問至多 $1000$ 個問題，每個問題都形如下："把此多邊行繞著原點逆時針轉 $x$ 度後，y座標的最大值是多少？"

互動格式：當要問問題的時候，以一個 '?' 加一個空白作開頭，後面接一個浮點數 $x$ 代表你所問的問題中的 $x$。當要回報答案時，答案有 $n+1$ 行 (n為凸多邊形頂點座標)，每行都以 '!' 加一個空白做開頭，第一行僅包含一個數 $n$，第二行之後，由 (0, 0) 開始往逆時針回報所有頂點座標。

這題應該不太難，我想了幾秒就想到一個做法：每一個詢問等於我們可以知道這個凸多邊形在哪個半平面裡，並且我們若以 $1$ 度為間隔詢問 $360$ 次以上，那麼原本的凸多邊形頂點，一定在這$360$ 次詢問所得到的半平面的交集的凸多邊形頂點上。那我們就大膽的相信，求半平面交後的凸多邊形上的所有整數座標頂點搜集起來後，就是答案。

實際上有更精簡的做法，不需要使用半平面交，只需要求線段交點就有辦法得到答案，但這裡就不提了，畢竟我的重點是在於這題的 debug 。

總之這題就解法而言其實相當單純，但麻煩的就是很難測試自己程式碼的正確性，它的 Sample 很不親切，完全就只有格式上的舉例而已，於是我就把我的程式分區塊，用我自己的方法檢驗其正確性，大致上無誤後就 submit 了，但是卻 WA了 ... 我再仔細看了一次題目，發現要輸出 $n$ 但我沒有輸出，但是我改了這個 bug後還是 WA。

接下來我又測了很多東西，但真的完全找不到錯誤，於是我又完全改寫做法，改用不需要半平面交的做法(畢竟半平面交我是直接使用 codebook ，很擔心 codebook 其實是錯的 Orz)，但還是 WA 掉了，甚至拿到 TLE，真的是莫名其妙呀...一直在考慮要不要把互動的 Judge 程式也寫一份來對拍看看是否正確，但是覺得好麻煩就放棄了。

我就這樣測了好久好久 ... 後來隊友來問我這題到底盡展得如何，我就開始向隊友說這題我實際採用的方法，以及我覺得可能出錯的地方和疑點，說著說著我突然發現，問問題時前面要加 '?'，但是我卻加成 '!' 啊...該不會我 debug 那麼久就只是因為這樣吧？之後修掉這個 bug 後就 AC 了。並且實驗證時，AC的八十分鐘前上傳的 code也是修掉這個 bug 就能 AC。

真的非常對不起這場比賽的隊友們 OAQ