Codeforces Round #302 參賽紀錄

這場的配分比較奇怪：500-1000-1750-1750-2500
看來這場的難度配置不單純 0.0

　　開場先看了 pA，把他列成式子會是一個多元一次不等式的整數解個數的問題，這類的問題一般來說都是使用 dp 做，於是就很直覺的寫了一個 dp。寫到一半發現不對，照感覺寫下去會是 $O(n^4)$，稍微多想了幾秒後，發現他是個另類前綴和類型的 dp，所以複雜度可以少一個 $n$。唔... 這樣的題目在 Div. 1 A 裡面算難吧... ?

　　接下來看了 pB，題目包裝的有點隱晦，題目說到要破壞盡量多的路...，立即閃過去的概念是 min-cut 問題，可是明顯不對 = =。馬上把他反過來想，破壞盡量多的路 = 保留盡量少的路，保留盡量少的路...其實就是求兩組點對的最短度？不對不對他們可能會有共用的路，所以要分兩個 case：兩組點對的最短路沒有相交，以及兩組點對的最短路交纏在一起。交纏在一起的話... 根本就是四個點的 steiner tree 問題吧...，三個點或四個點的 steiner tree 問題我看過好幾次了，所以這題和那些題目的差別就只在於多了點對間的路徑還有不能超過某個長度的限制，但這個條件還挺好判掉的。 這題的 code 感覺上有點長唉 ...，思考了幾秒要不要先看其他題，但最後還是決定先把這題寫完。

　　寫完 pB，我 lock 了 pA，大略的看了一下大家的 code，感覺都很正常，本來還以為說不定有人會寫 O(n^4)的做法 0.0 看來 pretest 大概有擋調。

　　接著看到 pD submit 的人比較多，所以我就先看了 pD。pD 題目很好理解，而且他看起來就很像常見的 dfs 兩次的 tree dp 問題(第一次只 dp 出每個 node 的 subtree 的某些性質，第二次在 dp初以每個點當 root的題目要求的性質)，我就靠直覺寫下去了。

　　寫完 pD 後， pC 還是只有少量的人 submit，難道說他不簡單嗎>_<，於是我先 lock了一下 pB，先 cha 一下看看，因為這題一副就很容易寫錯的樣子。開了幾份 code 後看到有人漏了一個 case (很容易看出來，因為他 code 比別人少了一部分)，賺了 100 分！

　　讀了 pC，第一個想到的是，每個字串一定可以靠著改變任一字母來達到題目要求，但，之後呢？這是 min-cost 類 flow 題嗎？感覺不像，要不然 $n、m$ 要更大才對？先想一下還有什麼 case 會讓某些字串滿足條件。若有某個位置，有 $k$ 個字串在該位置有相同字元，那我們就可以改變當中 cost 最小的 $k-1$ 個字元，使得這 $k$ 個字元都變的不一樣！於是，我們可以掃過 input 後得到好多 $1 \sim n$ 的 subset 以及對應的 cost，代表我要讓這個 subset 編號的字串們都滿足條件至少要多少 cost。到這裡，以經可以確信這題是位元 dp 問題了，但實際上究竟要怎麼 dp？好為難喔...，回憶眾多記憶中的位元 dp 方式都不對，如果對於每個 set 子集，都還要枚舉該子集的子集，複雜度太高了。但沒必要枚舉到子集的子集吧？只要枚舉一些重要的子集就好了。這部份我想的有點久 ... 最後總算注意到，所有的 (子集, cost ) 的對數至多才 400 對！$400 * 2^{20}$ 約為 $4*10^8$，常數小小的，以 Codeforces 的主機來說應該輕鬆 AC 吧 XD 許久以前也看過類似的題目，不過記憶模糊了 0.0。

　　在寫 pC 快寫完的時候， pD 竟然被 cha 掉了！？為什麼？我哪裡忘記 mod 了嘛？但後來看到 scoreboard 上大家被 cha成一片，可以相信這不是 mod 的問題，我暫時先把 pC 擱著，想了一陣子 pD 到底發生了什麼事。最後注意到，我 dfs 第二次時，有用到模逆的操作，難道說被構造了運算中會有 0 的模逆而造成不可預期的事態？唔...想到這裡，就決定暫時放棄解決這個 bug，先把 pC 寫完。

　　submit 完 pC 後，在認真回來想想 pD，先試著想想要構造出能 hack 這樣的 bug 的測資是否很困難，但腦袋有點鈍鈍的，無法清楚思考要怎麼構造。不管啦，先回來看看我要怎麼修掉這個 bug，然後才發現我原本的 dp寫法並不太好 ...，超難修 bug的啊！後來就把整個 dp 的部分重寫了 ... 由於要修的部分太多，所以我沒有在時限內修正完成  OAQ

 　　賽後問了一下學弟，pD cha 了那麼多份 code 確實是依靠我賽中想到的那個 bug cha 的，賽後我大概又花了約五分鐘把這個 bug 修補完成並 AC。最後 rank 37，以目前我的 rating rank，這樣的名次還是足以讓 rating 增加 84，若能維持這樣的 rating 增加率，要回到至高點還需要三場！