慘烈的一場比賽……慘烈到原本以為我應該沒有晉級機會的，但結果開獎之後卻發現只要最後早個十五分鐘決定放棄東西就能晉級了。
多慘？這次的晉級線是 25/100 (+1:19:12)，對應通過題目是 Q1 及 Q2 小……
我自己的成績也是 25/100，不過果然做題目沒有這麼順手了，加上 Q1 的一次罰時我的時間是 +1:43:05，排在了 1142 名。
慣例成績截圖以下有雷。
Q1. Spiraling into Control
這題其實很快就有想法，但是細節處理上還是讓我花了好久時間，還吃了一次 WA。
首先很容易得到有解的充要條件：步數 K 是偶數，且至少是 N-1。偶數這件事將盤面塗成西洋棋盤就容易證出了，這裡就略過；並且從這裡也能簡單構造出解。這題的難點其實在於要怎麼把解輸出：這題要求我們的輸出只包含跳號的步，因此得要從頭分析一遍構造出來的解的實際步數才行。
我構造的解是這樣子的：首先，如果步數多到走完一圈還能有解，那就把那圈剝掉，對裡面輸出解即可。例如 5 18，在走完 16 步到 17 後還剩兩步，而 3 2 是有解的，因此這個解就等於 3 2 但所有數字都加 16。剩下的步驟我是這樣構造的：
- 5 4：1→2→3⇨18⇨25
- 5 6：1→2→3→4⇨19→20⇨25
- 5 8：1→2→3→4→5→6→7⇨20⇨25
- 5 10：1→2→3→4→5→6→7→8⇨21→22⇨25
- 5 12：1→2→3→4→5→6→7→8→9→10→11⇨22⇨25
- 5 14：1→2→3→4→5→6→7→8→9→10→11→12⇨23→24→25
- 5 16：1→2→3→4→5→6→7→8→9→10→11→12→13→14→15⇨24→25
標 ⇨ 的是跳號步。這些步可由它們第一步在哪一條邊轉彎分類，因為在哪邊轉彎影響到轉彎後的數字差：5 4 的彎差 15，5 8 的彎只差 13，5 12 的彎只差 11，5 16 的彎就只差 9 了。當然，轉彎後還要判斷這次轉彎是不是正好接上內層順轉的路了，這樣後面就只剩直往中心的直路；以及判斷跳號步的個數 (它不是在走完一圈就減一了；像上面 5 12 還有兩步，5 14 就剩一步了。直接理由是最內層往中心的路在這裡變成順轉沒有跳號了的關係。)
而我的 WA……則是在像 5 16 這種最後一組的邊上進場的路線計算出問題。5 16 還沒事，出事的是像 7 26 這種輸入：因為最後一組進場邊的內層順轉接的判斷條件不同，要分開寫才行。
Q2. Pixelated Circle
……果然分析不夠，原本以為只數一個八分之一扇形裡的點就夠了的。
不過我倒是推導出了一個座標是不是會是空點的條件了：若兩座標的絕對值是 \(x, y\) 且令 \(x<y\)，則當且僅當範圍 \([x^2+(y-0.5)^2,x^2+(y+0.5)^2]\) 中沒有平方數時，(x, y) 不會被錯的實作給塗到色。我寫上去的程式就是基本實作這個檢查，再加上觀察到只要 \(\left\lceil x^2+(y-0.5)^2\right\rceil=x^2+y^2-y+1\) 此值等於 \(y^2\) 的話，對更大的 y 就都會塗到色了的判斷，把這個檢查切在 \(y=\min(x^2+1,\sqrt{r^2-x^2})\)。不過看來果然還是不夠……
Q3. Saving the Jelly & Q4. I, O Bot
這兩題最後都沒做，但 Q3 有一次嘗試。這就是最開始時所說的決策：我直到終場前 15 分鐘才決定放掉 Q3 大，寫個 Q3 小能過的解，結果初版完成時正好用完這 15 分鐘，想當然爾沒有通過－－然後賽後又花了個 15 分鐘修成到 Q3 小能過的答案了。馬後炮來看，只要早 15 分鐘決定寫這版，我能拿到這 10 分就能晉級了。Oh Well。
會卡題這麼久其實是我同時在評估要解 Q3 Q4 哪一題 (Q2 送上去之後還有一小時左右)，不過 Q3 完全沒有想法，倒是 Q4 有了一個模糊的概念好像需要進行一些配對，所以可能是個 network flow 題。在仔細研究 Q4 的配對細節時才發現不對，這細節有點多，好像不容易轉成 flow，加上我也幾百年 (!) 沒寫 flow 了所以還是回頭來想 Q3 到底該怎麼走。只是這個配對題的條件很不一般，而且 N 上限也只有 1000，看起來一副就是上看三次方的演算法 orz 因此才有最後這個決定只寫 N 到 10 的解，結果看起來是時間太急沒細想，我直接拿了 next_permutation 去硬試 10! 種組合，沒注意到用最簡單的 DFS 填數獨搜尋法就行了。
小結
說起來我這幾年打 GCJ 其實一半是裸參賽，畢竟回不去大學時期那種可以天天研究競賽的生活，只有平時的 Project Euler 還有一點解題刺激而已；不過看來也真的是老了，連續兩年決策失誤在 R2 落馬。
下次是下週的 GKS Round C，不過週日晚七這個時間有一點點囧就是。