2020NPSC
code與題本與記分板
這裡是比賽過程OuO
初賽
其實我有點沒印象了 燒雞
第一小時
剛開賽時我的肚子開始作痛
然後我就去廁所蹲了十幾分鐘QQ
出來後發現隊友把pB做掉了 電死
這時看計分板大家都只有pB 所以只好先把題目開完
由於我負責的部分是後半段的題目
pG題目好長所以我直接跳過 pF看了還沒什麼想法 pE一臉墨隊但我不會做
想到這裡就發現得燒雞了@@ 記分板情況是pB很多人過 pG只有wiwiho那隊過了
此時隊友丟給我pA 然後claim各種怪公式解 可是我看起來就很像數論分塊然後差分= =; 但由於還是得推式子很麻煩 所以先丟到旁邊
後來發現有人pA過了 可是我還沒推出式子 所以決定去認真看pG
看完發現是用map之類的維護他們的線段 應該算是經典手法吧XD
原本想了個比較複雜的維護方法 幸好隊友幫我矯正回來了 感謝><
之後就開始寫 然後學弟在寫pC
第二小時
實作能力燒雞@@
pG寫出一堆BUG 一直亂改亂改
到了一小時半才過
submit前發現可以用stack就好 map還會多帶一個log
但是秉持著log只是常數的精神 先丟一次看看 幸好有過
此時的記分板是pB最多 pG次多 pCpApF各有幾個過
因為還是不想推式子所以先去想F
然後學弟就說pC他寫不出來 我就接手了
發現只是維護狀態的bfs 但是有向量旋轉欸@@
原本一直在紙上畫各種例子找規律看向量會怎麼轉
結果隊友就用了翻轉矩陣得出逆時針90度是(-y, x)，所以就開始寫了
第三小時
實作能力還是在燒雞 也是一堆bug
後來終於過了範測 也一發 開心><
此時記分板也已經不少人寫出pApF了
於是就交錯一直想
pF想到離線照v排序然後維護每個點往後k個的數量
可是我不會找有沒有出現c OAO
第四小時
pF想不出來 於是只好回去看A
花了快十分鐘終於把式子弄出來了
寫出來發現是爛的QQ
結果是沒有處理到首相
然後還是爛 亂改亂改
也不確認複雜度就丟了
不過一發AC 神奇
結束前8分鐘過了 超刺激
summary
初賽寫太慢了@@
一整個不滿意 雖然有進決賽就好
後來發現pF我想的是對的 而找出有沒有出現c只需要維護最大最小直 超合理orzzz
pE的確是墨隊 但是好像得搭配treap吧
pD沒看 期望值超難
決賽
決賽在台大!!
又可以去台北玩了 開心
決賽是五個小時 很少打五個小時 也算是種學習吧!
測機
測測看vimrc要打多久 結果比我想得久超多
又因為超緊張 且鍵盤不習慣 導致一直打錯字之類的
後來覺得把整串打完太花時間 所以括號補上的map就沒打了
測機的互動二分搜題還一直wa 結果是我在戳 笑死
第一小時
開場先去打vimrc
結果發現他沒重製
所以就把括號補上那串也打完 然後打default code
看記分板已經有人開出pBpC了
隊友看完pB發現是greedy水堤
結果我沒注意n=1
WA一次後還以為是STL在雷我 改一改上傳又吃WA
de好久bug才想到N=1 雷
pB超慢 penalty又超多 我超級荒
後來去看C
發現他也是維護線段然後雙指針就好
寫完後測範測有過 就submit了
結果直接WA 心態更不穩
發現一堆bug 修完後隊友丟個測資又爛掉 為啥這範測這麼容易過啊 QQ
WA兩次後先去看F
F給了很噁心的隨機生測資的code
然後隊友在想共點的Case怎麼做
我是想到維護各個共點的時間點 但我發現記分板好多人都寫超快@@ 應該不會是這樣
後來想到共點之後的時間只會讓共點變少 到最後交點數量應該會是n(n-1)
隊友還不相信(雖然我也不太相信 畢竟用猜的)
不過我決定信信看自己 就說我先砸砸看 WA了再說(超級霸氣XDD)
第二小時
pF過了~~ 有夠梗
後來去修pC 在把一些地方改一下也過了
但是penalty還是真的太高 一直WA
記分板目前是大家都寫ABCF
去看了pA 亂claim greedy的塗法
就過了 其實我也不知道是不是假解
我甚至沒發現他是仙人掌圖@@
之後看大家燒雞 我就只好先撿看來比較可做的pDE
然後發現pG是密碼學 就丟給打ctf的學弟(超級慚愧 這題根本跟密碼學無關QQ)
第三小時
pE只想到trie然後壓常
所以就寫完後一直壓 但過不了
之後看到有人pE過了 所以我在想有其他做法
第四小時
想不到QQ
記分板大家都是做E或砸DG
所以我也去想了一下DG
才發現G跟密碼學根本無關
第五小時
燒雞
每題都沒什麼想法
五小時的比賽果然超累
看了pH 果然難 感覺就是防破台 所以也沒特別去想
pD想到邊數應該只會有根號種
pG想到應該是有環
但都跟正解還是差太多了
之後就這樣結束ㄌ@@
summary
pE是hash 但我沒想過可以這樣用 學到了新東西
pDpG都是噁噁的東西 其實我也沒很懂
pH果然是防破台(雖然DG就已經滅台了) 超噁的資結題 賽中根本寫不完吧
summary
今年NPSC能進決賽已經很開心了
去年甚至初賽就燒雞
做題速度的確不夠快
邊界case真的要多注意點
其實從npsc開始我才覺得高中的競賽之路有在走了(區賽是剛起步 npsc是正在走(? )
希望之後也能好好走下去><