2016 Google Code Jam Round 3

官方題目、比賽網站（可下載練習用測資並judge）
這篇文章跟先前的GCJ文不一樣，沒有打算要寫成豐富的題解，只是流水帳式的記錄比賽過程罷了。

這是我第一次晉級Round3，明知道不可能，還是會做一點進到onsite round的夢吧XD
所以今天特地早早回到宿舍、洗澡，然後好像離開始還有半小時以上就開啟電腦檢查各種設定。
（尤其上次DCJ Round1的時候還有發生斷網驚魂... 宿舍網路感覺很抖，尤其我的位子網路孔是壞的，卡不住，每次線掉之後都要試很久才能找會能接觸的狀態QQ）


終於比賽開始了！

一如往常先看pA，讀完之後先想到很基本$O(N^3)$的DP作法，
（這份沒有要打很正式，所以其實不是$N$，反正將來的我跟來看的人應該都能理解吧）
然後還想說這長相該不會是四邊形不等式壓到$O(N^2)$的題目吧XD
可是$O(N^2)$出這範圍有點太大了，而且四邊形不等式在這題也沒那麼有道理。
最後我就決定先寫單純的DP解掉small，解掉上傳完之後看一下分數......(A small 14m 07s)
怎麼全世界都直接把large解掉的感覺啊！！！

那麼也不用考慮什麼四邊形了，一定是比較單純的東西，這題說不定有greedy那類的性質！
然後在紙上試一試，覺得這個作法有點機會：從左邊掃過去，如果跟stack頂端一樣就配對，否則就塞進去，但是處理一下結束要讓stack空掉。
說實話想到這個作法覺得他好假喔...不過也不難寫，就直接寫出來用small測看看，對的話就傳吧！
（因為Round2 pB也是用small結果相信他對的...雖然那次想到作法我就覺得他蠻對的XD
後來在CF也看到很多人是用small測完就傳的，所以這次很乾脆就這樣下定決心orz）
然後就很順利地通過small的檢查並上傳了。(A large 21m 11s)
（large我會傳完之後再重新下載input/output檢查一下）

現在再來仔細觀察一下分數分布：
pB 只有small，25分
pC small跟large合起來也是25分
pD 正常的small+large，分數總和比25高

解large還有賽後爆掉的可能，上傳時也要比較謹慎，我覺得自己在剩下三題想要有超過一題完整解開應該需要一點奇蹟吧。
然後pD解開large感覺就希望渺茫，這樣的話比較有把握的最佳結果應該是pB small先解掉，而且small不會賽後爆掉，這麼多分的small成功的話能穩定心情，後續節奏也會抓得比較好。
總之，在一串斟酌之後決定先看pB！
（這時候還沒有什麼別人的狀況可以參考，只有少少幾人解了pC small而已）

讀完pB認真想一下，這種計算大概的比例鐵定就是random了。
然後很直接的寫下來，結果範測就錯了QQ
仔細弄一下，發現我從待選的課當中平均的隨機挑一個是錯的！
然後再過一下子就想到機率應該是跟依賴那個課的數量成正比，
（我是想成拓樸順序那樣，所以就是那個點的後代數量）
實作的時候不知道為什麼很順的取反向圖的拓樸順序DP出來...上傳結果WA了！！

當時是隨機10000次，其實已經有點慢了，但是就想說先試試看1000000次會跑多久。
擺著跑然後去看pC~

pC讀完覺得small超簡單而large沒想法，
（其實pB的一點挫折應該有影響我這邊的思考，總之我沒深入思考就只想把pC的small寫掉穩定軍心）
開始寫的時候發現1000000次太好笑了，怎麼可能跑得完XD
換100000次測一下多久，然後開始寫pC small了。
寫到一半，發現100000次花了2m 4xs，還可以，就很衝動的再試了一次pB。
還是WA掉QQ

這才先專注地處理pC，這麼簡單的small上傳...竟然也WA了！
然後發現我讀錯題目了，我以為只是從點0開始一直跳（不在同一點待超過S秒）就好了，其實是目標抵達點1。
沒關係，小事而已，修一下，用$O(N^2)$的dijkstra揍他...又WA了QAQ
花了一下子de到bug了，反正就是code裡打錯東西，不值得一提...這才終於通過了(C small 1h 32m 15s)

先回來看pB，
想說還是構造一點對人腦友善的測資測一下，
發現真的完全錯了，
仔細的debug，
找到我做DP取的拓樸順序根本沒有反邊啊orz
改一改用剛剛構造的測資測，覺得10000次已經足夠了，就用10000次上傳，也終於AC了！(B small 1h 46m 56s)

認清事實吧，我怎麼可能再解出任一個large然後衝到很前面呢？
乖乖的來看pD然後寫寫small也差不多就是整場比賽了...

於是就寫pD small，
很順的想出構造方法，結果又WA了。
這場真是諸事不順，各種簡單的部分爛掉嗎...
還是打起精神來找bug！
這題可能WA的地方很多：
我的構造方法，大概像這種模式10?10101010 ???，可能會有：

1. 後面問號數量錯了
2. 前面01不夠
3. 其實這樣構造不出所有非全1的字串
4. 總長度太長

大概就把這些都仔細的檢查了，還是沒有找到問題啊QQ
該不會又是題目讀錯了吧...
回去重讀一遍看到這行"Each program must contain at least one instruction."，
誒！該不會是L等於1？
看一下這真的在範圍內，於是趕快特判上傳，終於過啦！(D small 2h 15m 53s)

剩下兩題的large，這樣不到15分鐘不知道能幹嘛，就差不多休息了，只是很隨興的想一下D large然後想不到。

---

比賽結束，A large沒有噴掉耶！

最終成績 55pts 2:35:53，Rank 115

恩，我本來就不是天才型的，目前為止有穩定的逐年進步已經很棒了吧！
從高一那年在Round1被刷掉、高二Round2 2000+、高三Round2 500+，到現在Round3 115~
雖然這場失誤太多了，如果扣掉的話成績應該會再好很多，今年GCJ結束在這邊也算滿足啦！
明天還有DCJ呢~

（之前想過要寫Round1題解、Round2比賽流水帳，不過我想應該不會寫了XD）