Codeforces Round #680 雜記

#第一次就上手如何跌出LGM

開粉專第一篇就來教大家如何上手跌出 LGM XD

= = =

今天最大的敗筆大概是賽前一兩分鐘還在和別人聊天以及因為這場比賽而沒能和老婆一起吃晚餐導致心情有點亂吧 (>__<)

以後還是不要打和吃飯時間重疊的比賽好了 (>__<) 

= = =

開場看了 A 題，題目簡單易懂

給定兩個數 p, q (p<=10^{18},q<=10^9)，請找到最大的數滿足 x 整除 p 且 q 不整除 x。

這題算是比較套路的，我第一個閃過的念頭其實是使用大質因數分解的模板來枚舉所有 p 的因數來 check 答案 XD。

但是在 10^{18} 範圍的 p，因數可能有超多個！所以必須減少需要檢查的因數個數。

要選哪些數呢？先不管要做什麼事情，反正有個常見套路就是要枚舉質因數。

那麼枚舉質因數能做啥呢？啊！只要 x 的某個質因數的次方小於 q 的質因數的次方就行了！

枚舉 p 的質因數似乎有些繁複，於是再多想一點就會發現只要枚舉 q 的質因數就行了！

枚舉 q 的質因數並把 p 一直除以該質因數直到不被 q 整除，那麼剩下的數就是 x 的可能候補之一，最後取最大的候補就好啦～

雖然我打那麼多字，可是這些思考大概是一分多鐘以內的事，並只用兩分多鐘就寫完了 code，在不到 4 分鐘時就過了 Pretest!

此時看了一下每題 AC 人數，發現 AC A 題的只有 8 人，而 AC B 題的已有 4 人！！！？？

= = =

接著馬上看 B 題，B 題的敘述很短：

給 2n 個數，把他分成 2 組各 n 個數，第一組為命名為 a_i， 且把它由小到大排序，第二組命名為 b_i 且把它由大到小排序。

每個分法的 cost 為 abs(b_i - a_i) 的總和，請計算所有分法的總和。

這題是前三題我想最久的題了...

這種題乍看之下也是個套入題，就是去算每個數字的對答案的貢獻。

於是我就開始去思考，每個數字在 cost 中是負和正時各有幾次，我列了好多次式子都無法把公式列清楚，看來我比賽前的心煩意亂在需要數學計算的時候就體現出來了 (>__<)

算了好久並且用程式寫了幾個式子都沒有過 Sample。

這時我提醒自己，可是有 4 個人在開場馬上就 AC 了，公式應該超簡單。

於是我就在計算紙上模擬一些實際例子。然後馬上就發現，前 n 個數對答案的貢獻總是是負的，並且後 n 個數對答案的貢獻總是是正的...

又再次的驗證，什麼都想不出來的時候，觀察一些 Sample 如何計算答案就有機會猜到答案...

= = =

前兩題都過了 pretest 後，比賽已過了 21 分鐘，可是還沒有人過了 pC 的 pretest，於是我覺定從 E 題看回來。

但是 E 題是個互動題 =口=，我看都沒看就跳看 D 題。

D 題看完並理解題意，是個構造題，據我經驗，構造題通常在思考上的不確定性太大，所以我想都沒想就直接看回 C 題了...

C 題題意如下：

給一個 Graph，每個點屬於 1~K 中的恰一個 Group，有些 Group 可能不包含任何點，請問有多少 Group Pair 滿足這兩個 group 的點所形成的導出子圖 (induced subgraph) 是個二分圖。(點數、邊數和 K 都不超過 5*10^5)

這時我有些急躁... 一剛開始我看錯題意了...，以為它是問有多少導出子圖的補圖有完全匹配...

於是就覺得，這題目怎麼看起來那麼難 =口=

花了一些時間後我發現，要解我讀錯的題目，我就能夠解出點數和邊數都超多的圖的一般圖匹配！

這不可能啊！結論=>我讀錯題了，於是我在重讀一次題...才發現問的是二分圖...

題目一正確後我就知道正確的做法，因為是判斷二分圖，並且算是有些動態的判斷二分圖，那麼和記憶中匹配的演算法就只有並查集 + 時光逆流了。

我使勁把他刻完了，又重寫了一次時光逆流...，以後應該也要把時光逆流的部分放入 codebook (此處應有思考的表情)

Debug 了許久，直到比賽剩 1 個小時的時候左右才過了 Sample。

原本想檢查一下再傳，但衡量了這題 code 有點長且已經沒有時間優勢了。我求勝關鍵要擺在多 AC 一題。所以值得賭賭看能不能一次就過 pretest，可惜失敗了 (此處應有哭臉表情)

首先馬上就抓到了一個 x,y 打反的 Bug...但再傳一次還是 WA。

接著我又花了好久時間都找不到 Bug... 中間又亂傳了一次，於是共錯了 3 次。

真的百思不得其解！我一定沒有 Bug！若有 Bug，那肯定是我題目又讀錯了！

於是我又再仔細讀了幾遍題目，然後發現....我的作法中殘留了原本讀錯題目時才會產生的條件：Group Pair 的總點數必須是偶數才有可能滿足條件 (ꐦ ಠ皿ಠ )

為什麼我多寫了這個條件還能過所有 Sample 啦...

於是我把這個條件移除後就過 Pretest 了...

= = =

還剩 40 分鐘

但我腦袋大概有點壞掉了。沒能冷靜下來思考題目，在試圖解 D 題的過程中慘不忍睹，這次就不把慘不忍度的過程記錄下來了 (>__<)，感覺沒有任何教育意義，純粹就是我腦袋壞掉...

比賽結束後原本的名次是一百多且 Rating 預測也是會減少一百多，不過評測結果有非常多人 C 題 WA 掉了 (此處應有困惑表情)，於是我名次以及減少的 Rating 數值都落回 100 以內。

明天還有一場 Div. 1 難度的 Codeforces 比賽，且這場比賽是 VK Cup Final 的題目！依過去經驗，VK Cup Final 的題目都會很精彩！請大家敬請期待！

2018 Facebook Hackercup Round 3 流水帳

由於前兩年都進了 Facebook Hacker Cup 的 Final，所以壓力有點大，因為我向來自詡自己能到達的階段是不太會退步的 XD

開賽時中規中矩的從 pA 開始看。今年的題目似乎比往常的短很多，也比以前還要容易理解，但這題就算理解了題目，也是沒什麼想法呀...，想了幾分鐘後，就決定想到什麼就寫什麼，例如說：我想到了若有連續三個井字號，則這三個井字號以及後面的字源可以全部不用理會。又或是若有連續兩個井字號，下一個字元不是星號也不用理會。

總之就是想了各種條件，大概就是又分成答案是 $0$、答案是 $1$、以及答案大於 $1$ 的 Case，其實也就三種 case 啦...但是真的很難想的清楚，所以我提交時已經過了 45 分鐘了。

但以開場來說，這個速度其實還算正常，我是第 30 個提交題目的人，但真的正常嗎？這也很難說，因為可能其他人不僅已經提交了一題，而且還把所有題目看完了，但我剩下三題都還不知道題意。

接著我選擇看第二題，題目理解後沒什麼頭緒，說是沒什麼頭緒也不對啦，總之一定有複雜度超高的 dp 方法能做，但實在是高過頭，想了一下對於壓低時間複雜度的方法毫無頭緒，於是決定先看第三題。

第三題讀完我腦中就猜了個 Greedy 類的做法，感覺還蠻對的，但沒有仔細證，可是時間複雜度是 $O(N^2)$ 而這題 $N = 30000$，嗯...依照 Hackercup 過去以來的尿性，真正 $N$ 是滿的測資其實很少，相信 O(N^2) 也是能過的！於是我就直接寫下去了！但為了讓心裡更有底些，我在寫的過程中，同時也想著要把常數壓小，導致雖然做法簡單，但還是寫了很久，終於寫完後，卻發現我 Sample 錯掉了！！！

這可怎該怎麼辦？看來看去，都覺得我的程式碼寫得很穩呀，到底是哪裡寫錯，還是有哪裡想錯了？仔細分析了一下挫的那組測試資料，實在是看不出所以然...

這時比賽只剩約 70 分鐘...完了...完了...感覺一切都完了...但我還是繼續拼命地動腦 QwQ

我一直在想著，我的 greedy 方法到底拿理會錯調，想著想著，我突然靈光乍現，想到一個更穩妥的 dp 方法，雖然一樣不知道是不是對的 XD 不過它超好寫，於是我迅速的把它揉完，並發現 Sample 因此通過了，也沒時間再驗證做法正確性了...總之就傳吧 (>__<)

看了一下 scoreboard，我大概落在五十幾名吧...而且只剩一個小時左右了，這時才開始讀新的一題並且想+寫感覺時間不夠呀...但是第四題這時有好多人傳了喔...感覺不寫第四題說不定就沒機會晉級了...所以我開始看第四題，繼續把第二題擱著。

第四題讀完後覺得不得了不得了，這題的感覺和 tmt514 在今年某場比賽初的某題有 87% 像呀... 於是我先想了一下下正確性到底如何，但是...感覺時間不夠讓我好好證明 tmt514 用的方法是不是可以直接套用在這題上了，但感覺就是很對嘛！於是我就把之前那場我寫的程式碼找出來，改了一下後， Sample 就輕鬆全過了...就直接傳了吧，傳完後我的名次就進到前 25 名了。

剩下半小時，我還是努力有想要寫出個 pB 的代碼，所以我也是想到什麼就寫什麼，但是寫到剩下 5 分鐘時，發現我寫的方向錯掉了，很難修正...於是就放棄了 Orz，剩下時間就盯著　scoreboard 看。其實這個時候我的名次已經遠遠掉出 25 名外很多了，但我真的沒辦法在做什麼了吧 (>__<) 就一直觀察著我的名次我後落...

四點一到， score board 刷新後，發現我竟然三題都通過了！！！勉強的重新回歸前 25 名！這真是太令我感到意外了(?)我...我...就這樣又進到 Hackercup finallist 了 (>_<) Facebook 的出題群是不是要檢討一下呀 XD 連三年都讓笨笨如小月我這樣的人水進 final XD

2017 Facebook Hacker Cup(FHC) 世界總決賽參賽紀錄

今年難得晉級了好多個總決賽，花點時間來把決賽的比賽過程紀錄一下，讓自己對過去所犯下的罪孽深重的錯誤有更深的印象 >__<

FHC 的決賽總共是四小時，今年總共有六題

開場先看了一下這次題目的分數分布：12-16-16-18-19-19

是標準的 AC 題數多名次一定比較前面的分數分布哪...(關於這件事我曾經出成系列題目XD Score Distribution 系列)

可以相信第一題一定是相較起來簡單很多的一定要拿到分數的題目

所以我豪不猶豫的從第一題開始讀起。

第一題題目意思是：

請問在所有每個數的值都介於 $1 \sim H$且大小為 $R \times C$ 的整數矩陣，把每行及每列的最大值按照順序寫成一個數組，請問有多少不同的數組？($1 \le R,C,H \le 10^5$)

題目意思雖然那麼簡短，可是題面包裝得很複雜，我至少看了五分鐘才看懂題目吧...

就第一眼的直覺，這題要不是 dp 就是純粹的組合數題，要點就是先掌握一下可能的數組有什麼關鍵性質吧，所以我就先畫了簡單的一些例子，並觀察到：所有行的最大值的最大值和所有列的最大值的最大值一定一樣，說這件事適用觀察到的應該還蠻蠢的啦XD總之這是個很理所當然也不須要怎麼證明的事情。

我注意到這點的時候...已經有人 submit 這題了...所以可以相信這題的 code 應該很簡短很好寫?

但注意到這點到底有什麼用呀?於是接下來就想要大膽猜測：所有只要滿足這個條件的任一組數組，都能構造出對應的矩陣。

於是我有事圖畫了很多例子想證明這件事，其實我也有想過不要真的去證明直接把它當作是對的，但由於就算這件事是對的也沒有馬上知道要怎麼做，所以還是先給個證明增加信心。

花了些許時間後終於證出來了，接下來下一步就是想個排列組合公式解這題，這邊我也花了些許時間才想到作法。

這題的做法很乾淨很簡短，可是我寫完的初版 code 並沒有過 Sample...

我又花了些許時間才 de 出 bug...

比賽過了約 30 分鐘我才 submit 了第一題

沒記錯的話，我大概是第 14 個 submit 這題的人吧，而且已經有人連第二題都 submit 了 0.0

開場就感到些許絕望...


接著看了第二題

這題題目敘述更是複雜了...

我看了 20 分鐘左右都還沒有足夠的理解題目，以至於一剛開始以為這題只是超蠢的二分圖判斷類的題目。

但寫完後 Sample 卻錯了好幾筆測資，接著 debug de了不少時間後，最後一個測資怎樣也過不了樣例，於是我下狠心用手畫圖親自用人腦解該筆測資。

為什麼我會說下狠心呢？因為該筆測資是有超過 20 個點的 graph...

後來我發現我對題目有些微的認知錯誤，或者是說，我作法想歪了，這題並不只是超蠢的二分圖判斷，而是先做完二分圖判斷後，若是二分圖，還得找個二分圖最小點覆蓋...

說起來，這道題很裸啊！！！只是他題目敘述包得很複雜而已，我很不喜歡這類的題目唉...

得到正確的作法後，我對原本的 code 在稍作修改，又 debug 了一陣終於過了 Sample，並 submit。


這時比賽已過了一個半小時左右，看了下 scoreboard，我的名次仍舊落在 15 附近的中後地段 (決賽只有 21 個人參加)

但比賽仍有兩個半小時，前面兩題事都算是我寫的很不順利，若後面的題目寫的順利些，應該還是有機會翻盤。

於是我按照順序先看了第三題

這題讀題也是花了不少時間吧...

理解題意後，想了一下覺得細節好複雜喔，沒有很好的思緒能理清該從哪裡下手解這題，這時再看看 scoreboard 

發現有一兩個先傳了第五題，於是決定再繼續看第五題

第五題倒是一下就理解了題目，且稍想了一下我馬上就知道怎麼做了!

就只是個矩行面積覆蓋類的線段樹問題嘛！

這時覺得說不定有機會名次衝上去了！


但剩下的兩個半小時已經沒什麼話好說了

一直以來我寫線段數的問題似乎都很容易卡住，這次也不例外

而且我找最久的 bug 竟然是線段數初始化的位置擺錯...超蠢的T_T

submit pE 時間只剩下一個小時， scoreboard上有許多人都已經傳了 5 題，已經傳四題的人更是多，

到這時已經拉開題數差距，再加上我讀題總是很慢，看來再怎樣我都頂多只能四題了

這時我稍微想了下，我要直接繼續想第三題呢？還是在開新題目來讀？

看了下 scoreboard，覺得寫A、B、C、E 四題似乎分數還是有點慘烈，但 F 也有可能因為比較難而到賽末都寫不完，並且此時傳 D 的人比 C 還多，於是我決定看 D 的題目。

這算是做了錯誤的決定吧...

不知道怎麼搞的，我讀題讀了 20 分鐘左右，卻對題目在搞什麼連皮毛都還沒摸到... 超慘烈的啊！！！是因為我太緊張了嗎？還是我英文就是真的這麼差= =

在比賽剩 40 分左右時我放棄理解 E 的題目意思了，回去思考 C 怎麼做。

這時大概心很慌吧，就開始想到什麼就寫什麼，Sample 錯了就想想到底還要補些什麼，直到比賽結束都一直在做這樣的事情。

比賽結束時只寫了三題，這時在 scoreboard 上的名次是第 16 名(先當作大家有傳就有 AC 來做排名)，超慘的啊。


開獎後，我 pB fail 了...故實際上只有 AC 兩題，最終排名為第 15 名。

這次前四名都是 AC 5 題，明顯感受到和大家的穩定性差距呀...(我說穩定性是因為，我沒答對的題目並不是我不會，只是我沒時間去理解或思考，因為花太多時間在寫其他題目上了...，剩下的題目我一定都能想到！)

P.S. 1 比賽結束過後，開獎過程中，我都一直在思考 pC 正確做法到底是什麼，大概想了 20 分鐘才想到，並發覺我賽中最初填上去的 code 離正解實在是太偏了，由那種 code 當起點東補西補怎麼可能改成正確答案呀...

P.S. 2 之後我看了再認真檢查我 pB 的程式碼，發現我最後傳的 code Bug超多，其實連 Sample 都沒有過... 只是不小心矇對了原本唯一錯掉的最後一筆測資，就被我當成所有測資都過了 Orz。

P.S. 3 最後六題 AC 人數分布為: 21、11、10、14、9、4。大概可以看出 B~E的難度根本沒什麼差...甚至 pD 可能還比較簡單，我 pD 讀不懂題目真吃虧...