2023.12.15 PM 04:30 by CBJ
今年終於如願進到全國賽的舞台，如果還沒有看過複賽心得的話可以[看這邊]。
這次全國賽的心情就比較輕鬆一些，對我而言，能夠進到全國賽已經是對自己相當大的肯定了，加上比完賽隔天就是清大資工的面試，所以就沒有完全把重心放在全國賽上面，賽前也沒有特別做任何複習或準備，只有告訴自己，保持健康的心態參加，享受過程。
全國賽的時程總共有兩天，第一天是測機和晚宴，第二天才是正式比賽。由於我們學校 (甚至是雲林縣) 沒有參加過全國賽，所以我們學校的老師也一起陪同參加，我到現在都還是認為老師是去度假的 XD。
早上上完兩節課之後就從學校出發，搭車去新竹車站，經過一番波折之後總算找到集合點，搭著接駁車前往清大。
抵達以後就開始跟認識的人寒暄，簡單的進行開幕式之後，就進到測機的環節，測機總共有 3 題，都是相當簡單的題目。
第一題是 Hello, World，想必不用多加說明，第二題則是分數的運算，寫好送出之後，不知為何一直沒有滿分 (差一個測資沒過)，於是就先去開第三題，第三題是檢查兩個二進制數字有幾個 bit 不相同，一開始我使用 bitset 實作，結果沒有滿分，於是我改成直接使用一行解，使用 __builtin_popcount(a ^ b) 計算，結果還是一樣沒有滿分，後來重新閱讀題目才發現，要使用 unsigned long long，改完以後就過了。
接下來就一直專注在第二題，寫到剩最後十分鐘左右，工作人員才說那個是故意錯的，要傳第一題的 code 才會過那筆測資 (???)，聽完所有人都傻眼了，但還是有人滿分 orz。
測機主要只有遇到一個問題，就是不知道如何貼上測資到 exe 檔，後來我就直接使用讀檔的方式解決，出來也忘記問了 QQ。
測試完之後，我們就搭車移動到和選旅 (之前去交大經過都在幻想自己可以進去住，結果還真的如願)，晚宴的菜色蠻豐富的，但感覺大家都不敢吃太多，怕影響到明天的比賽，也有在晚宴中認識一些人，整體而言還蠻不錯的，主桌是老師和家長，我老師在和大家分享我們學校，感覺大家都聽得很開心 (畢竟我們學校是個奇葩ww)。
接著就是分房的部分，一如往常，這次也是主辦方隨機配對兩人一間雙人房，由於我要續住一天 (清大面試)，所以和另一位也要續住的選手住同一間 (比較特別的是，老師跟家長要自己訂房，算是強迫推銷嗎 XD)。
飯店有提供三溫暖跟健身房，但我認為浴缸 = 私人三溫暖，所以就只有泡浴缸，但聽說還蠻不錯的，之後的選手可以去嘗試看看 XD。由於明天要比賽，所以大約 11 點多就睡了。
隔天大約 6:00 起床，盥洗以後就去樓下餐廳吃自助早餐，後來老師找到我，於是和我一起吃早餐順便聊天，雖說心態上比較輕鬆，但還是會有些手腳冰冷 (生理正常反應)，後來就搭著接駁車去到清大比賽了。
抵達清大後，就直接進到競賽會場，由於認識旁邊的選手，所以就開始聊天 XD，直到競賽快開始時，主辦突然說要延後 10 分鐘，所以就繼續聊天。
最後一直拖到 20 分鐘後才正式開始，開始前 2 分鐘左右，工作人員就先叫我們打開題本 (???)，要對題本進行勘誤，改到一半，比賽就開始了 = =
我不疾不徐的翻開題本，慢慢先一次把題目看過一遍 (這個方法真的大推，等到開始寫 code 之後就會沒耐心去看題目，反正不管怎樣都還是要看題，不如就寫 code 之前先看)，大約 30 分鐘至 1 小時之後，我才開始寫 pG。
pG：給定一個數列 a 跟一個整數 k，要求使用最少次交換，使得前 k 大的數字都在 a 的前 k 項，定義一次交換是跟相鄰的點交換位置。
這是一題 greedy 的題目，顯然對於從左到右的順序，每個滿足是前 k 大的數，盡可能推到越前面會越好，所以就簡單的實作完便送出。
(1:09:58) pG – 0/100
拿到 0 分之後，我開始檢查我的 code，才發現我忘記把 freopen() 註解，所以註解掉之後，再次送出。
(120 秒內不得再次上傳)
所以我就乖乖地等到兩分鐘後…
(1:11:59) pG – 100/100
很好，看起來 greedy 的結論是對的，於是我就開始寫 pH。
pH：定義一個整數 x 的回文分解法為，一個由數字組成的回文，滿足其各數字相加 = x，對於每筆詢問 n，請求出 n 的回文分解的方法數，舉例：6 的回文分解法有 8 種 (6, 2+2+2, 3+3, 2+1+1+2, 1+4+1, 1+1+2+1+1, 1+2+2+1, 1+1+1+1+1+1)。
看到回文，很直覺的就會想從兩端做，假如限制兩端的數字，剩下的部分就會是更小的回文分解法，因此我們可以使用 dp 的方式，定義 dp[i] 代表 i 的回文分解方法數，所以可以枚舉兩端的值 j from 1 to i/2，dp[i] += dp[i – (2*j)]，寫完之後通過測資，所以就直接上傳。
(1:28:18) pH – 40/100
由於 n <= 10^15，所以只能通過 40%，於是我開始觀察，發現 n 的回文分解方法數其實就是 2^(n/2)，所以就直接套快速冪。
(1:35:35) pH – 100/100
寫完 pH 之後，我回到 pF，打算先寫其中的 21 分 (Subtask 2)。
pH (Subtask 2)：給定一個三維空間，在不會出界的情況下，(x,y,z) 可以走到 (x-1,y,z), (x+1,y,z), (x,y-1,z), (x,y+1,z), (x,y,z-1), (x,y,z+1)，接下來給定每個餐廳的座標位置，對於一組詢問 (qx,qy,qz)，請求出該點到最近的餐廳的最短距離。
顯然是一個很簡單的三維 bfs，雖然之前只有寫過二維的，但其實實作起來跟二維的完全一樣，所以寫完之後便送出。
(1:45:24) pF – 0/100
於是開始進行 debug 環節，中間經過了數次的 0 分，大約改了 15 分鐘左右之後…
(2:00:44) pF – 21/100
順利地拿到很肥的 21 分。後來有花約 15 分鐘寫看看 Subtask 1，但後來沒寫成功，加上分數很少，就先跳去寫 pB 了。
pB：給定 n 個長度為 k 的 0/1 字串，請構造出長度為 k 的字串，滿足不管任取哪 t 個位置，都只少有一個 0/1 字串在該 t 個位置都相同。
pB 感覺就只是一個閱讀理解題，只要使用 permutation 套 permutation 就可以了，起初因為沒有估算好複雜度，一度認為只能拿到 8 分，但就抱持著試一試的心態上傳…
(3:01:58) pB – 100/100
當時看到的時候非常驚訝，結果後來才發現第一層 permutation 的複雜度估錯，不是 O(n!) 是 O(k!)，而 n <= 100, k <= 10，自己都覺得好笑。寫完 pB 之後，比賽也過半，分數目前是 321 分，感覺非常有機會拿到好名次。
接著就進到撈分環節，於是我看向 pC，想要撈一些分數。
pC：給一個有向圖，對於每個點，可以決定是否要使用 1 枚代幣，使用後可以決定想要走向的子節點，否則會隨機選擇，請問最少要使用多少枚代幣，才能保證從 s 絕對可以走到 t。
Subtask 1 是一棵樹，所以可以保證路徑唯一，因此就簡單實作 dfs 即可。
(3:32:40) pC – 0/100
很好，我又忘記把 freopen() 註解掉了。
(3:34:43) pC – 4/100
寫完之後，我就開始撈 pE。
pE (Subtask 1)：給定一個迷宮盒子跟一顆小鋼珠，請問最少要把箱子旋轉幾次才能讓小鋼珠離開迷宮。
顯然 pE 是 bfs，首先我先把題目轉換，把盒子向右轉表示讓小鋼珠往右跑，反之往左跑，旋轉一次之後，往右轉就變成是往上跑，反之往下跑，不斷循環 (讀者可以自己推理看看) ，這樣一來，就可以不用真正轉動盒子，因此我定義 bfs(x, y, k) 代表目前在 (x, y)，且已經轉了盒子 k 次的情形。為了方便我定義 find_left(x, y) 代表從 (x, y) 往左走到底會走到的位置 (回傳 pair)，其他例如 find_right(x, y) 等等就以此類推。假如 k 是偶數，表示要往左跑或往右跑，所以就會 呼叫 bfs(find_left(x, y).first, find_left(x, y).second, k + 1) 跟bfs(find_right(x, y).first, find_right(x, y).second, k + 1), 否則就是往上或往下，假如 (x, y) 是界外，表示找到答案 = k。寫完之後便直接送出。
(4:06:36) pE – 0/100
出錯以後，我就開始編小測資 (這題的好處是很容易看圖算答案)，後來才發現，我雖然把 bfs() 定義成三維，但 vis 卻沒有，因此我把 vis 加上 k 的維度之後再次上傳。
(4:25:50) pE – 37/100
至於為何 vis 要多一個維度 k，可以嘗試想看看下圖。
接著就一直關注 pC，但不知為何，明明 Subtask 2 對我而言不算太難，卻沒在賽中想到，而且竟然忘記看 pI (???)，因此就保持 362 的成績直到結束。
賽後馬上開始進行內部查榜，發現很多人分數都比我低 :o，加上覺得自己打得不錯，撈個佳作甚至三等獎都蠻有機會。
走出賽場之後就有人流出 ranking，沒想到我竟然是第 22 名，起初賽前認為自己最多 35，竟然這麼接近三等獎，因此相當的開心。
後來大家回到休息室吃午餐 (對，我們 14:00 才吃午餐)，清大有準備兩位教授的演講，因此在整理成績的時候不會空等，整理完之後就開始進行頒獎，有趣的是，在我拿到全國賽佳作獎狀的時候，區賽的仍然不見蹤影 XD。
後來我們相約吃晚餐，然後去台達館旁邊的籃球場打球，也在消夜時間吃到了新竹的貢丸跟米粉，接著就回到和選旅，準備明天清大的面試。
總結而言，我對於這次全國賽的成績相當滿意，想到一年前剛接觸競程的自己，想必沒有想過自己可以有今天的成績，同時也為雲林立下了一個 flag XDD，未來就剩下 TOI 初選要拚，希望可以再次獲得好成績！
發佈留言