今年 1A 題目就出成這樣……感覺有種我又要在 R2 脫隊的預感 (爆
(而且今天因為早上有些小事所以晚了約 20 分鐘進場，不過看起來多這 20 分鐘應該不會讓我得到更多分)
最後分數是 75/100，只有 Q3 的大測資沒過。分數截圖以下開始有雷。
Q1. Append Sort
馬上看到這題不能用整數去做，而要用字串去做。補的方法其實幾乎貪婪地補就可以了：我們的目標是要把數字補成補得出來的數字當中最小的那一個。因此做法就是：
- 如果後數比前數長，不用做事因為已經遞增了；
- 如果後數和前數一樣長，那就做字串比較：
- 如果後數字串比較大數字也就比較大，所以也不用做事；
- 如果後數是前數的前綴 (例如前數 123 後數 12)，那：
- 若確定前數多出來的不全是 9，則把前數 +1 當後數即可。補的個數是位數差。
- 如果全是 9 (含空，即前後數相等)，那歸到下面去。
- 其他狀況也歸到下面去。
- 剩下的狀況，補法就是一直補 0 補到數字比較大為止。
可能會補到和前數等長或比前數長 1，相應地計算補的個數即可；這個的判準直接進行字串比對即可。
然後上面的 +2 是我很悲劇地兩次 RE，原因大概是我忘了刪掉 stderr 輸出所以爆掉了 (爆
Q2. Prime Time
後兩題我都開起來看之後第一印象覺得兩題的大測資我可能都要放掉，那就先簡單寫個做法送上去再說吧。
這題數學上可以這麼看：若輸出的答案是 \(n\)，則所有牌的和得要是 \(n\) 加上 \(n\) 的質因數分解的和；而且我們可以簡單地確定一個數字是不是解：就用手上的牌嘗試把它質因數分解，檢查個數有沒有超過手牌，然後檢查這個和是不是所有手牌的和。題例的總和 35，在試到 25 時拆成兩個 5 手牌可以給出，然後 25 + 5*2 = 35 等於手牌和，因此 25 可以是解。Sample 提到的 22 也能類似地檢查：22 = 2*11 手牌可以給出，然後 22+2+11 = 35，所以 22 可以是解。
於是一個簡單做法就是：從手牌和開始往下試，試到可以是解的就輸出就行了。無解的判斷可以簡單地試到底，所有正整數都不是就輸出 0 了。這樣的寫法就能通過前兩組測資了。
要通過第三組則要改進一下無解判斷：要來估計 \(n\) 的質因數分解的和最大值。先不管 2 到 3 這一段的反常性 (這個反常的原因和歐拉常數 \(e\approx2.718\) 有關)，大致上拆越少數總和越大。這裡題目的另一個限制就跳出來了：輸入的質數最大只到 499。這個限制保證了我們至少得拆出 \(\log_{499} n\) 個數相乘，因此這個總和最大就會是這個數乘以 499 了。可以注意到我們這裡是拿答案去推，但我們有的是答案+質因數和；不過沒關係，考慮的數大了些考慮的範圍是大了些，但沒有大到短時間處理不完的。於是這樣我們就有了一個約略為 \(O(\log n)\) 的搜尋限制，對題目給的大到 5*1017 的總和仍然是足夠搜尋的。
Q3. Hacked Exam
我會覺得這題的大測資也該放掉是因為，題目給的大測資 Sample 要輸出的有理數分子竟然超過 297，也就是明擺著告訴你：要過這個請寫大數。所以我果斷放掉了。
放掉大測資的話，小測資和中測資最多只會有兩個學生，事情就會簡單一點了。
首先看一個學生的狀況。策略很簡單：如果他答對過半就抄他的答案，否則反著抄他的答案－－即是 T 改 F，F 改 T 地抄。理由很簡單，他的這 Q 題答案裡有這麼多題答對了，那每一題會是他寫的答案的機率和他的答對率成正比，這一點每一題都是一樣的。
兩個學生的狀況就稍微有趣了：我們可以把題目分成兩類，其一是兩人答同樣答案的，另一是兩人答不同答案的。假設前者有 s 題，後者有 t 題好了。後 t 題的狀況和一個學生相同，只是這下我們不用反著抄，因為反著的就是另一個學生；所以這 t 題兩人誰答得多就抄誰的－－等等，我們怎麼知道這 t 題兩人誰答得多？很簡單：兩人的分數裡面恰好有 t 分是來自這 t 題，剩下的則來自前面 s 題；但前 s 題兩個人的答案是一樣的，因此這部份兩人分數相同。所以兩人分數和減去 t 就是前 s 題中兩人的答對數，各自扣掉之後就是兩人各自後 t 題的答對數了。這樣一來，前 s 題和後 t 題都可以各自應用一個學生的狀況－－因為只有兩類所以兩邊各自機率不會互相影響－－所以期望值就是前 s 題兩人答對數或答錯數，加上後 t 題兩個人中高分的那一個。
以題目參考測資 3 為例：學生一答 FFTTTF 得 2 分，學生二答 FTFTFT 得 4 分。兩人不同答的題目有四題，所以兩人同答的題目中答對的有 (2+4-4)/2 = 1 題，因而學生一在不同答的四題中答對一題，學生二答對另三題。因此不同答的題目 2, 3, 5, 6, 抄學生二，而同答的題目 1, 4 因為不少於一半故正的抄，總共合起來答 FTFTFT，期望值 3+1=4 分。
理論上同樣的方式應該可以用在三人的狀況 (這時題目會分成四類：三人同答，以及 C(3,2) 種兩人同答)，但看起來這四類之間的交互作用就會讓答案不是整數了，探討起來會更麻煩一點；而我由於晚進場的關係，寫完 Q2 大測資就剩十分鐘了，顯然這點時間推複雜公式是不夠的，再加上還要寫大數，就算開場的 20 分鐘也加進來大概還是寫不出來吧。
總結
今天其實除了晚進場之外，參賽也不是在自己房間 (因為有其他的事出來一趟)，所以其實參賽狀況不是頂好，不過至少 Q2 的大測資找到了那個必要條件有過了所以還算過得去啦 XD 原本是有打算要不要就放掉這次，參戰下下週的 R1B 的，不過考慮了一下還是來挑戰好了。
這場的賽中分數榜其實很刺激，因為隱藏的測資是 Q2 大及 Q3 中大，但 Q3 大這個 25 分是明擺著要你花不少力氣才會得到 (終場全場只有約 70 人拿到這 25 分)，Q2 大則是要簡單的推算邊界才拿得到，所以賽中時其實是看到一大票人的分數都是暫定 100 (沒記錯好像還超過晉級線 1500 了)－－這其實是我在把 Q3 小中解決之後回頭去推 Q2 大的關係式的原因：60 分感覺有點怕怕的。事後看起來如果我沒去做 Q2 大，名次應該會在七百多名－－不過這在賽中誰都說不準就是了。