今年開始有這個地方就來寫個和以前一樣的解題筆記好了。其實這本來應該是上週 GKS Round A 就要先開始做的，不巧那一回在週日凌晨，有些事情卡著沒辦法凌晨參戰只好延到這次。
繼續閱讀開始有雷。
Q1. Reversort
認真看完題目之後，這題就只是很簡單的模擬題，要怎麼反轉就照做就行了。利用 STL 裡的 min_element 和 reverse，還可以把內層迴圈藏進去 XD
Q3. Reversort Engineering
然後就先跳來這題題目前半一模一樣的題了。這題是反過來，給定反轉總花費構造出列表來。
可以發現總花費是有上下限的：對 \(n\) 個元素的列表，總花費最少是 \(n-1\)，最多則是 \(2+3+\cdots+n=n(n+1)/2-1\)。觀察反轉過程，可以發現每一步的花費可以在 1 到剩餘元素數之間選擇，因此我們只需要適當安排元素來選擇每步的花費即可。由於反轉是一個套一個的關係，倒過來選擇花費會比較容易操作；因此構造方法就是：準備已排序的列表，從倒數第二個元素開始，貪婪地在不讓後續沒有花費的前提下滿足剩下的花費。
這個方式顯然不會得到和 Sample Output 一樣的輸出，不過這題是 Special Judge 所以沒問題。以第一個範例 4 6 為例：
- 已排序列表是 1 2 3 4
- 有三步選擇，花費分別 1~2、1~3、1~4
- 所以在儘量滿足的方式下三次反轉由後到前的長度是 2、3、1
- 序列變化是 1 2 3 4 → 1 2 4 3 → 1 3 4 2 → 1 3 4 2，即是輸出
Q2. Moons and Umbrellas
這題要做的事很簡單：填滿中間的問號使得總字串的 cost 最小。不過因為 cost 只跟相鄰字母有關，這個字串的 cost 其實可以想像成在一個兩個點的完全有向圖上走路，走過的邊有 cost，要最小化走固定步數指定起點和終點的 cost。
既然是固定步數，這其實就只是個簡單的 DP 結構；由於圖上只有兩點，狀態只有四個，DP 遞迴式可以完全寫開：
C...C = C...CC + C...JC = min(C...C, C...J+JC) C...J = C...JJ + C...CJ = min(C...J, C...C+CJ) J...C = J...CC + J...JC = min(J...C, J...J+JC) J...J = J...JJ + J...CJ = min(J...J, J...C+CJ)
這是給定頭尾 (就是問號在字串中間的)，如果是在字串頭或尾的話就要考慮頭或尾是兩種的哪一種了。全問號的題目乍看不需要做，不過 Bonus 的 1 分有負 cost 的就需要考慮了，所以就也寫進去了。(反正對沒有負 cost 的輸入也會正確跑出 0 所以沒差)
Q4. Median Sort
每年都會來的互動題。
如同題目所說，這種排序法無法分辨整個序列是正的或反的，不過除此之外的順序卻能問得出來。特別的是，我們可以問出一個數字是該排在已有序列的哪兩個數中間。這就很直覺地能夠聯想到插入排序法。
插入排序法有一個很常見的改進比較次數的方式，就是每次都使用二分搜尋尋找插入位置。詳細方法是：最開始的三個數直接問一次就能提供排序基礎，隨後的二分搜尋對已有的 n 個元素中的 n+1 個空間，詢問新元素是否放在這空間正中間的位置；如果回答中位數是新元素，那就在正中間，否則就是在回答那數的那一邊。
實際寫出來就可以在統計上看到平均 170 次詢問是足以排序 50 個元素的。後來我用 Mathematica 簡單算了一下，對 50 個元素的平均詢問次數約是 162.4 次；這和實際測試時給出的 100 組測資總次數約略 16300 次是相符的。
不過，由於這是一個三元詢問，因此其實可以把二分搜尋改成三分搜尋：把搜尋範圍切成三份，詢問新元素是否在正中間那一份當中。由於 \(O(n\log n)\) 的對數底數由 2 變成 3 了，排序 50 個元素的平均詢問次數是會下降的，實際數字是約 145.5 次；不過考慮到原題是給 170 這個邊界，應該是有意要讓二分搜尋也能通過就是了。
Q5. Cheating Detection
果然我對統計類的題目還是完全不行……
很大略地說，這題是要你在 100 個根據某個分布選取的有 10000 元素的樣本中，選出其中分布和另外 99 個不太一樣的那一個。詳細上來說，題目有給定大部份樣本的「分布」(是個根據邏輯函數決定機率的伯努利試驗)，而不一樣的那個則是這樣的分布加上一個變換讓他能有好一點的成績。
因為完全沒想法，只好用點估計方式來嘗試猜測各個人和各個問題的隱藏參數，但實際上因為這個估計很不準的關係 (對問題參數只有 100 個樣本點)，效果其實很差，連測資一的 10% 都達不成。在思考了一天 (加上大白天倒在床上睡了好一會兒) 之後，才總算拋掉估計參數的大方向，直接去用給定的樣本去算。
會想到這個方向的原因其實和題目特別使用邏輯函數決定機率是有關的。如果認真的去把想估計的參數的最大似然估計給求出來的話，會發現不論樣本點是答對還是答錯，因為邏輯函數的特性，似然函數 (的對數) 的微分中各項會變成差不多相同的項；也就是說，最後決定這個最大似然估計值的參數只有答對率，跟實際上答對了哪一題是沒有關係的1。在這層觀點上，這 10000 個題目只有「全部都答對」「被 99 人答對」……「被 1 人答對」「沒人答對」這 101 類而已。隱藏參數和答對率是有關，但這基本上就是出題時的隨機過程的隨機樣本而已。
但這樣問題就又回到原點了：我們要找的分布究竟是怎麼樣的分布？回頭思考答題和「作弊」的過程，不難發現差別是這樣的：正常答題在高難度問題的答對率會顯著下降，特別是接近難度 3 的題目只有技能 3 的強者才有接近 50% 左右的答對率；但如果作弊了的話，就算是難度 3 的題目都能輕鬆獲得至少 50% 的答對率。也就是說，我們要找的是在高難度題目有著異常答對率的人。
根據上面的觀察，所謂「高難度題目」其實就很單純地是「很少人答對的題目」；但異常答對率要定量描述就有點難度了；因為每個樣本點不是機率值，而是根據機率值產生的樣本，因此「有異常答對率的人」很容易跟「本來就很強的人」混在一起。我最後送上去的答案的正確率大約只達到 70% 左右，達不到第二組 20 分需要的 86%，不過就先這樣了吧。
我這個 70% 的答案是：從最少人答對的題目開始，統計所有人對這些題目的的答對率；每次統計完某個總答對率的題目之後，對所有人進行答對率排序，取前十名，給這十個人一個正比於該人總體答錯率的分數。在處理了一定量的高難度題目之後，就說有最高分的人是可能的作弊者。會考慮整體答錯率是因為，作弊的人除非他自己本來就夠強，不然整體的答錯率會比很強的人不作弊的答錯率來得高；是利用這樣來簡單篩選可能的作弊者的。相對來說，作弊者自己夠強的話就會從這個篩選當中漏掉；雖然這樣一來他很容易在這統計中霸榜，不過我暫時沒有心力去找一個適當的判斷條件來切換偵測方式了。
總結
雖然是第三年參加 GCJ 了，但是停了這段時間沒做競賽題材果然有些東西還是滿生疏的；加上碰到我不擅長的題材所以就頗為卡卡 orz
話說回來，不知道是不是因為最近有在看一些 AI 相關的東西，這第五題看起來很有傳統 AI 的分類器題型的味道……我在猜該不會這題其實是有這方面的簡單答案？
註腳
- 詳細說是：\(\frac{d}{dx}\log\sigma(x)=\sigma(-x)=1-\sigma(x))，但(\frac{d}{dx}\log(1-\sigma(x))=-\sigma(x)\)，因此不論答對狀況，所有人對所有題都有 \(-\sigma(x)\) 的項，答對答錯的差別就是有沒有 1 而已，因此最後結果只跟答對率有關。 ↩︎