好狠的 Round 1A……配分是 10+15/31/13+31，只做前兩題說不定還晉不了級－－從我破台開始，1500 名一直都是 Q1 Q2 的 56 分，而因為這個配分的關係，下一個分數是 Q1 Q3 的 69 分，再上去就是破台了，所以基本上可以說晉級線一定是 Q1 Q2 的 56 分，只是劃在解題時間多少而已。
至於為什麼沒有 Qualification Round 的文章……這次的 Q Round 給五題，不過前三題是基本題，第四題需要想一下，第五題才是鑑別題。然後我做了前四題，第五題因為抓不到一個關鍵的思考點所以沒做。既然最有得寫的第五題都沒做出來了，我再寫些簡單觀察就跟題解重疊率太高就沒寫了。
回到 Round 1A。我在賽事終了前 50 分鐘左右「破台」，這時的暫時名次約 370 名左右；賽後發現 Q3 大 WA 了只得 69/100，不過還有約 500 名。照慣例分數截圖以下有雷。
Q1. Double or One Thing
很容易觀察到一個字母要不要複製是跟它後面的字母有關，不過不僅僅是後一個字母。第二組 Sample Input 就給了一個很好的例子：10 個 A 的字串正解是一個字母都別複製，因為只會得到 10 至 20 個 A，當中字典順序最小的是 10 個 A。
所以要看的其實是連續相同字母之後的下一個字母，如果比自己大那就複製，否則 (比自己小或是到字串尾都相等) 就不複製。字串長度 100 所以直接寫過去就行了。
Q3. Weightlifting
最簡單的想法：所有人共同的槓片上去之後就到最後才會下來。不過其餘的槓片要怎麼排才是問題；稍做思考之後可以發現，必然存在中間某一次練習，在更換到這次練習的過程當中槓鈴上的槓片只有所有人共同的槓片。因為若這不成立，則除所有人共同的槓片外還至少有一個槓片也會一直待在槓鈴上，那那個槓片就也得是所有人共同的槓片，矛盾。
知道這一點之後，題目就很簡單了：對每次練習都當做上面定理中的那次練習來計算結果，取最小值即為答案。因此這是個很標準的 DP 題目，由小區間答案拼成大區間的答案。
至於我 WA 的那一次……則是想太多了。上面說存在某一次練習是這種狀況，我原本以為會是某一個槓片放上去後把有那個槓片的練習儘量做完才拿下來，不過回頭看時才發現被第三組 Sample Input 打臉了－－這組測資是在練習１到練習２當中出現只剩共同槓片的狀況 (步驟是：共同的 AABC 先上，再上一個 A 做練習１，拿下 A 依序上 BBCCA 做練習 2，拿下 A 做練習３)，但這個假設會捨棄這個組合，假設練習１的 A 會留到練習２結束，因此就輸出 26 了。原本為了這個怪條件把最小值的初始條件拗了一個奇怪的設定把這組測資矇過了，WA 了一次回來想了好半天才發現原來是這一點想太多。
然後……賽後發現大測資 WA 了。(倒) 大概是哪個小地方沒寫好吧。等等來找找看。
Q2. Equal Sum
這題我其實一開始就已經有初步想法了，只不過還是因為想太多沒有仔細考慮才先放著下去做 Q3。
很久很久以前解過這麼一題 UVa 10025：給定式子 \(?\ 1\ ?\ 2\ ?\ \cdots\ ?\ n = k\) 及 \(k\) 值，找出最小的 \(n\) 值使得存在一個將 \(n\) 個問號替換成加或減時式子能成立。稍微做一點數學可以發現，對於特定的 \(n\) 值，所有絕對值小於等於 \(\frac12n(n+1)\) 且和其同奇偶的數都能做出來：首先全加當然就是這個和數；少 2 的話把 1 改成減；少 4 的話換把 2 改成減；依此類推，到少 \(2n\) 時把 \(n\) 改成減，少 \(2n+2\) 時除了 \(n\) 外再把 1 改成減，等等。繼續推下去，最後到所有數都變減時就是負的和數。UVa 10025 在有了這個觀察之後就是簡單的數學式操作而已了。
同樣的技巧可以用在這一題上：如果我們能將對方給我們的數分成差相對很小的兩組的話，我們可以用類似的技巧把我們選的數貼上去 (某種意味上就是分到加組跟減組) 就能得到和相等的兩組了。為了讓這個「相對很小的差」儘量大一點，這裡不選用 UVa 10025 的連續自然數，而是另一個數學謎題裡的常客：2 的次方數。利用同樣的證明和二進位的特性可以知道，如果我們選的數中有 \(2^0\) 到 \(2^n\) 的話，我們可以適當將它們分邊得到絕對值小於等於 \(2^{n+1}-1\) 的所有奇數差值；由於所有數字最大只到 \(10^9 < 2^{30}\)，我們可以花 30 個數在 2 的次方數上；N 一定是 100，所以剩下的 70 個數隨我們選。
要保證我們能得到小於等於 \(2^{30}-1\) 的差值，可以很簡單地貪婪分組：對每一個數，哪一組和比較小就丟過去，連隨我們選的 70 個數也一起丟進去；由於差值只會在丟數字進去後總和超過另一組時變大，但不會超過剛丟進去的數字，這樣就能保證 170 個數分完之後的差值不會比任何一個數還大，我們就能用同樣的辦法把 2 的次方數丟進去補齊。使用 2 的次方甚至不需要像 UVa 10025 一樣一個一個調：我們要把總和 \(2^{30}-1\) 的 30 個數分成給定差的兩組，解一個簡單的二元一次方程就知道哪一邊要分多少，再用二進位的特性直接丟數字進去就行了。
總結
賽後看了一下，破台的是前 304 名，69 分 (Q1+Q3 或 Q1+Q2+Q3小) 的人到了前 928 名，1500 名劃在 56 分且用時約 1 小時 1x 分的地方。果然這配分真的很硬……
GKS Round A 的時間因為有事在忙所以沒能參加，Round B 則是在 4/24 登場－－不過時間有點囧 (早七到早十)，所以不要太期待表現 XD GCJ Round 2 則是 5/14 下午，應該是個滿不錯的時間。就到時候見了。