nhspc-2024

12 / 6

因為13:40才要去建中集合，所以我就在家待到9點多才出門，然後在費曼耍廢三小時。
然後建中所有人只有我帶行李箱，因為我塞了一件羽絨外套在裡面，但其實也沒用到。

我們好像是比較晚到政大的，所以講堂裡面沒剩很多連續的座位，我看到尉崴旁邊有兩個空位，然後我就問詹哲崴要不要去坐尉崴旁邊。
然後就在講堂進行開幕式，聽了系統環境、競賽規則及注意事項說明，然後負責說明的教授講了一句怪話：「題目的子題採自動交集」。

然後就是測機時間，測機有三題，pA是他教你隨機，pB是互動提，pC是數獨output only。
我先寫了一下pA，然後去寫pC，因為全國模擬賽的測機題有一樣的題目，結果有一個測資我忘記怎麼寫了，沒拿到滿分。

測完機就搭車去飯店了。
分享一下，顏子喬擅長測機。

到了飯店開始發房卡，我跟王以安住一間。發完房卡之後他就發餐盒，然後餐盒的意思其實是便當，蠻好笑的。
飯店的浴室有個窗戶，可以直接從床那邊看過去，但是有窗簾可以拉下來。
然後浴室沒有乾濕分離，只有浴缸然後沒有浴簾，洗澡的時候一開始我盡力不讓水噴出去，所以蹲著洗，結果好像怎麼搞都會噴，而且蹲著很累，我就放棄了。

晚上實作了去年全國賽的pE，大概半小時寫完（雖然之前就大概想過怎麼實作了），然後一發過，好爽。
大概22:30就有點想睡了，然後把東西弄一弄大概23:30才躺到床上睡覺。

12 / 7

睡得不錯。
然後就衝去吃早餐，我的策略是早餐吃多一點，然後比賽的時候不吃東西。

然後以下是大爆雷。

痾

比賽剛開始我先看題目，看完題之後大概的想法長這樣：

• pA 水
• pB 怪，要推一下
• pC 怪
• pD 怪output only，不會
• pE 沒想法
• pF 什麼鬼
• pG 怪定向
• pH 水
• pI 感覺顏子喬就會
  看完題之後去打default code。然後開始做pA。
  pA直覺的greedy就是直接sort然後直接算每一組的距離和，但是我對這個結論有點沒自信，而且我忘記怎麼證了，然後我就想到之前顏子喬出在暑假資讀的某題就是這個結論，然後我就會了。
• 0:27:12 pA 100
  之後去寫pH，我的作法是換根dp，我還掙扎了一下有沒有換根以外的做法，然後我沒想到，所以就寫換根dp了。剛好前幾天才練了兩題，所以寫得很快而且沒有出bug。
• 0:44:56 pH 100
  然後賽後發現這是首殺，好爽。
  之後去做pB，我的想法是每個被丟到前面的字會讓後面的人的index都減一，所以可以預處理一些東西之後bitmask dp。
  結果我有一個小地方寫錯，然後我以為是我推錯東西了，所以我就先跳去pC。
  pC一開始沒什麼想法，後來發現我應該直接判兩個人能不能連邊，而不是拿一個人去找所有他可以連的人。
• 1:39:11 pC 100
  之後回去推pB，發現我一開始推的就是對的。
• 1:42:10 pB 100
  然後我就只錯那個小地方而已，改掉就過了。
  之後稍微推了一下pE的式子，然後發現好像這個不定方程有解而且不是的倍數就一定有解，但我不太會證這是對的，所以就先丟在旁邊了。
  然後我再去看了一次pG，發現他跟圖論完全沒半點關係，排組亂算一下就好了。
  我記得他範測2的答案只有7位數，但其實他很大，是模了之後只有7位數，我有點被搞到，蠻好笑的。
• 2:17:04 pG 100
  聽說很多人pG預處理階乘沒開到。
  這時候我手爆了一下pD的subtask 1，亂爆就做完了。
  回去看pE，然後我發現我會證他一定有解了，所以就開始實作。
  實作到一半發現我不會推exgcd，我不知道他怎麼從變成的，但還好我知道他會這樣變，所以我還是能寫出exgcd。
  然後我發現有東西的值會爆到，所以要開__int128_t，然後大概判了8個case之後就做完了。
• 3:17:30 pE 100
  我先傳pD的subtask 1上去看看，確認我是對的。
• 3:18:07 pD 4
  之後我去喇pI的23分。
• 3:26:11 pI 23
  然後花了一點時間手爆subtask 2，結果爆不出來，所以先跳pF。
• 3:35:54 pE CE
  被抓到不會寫interactive，然後去看了範例程式才會。
• 3:38:59 pE 16
  pD的subtask 2試了很多方法才爆出來。
• 3:58:44 pD 8
  然後我不想手爆了，所以我決定寫backtracking，結果backtracking的時候大概漏了8個case，寫很久才寫對
• 4:26:37 pD 19.66
  看到我有個子題沒拿滿才發現我理解錯題目的意思了，他是說在不同sub-grid共用同一塊積木的對數最小，老實說我覺得我看不懂是他的問題，他真的寫得不太清楚。
  之後我去喇了pI的subtask 3。
• 4:35:17 pI 23
  吃TLE，然後我以為那個方法是爛的，因為其實那1000個特殊點是一種點覆蓋，然後我找那些點的方法是每次拔degree最大的，賽後顏子喬跟我說這是一個不錯的近似，然後我回家才發現我忘記把degree=0的點拔掉所以全部都變特殊點了==，我怎麼這麼笨。
  喔然後林祺祐用這個方法唬爛過了，然後我發現我如果過pI會一位，有點不爽QQ。
  之後我花了一點時間證明pF的subtask 2，我的作法是直接把的答案中的人挑出來，如果沒有的話就補上去，。
• 4:48:09 pF 27
  然後我之後就沒有再拿到分了。

總分669.66，rank 6。
出來之後顏子喬說pI是水題，有種不要嗆人==。

我其實覺得我這場打得不差，除了pI耍小丑沒發現之後，其他題都是一發就拿到分數。
而且做不出pI可能蠻正常的，因為我平常沒有在練隨機，根本就看不出來。
總之拿到二等獎了，下一個目標是進二階。