今年的 GKS 多了這個練習 Session，雖然不確定用意是什麼不過也算是個練習，於是雖然最近有點忙但還是抽了時間把題目做一做了。
那因為反正是練習 Session 所以就不貼成績了。繼續閱讀開始有雷。
Q1. Sample Problem
環境設定 A+B 題。
Q2. Centauri Prime
字串練習題。
Q3. H-index
算是第一個比較需要考慮算法的題目了。
首先會想到如果只求一次，那最簡單的做法是排序後從最多引用的開始，逐一判斷是否找到所要的 h 值。不過既然是連續求值，很顯然的是我們會需要改成插入排序法，每插入一個找一次；但這每一次詢問其實並不必要從頭檢查，這是因為每插入一個論文頂多會讓 h-index 增加 1。
令前一次的 h-index 為 h。假設第 h-1 多、第 h 多、第 h+1 多引用的論文分別是 G、H、K，而新論文是 P。這表示 H 有至少 h 個引用，G 當然也至少 h 個引用，但 K 則是至多 h 個引用 (否則 h-index 就該是 h+1)。若 P 插入在 H 之後，那 P 也至多 h 個引用，所以 h-index 不會變動；若 P 插入在 H 之前，則第 h 名變成 G 了，它也有至少 h 個引用，所以 h-index 仍然至少為 h。論文 H 變成第 h+1 名，所以如果它的引用數也有至少 h+1 的話就能將 h-index 提升為 h+1；但不能再更高了，因為第 h+2 名的 K 引用數只有至多 h，是不足 h+2 的。
因此，每次新的論文進來只要一個判斷即可得到新的 h-index，總時間扣除排序便是 O(N) 了。不過這一題似乎對排序上的要求沒有很大，我用最簡單的 vector<int> 直接 .insert() 插入元素的寫法 (最差 O(N^2)) 也能過大測資……果然因為是練習回合就放鬆了嗎？
Q5. Milk Tea
先跳過來講 Q5，雖然我的答題順序是依序作答的……
題目很簡單：給定 N 個「需求」01 字串和 M 個「禁止」01 字串，找出一個不在禁止字串中的 01 字串，使得其與所有需求字串的差異數總和最小。對於小測資 (最長 P=10) 只要 1024 個字串下去搜一遍就行了，但大測資 (最長 P=100) 行不通；但禁止字串最多 100 個，所以如果我們能逐一由差異總和最小的字串開始看看在不在禁止字串內，那就很容易得到答案了。總和最小的字串很容易求，但要怎麼往差異較多的字串找上去？
關鍵觀察是，變動某個位元所增加或減少的差異數是能夠事先算出來的。如果這個位元有 3 個 0 和 2 個 1，那選 0 會有 2 個差異數，選 1 會有 3 個差異數，所以由 0 變 1 會多 1，由 1 變 0 會少 1；我們的目標既然是要找差異數總和最小，那不可能會需要做總和下降的變化 (因為已經試過了)，因此可以發現其他字串的差異數總和能夠由最小字串加上所翻轉的位元對應的總和上升量而得。因此我們可以在每次檢查字串時，判斷由此字串翻轉 1 位元能夠獲得其他哪些總和較高字串，再找剩下的當中總和最小的繼續－－這跟 Dijkstra 演算法的精神是一模一樣的，只是這裡沒有一個固定終點，而是藉由「翻轉 1 位元」建立的圖中第一個找到的未禁止字串。知道這一點後就很容易作答了。
時間複雜度方面，Dijkstra 本身是 O(V+E)，但因為我們只有在發現禁止字串時才會繼續走，最多只會看過 M+1=O(M) 個字串，每個字串有 O(P) 個下一步，因此這部份的時間是 O(MP)；而求出總和最小字串及各位元翻轉上升值只需要做一次各位元的統計，花費 O(NP+P)。總計只要 O(NP+MP)，簡單通過大測資。
Q4. Hex
我在這題卡了意外的久。簡單的分析可以發現到，不合法的盤面大略可以分成以下三種：
- 兩方石頭數量差異過多 (差至少兩顆)
- 最後一手不是盤上形成連續的該方
- 盤面形成不可能的多條連線
前兩項很好解決：1. 只要數一數就好，2. 則做一次搜尋判斷即可。問題在 3.，要如何檢查多條連線的問題。一個很容易的想法是，每次拿掉一個該方的石頭，再檢查一次是否仍然連線。這樣的做法，每次檢查的時間是 O(N^2)，而且所有石頭的數量也是 O(N^2)，因此總時間是 O(N^4)。對 N=100 的題目來說這個數量級有點在 TLE 壓線的邊緣，所以我一直在考慮到底要用什麼好一點的方法。
容易發現，這個「拿掉後檢查是否連線」的性質正是所謂的「關節點」(articulation point) 的性質。不過一般的關節點演算法會需要調整才能使用，因為我們只關心盤面的兩端是否相連，對其他也是關節點但並不分隔盤面兩端的點並不關心。我就是在這裡卡住了好一段時間，要找到一個適當的方式調整演算法不是那麼簡單的。
最後想通的關鍵是：在一般的關節點演算法裡，經由 low 判斷得知此點是關節點的時候，其實我們也一併知道了這個關節點將圖的哪一塊給分隔開了：由於它是在判斷之前剛回傳的遞迴路線，走此路下去的所有節點都無法走回 dfs 編號更小的節點，這代表這一團無法走回因此會被隔開的節點正是剛才的遞迴所用到的所有 dfs 編號。因此，當將盤面兩端也視為一個節點進行操作時，我們可以固定由一邊出發，進行普通的關節點演算法，只是在每次遞迴前後紀錄當下的 dfs 編號；當判斷得到一個關節點時，紀錄下來的編號區間就是被隔開的點，因此只需判斷代表盤面另一端的節點是否包含在這個範圍裡面即可。時間複雜度上，這樣的紀錄只有在每次邊的遞迴呼叫時進行紀錄，最多進行 O(V) 次，不影響全體時間 O(V+E)；而這個盤面的邊數量至多也是 O(V) (每個點至多只有常數個邊)，因此總時間也就是 O(V) = O(N^2)，是個比較令人滿意的時間。
總結
那就是這樣了。這幾個星期因為有事有點忙，不過影響應該還好。今年 GCJ 三月報名，Qualification 在四月，應該是不會被這陣子忙的事影響才是。