結果晚七其實也不是什麼好時間。還好 GKS 的難度一般來說偏低，所以中間跑去邊做事邊想題目還是可以的。
破台時間是比賽終了前 15 分鐘，排名 188 名；不過如果不計滿分魔王 Q4 大測資的話，到 Q4 小通過的時間是 1 小時 23 分鐘，大約才用去一半時間而已。
照例分數截圖以下有雷。
Q1. New Password
簡單題。
Q2. Range Partition
這題是 GCJ 1A Q2 的簡單版。那時的題目是我們要構造出一組數讓某個範圍內都有解，而這題則是給定了你要用 1~N 這些數來構造某個範圍內的解。構造的方式其實很類似，甚至還更接近 UVa 10025 的構造法，所以就不在這裡多敘述了。
Q3. Ants on a Stick
這題的關鍵是一個觀察：把螞蟻的路線給畫出來可以看到其實可以不讓它們碰撞，就當做互相穿過就好了。這樣一來，掉落時間就直接把所有螞蟻直走掉落的時間給搜集起來就好了。至於是誰掉落？可以證明，朝向兩個方向的螞蟻數是固定的，不管如何碰撞，因此最終所有左邊的螞蟻會往左掉，所有往右的螞蟻會往右掉，這樣就能對出誰在什麼時候掉落了。實際寫起來最後這一步就和合併排序法類似，兩個指標自兩邊往內掃，誰先掉落就輸出誰，一起掉落就先輸出小的號碼即可。
Q4. Palindromic Deletions
首先先提一下這題的輸出格式：這其實是和去年的 GKS Round H Q4 是一樣的，所以就請參考那邊了。
這題的簡單做法是對所有子序列進行 DP。DP 式很好推：每個位置都刪刪看，求所有這些結果的平均值，然後如果這個子序列本身是迴文就再 +1 就行了。這樣做的狀態數是 \(2^N\)，每個狀態要跑一次所有位置，所以總時間是 \(O(N\times 2^N)\)，是個讓小測資能過的做法。由於我前三題做完只用了 40 分鐘，時間雖然滿充裕不過有點轉不開到底要怎麼算大一點的 N，所以決定先寫了一份 DP 解送上去，送上去的時間就是剛才提的約莫中場。
後來想到大測資解法的關鍵是：既然我們只要求期望值，那把每個對期望值有貢獻的東西分開看如何？
到底什麼東西對期望值有貢獻？就是遊戲過程中出現的迴文。把所有 \(N!\) 種過程列出來吧：考慮一個子序列長度 \(K\leq N\)。全部的 \(N!\) 種刪除過程中每個長度為 \(K\) 的子序列都有出現，而且都出現一樣多次，因此特定一個長度為 \(K\) 的子序列有 \(1/C(N,K)\) 的機會出現在遊戲中。如果這個子序列是迴文，那它就對最終的期望值貢獻了 \(1/C(N,K)\)；那我們只要把所有這些貢獻全部加起來就是所要求的期望值了。
因此我們要求的其實是：每個區間 [x,y) 當中，長度為 k 的迴文個數。這是一個三維的 DP 式：區間 [x,y) 的長度 k 迴文個數可以用排容求出來，它等於區間 [x+1,y) 的長度 k 迴文數，加上區間 [x,y-1) 的長度 k 迴文數，減去區間 [x+1,y-1) 的長度 k 迴文數；如果兩個端點 [x] 和 [y-1] 相同的話，還要再算上區間 [x+1,y-1) 的長度 k-2 迴文數 (加上這兩個端點也是迴文)。區間個數是 \(O(N^2)\)，迴文長度最長是 N，所以 DP 空間是 \(O(N^3)\)，對 \(N\leq400\) 是輕鬆過關。
至於我在那之後送到第四次才過的原因是……算排容時溢位了。每次都被溢位婊……
小結
GCJ 敗陣之後只好在 GKS 裡找回一點點自信了。雖然中間跑去寫了只能過 Q4 小測資的做法就是。(汗)
這次滿分一共有 223 個，而少 Q4 大的 73 分約有 300 個，算上中間其他的分數後 73 分的最低名次是 553 名。果然 Q4 大這個魔王不好打……
GKS 接下來在 6 月底有個練習回，然後 Round D 是 7/10。是說感覺這裡變成 GCJ 紀錄用了……之後看看能不能找些別的題材來寫寫吧。