前言
Written by pooh at 2024/12/07~2024/12/14
開始寫這篇是全國賽當晚,因為還是不會
希望寫完這篇之前我已經想到怎麼弄專題的東東了。
這段時間基本上最重要的兩場比賽是全國模擬賽跟全國賽,然後中間還有 vir 了 2023 的全國賽,這三場我會特別紀錄一下,剩下的我就想到啥寫啥。
北市賽後
北市賽後我們就繼續請公假囉(開心!),因為剛好全國賽是段考後一周,所以不用考二段(謝謝主任),我們可以心無旁鶩的備賽,a.k.a. 去台大玩。中間大概去台大玩了兩次,看 Darren 表演當 8。剩下的時間我們三個都在費曼混,我通常是禮拜一四做專題,禮拜二備資讀的課,剩下的時間寫題,講白了準備的時間並不多,但還是有在寫題啦。
中間某次去台大玩的時候遇到 AC,他說全國賽最好的準備就是不要特別準備,我不知道該不該信啦,反正我是信了。
講白了這段時間我並不是特別有信心,畢竟我北市賽打的超級爛,真的沒什麼信心我全國賽會比較好,而且覺得如果全國賽又繼續吐的話我就會吃土,畢竟感覺我比賽會給我自己很大的壓力,我個人其實覺得跟蔡孟宗老師做專題我比較放鬆跟開心,因為不限時間的想一個問題的感覺真的比較好,但反正我還是會想要去選訓,然後真的很不想考 TOI 初選,所以還是全國賽拚一下吧。
最後一次去台大玩是全國模擬賽前的禮拜五,我們在那邊順便幫忙測機,然後發現 special judge 是爛的,順便精神了一下重訪黑白機,然後就到了全國模擬賽的日子了。
五小時制的暫定策略
vir OI 的時候我現在是一開始第一個小時先拿簡單的且大塊的分數,中間想三個小時做突破,最後一小時就喇小分數,全國賽我打算一樣的打法,所以其實沒什麼特別的策略。
12.01 - 全國模擬賽
全國模擬賽前的測機我連 judge 多快都沒有測,講白了是一個很不稱職的測機,但因為我覺得那一天有點累所以就懶了,全國賽有好好測啦,我這個時候在試要怎麼調讓我比賽時候好像不會想吐,結果心因性的好像根本 vir 不出來,倒。
題目我不想打,你們自己上 cf 去看。
0hr : 開打
一開始在讀題目的時候看到 A 覺得是簽到題,所以就先去寫了,然後就吃 8 次 WA,一邊吃 WA 等 CD 的時候就發現看起來剩下最水的是 pH 跟 pC,pH 是很簡單的 dp,跟, pC 則是樹 dp 一下,pB 看起來就很像蕾米廚場的題,身為一個沒在打 cf 的人,我很抱歉,pF 則看起來像是一個有趣的圖論題,dfs tree 只會虧根,感覺就不難。
所以我就先跳去寫了 pH,在大概 1:11 的時候 AC,然後我就發現我 begin 跟 end 寫成 rbegin 跟 rend,複製沒有弄乾淨 = =,早知道就 define all(x) 了。
1:14 200 分
接著我就去寫 pC ,實做了 25 min 後就一發
1:39 300 分
pF 先寫了一個 dfs tree 的版本以後就腦抽忘記隨便找都有偶環也忘記寫 12 分的 subtask 1,然後就一直砸,最後也只有 40 分,像個智障。
3:00 340 分
然後就去寫 pB,我是採取無腦前綴和開四棵線段樹的方法,寫了 55 min 才過,然後就到 4 小時了。
4:00 440 分
開始喇分模式,先喇 pE 的 21,再喇 pI 的 20,最後在喇 pG 的時候來不及寫完 QAQ。
比賽結束 : 481 rk 4 (5) (Global / + Pacybwoah)
開版以後其實挺意外的,似乎每個人都覺得自己打很爛但都一起耍笨,然後這場有 8 個人沒有打或沒有好好打,所以其實沒有多大的參考價值。
12.05 - vir 2023 全國賽
特地留到這個時候來 vir,所以一題都沒戳,講白了真的很想知道我如果打去年的能打多好,所以那天就跟 zzw 一起去 vir 了,同時感恩 Pacybwoah 幫我們模擬前三個小時不能傳 pA。
0hr : 開打
一開始就先把題目看完,第一感覺 pG, pH 是簽到題,pG 亂貪心一下,pH 就等比級數推一下,下一個比較簡單的應該是 pB,雖然實作細節還不清楚但應該會。拿完這三題以後打算拿 pE, pF, pI 去打三小時,pI 我覺得是轉移點單調,pF 整體二分搜,pE 是 777771449 維 BFS,感覺寫起來都挺煩的。pC 感覺亂亂 SPFA 一下會有一些分數,但不會做,反正就按照策略去先寫 BGH 吧。
1:18 300 分
前三題都 AC 了,pB 實作時稍微想了一下,但其實不難,講白了是一個很在我的策略裡的步調,但因為覺得 pE, pF, pI 的實作都還沒想清楚有點煩所以打算先寫 pC SPFA 的分數去看看喇幾分,順便把 pI 的實作想清楚。
不寫不知道,一寫不得了,59 分阿,怎麼過的我都不知道,秉持著一個他根本是乘一個矩陣,所以相信一定會收斂的信念決定用時間剪枝讓他收斂,結果就過了,真的是賺到。
1:51 400 分
這時 pI 的實作也想好了,其實就只需要用個線段樹做掃描線,寫了一下又處理了一下 index (真的有點煩) 後就先交只有 a > b 的 subtask 驗一下 code,然後再改一下就 AC 了
3:15 500 分
然後還莫名得搶到了 topcoder,真的詭譎。
接著我去寫 pF,然後耍大笨沒有 AC,想說來寫個小的 subtask 對拍結果聯集過了 = =。
只能說運氣太好,後來有找到是 dsu rollback 沒有把 checkpoint pop 掉,到底怎麼過的阿。
4:30 600 分
然後 owoovo 就來費曼干擾我們了,我 pE 實作又爛掉喇不到分,所以就整個大小丑。
比賽結束 : 600 rk 3 (Global)
順便檢討一下我 pF 吃大毒,但反正過了。
pC 我的作法只要跑
只能說這場完全靠賽,也沒有什麼穩定心情的作用,而且實作還很臭。
12.06 全國賽前一天
首先我在家裡打包東西跟享受人生,然後我就去費曼找 zzw 跟 cot 耍廢,畢竟要比賽了不想動太多腦,然後孟學就來帶我們去政大,還請我們喝飲料,謝謝孟學。
我們接著就去政大參加開幕,也是我第一次會實體見到高雄人們 (對不起我今年 3 月在亂用 codeblocks QAQ),在到開幕地點之前我在路上跟 cot 討論測機要測啥,我想了一下大概是 set, map, 線段樹, bitset, 階乘跟加法吧,結過最後實戰的時候我只有測 map www。
到了那邊以後我們先去報到跟領號碼,我的號碼剛好是 No. 1,我就一直說這是我要大一位了的預兆,下面放一張我的帽子、耳機還有號碼的合照。
因為會場不能喝東西,所以我們把手搖飲放在外面,然後就進去聽開幕,負責講規則的教授好像不太熟悉規則,所以他還講出了自動交集這一類的話,我個人的想法是自動交集並不是一個新概念,像是 APCS 就是自動交集的。
測機三題分別如下,我不想加暴雷。
pA
給你
pB
Interactive, 告訴你有一個 Hidden Permutation,叫你在
pC
Output Only, 數獨,跟全國模擬賽的一樣,給你一個
首先第一件事我先去把螢幕亮度調低,不然我用到差點瞎掉。
pA 是隨機,題敘裡就有教你做,所以我就把他時間剪枝做一下就過了。
然後我就跑去測了 map,結果 key 用 pair 的 1e6 次超過了一秒,有點燒雞。
然後我就用個 stable sort 把 pB 拿了 95 分以後就開始玩數獨,但也沒做多少測機時間就結束了。
先來表揚一下 owoovo 在測機的時候玩大的踩地雷差一點就過了,結果猜錯,但理論上一個好的踩地雷地圖應該要是不用猜的,所以表揚 owoovo 手刀 co-NP complete 問題。
接著表揚一下 cot 在模擬賽測機的時候做出 sudoku,數獨是個 NP complete 問題,所以表揚 cot 手刀 NP complete 問題。
最後表揚我自己有記得要測電腦的速度,因為我們這一群好像沒有其他人去測,所以表揚我自己手刀測機問題。
測機的題目竟然是比賽題目的提示欸,有點洩題的感覺,雖然我是比完賽以後政大的老師講才意識到的。
然後測機就結束了,還記得孟學幫我們買的飲料嗎,至少我是忘了啦,所以他就被丟在會場外面到隔天。
我們這個時候就分批上車,然後 guagua 就把東西忘在會場導致我們這一車比較晚出發,那個時候我們還在臭他,結果沒想到我跟 pacybwoah 才是真的把東西忘在會場門口還完全沒有意識到的人。
到飯店以後我跟 zzw 住一間,然後王以安跟 cot 也來我們這間玩,我們一進去最先注意到的就是浴室有一面是玻璃,超級色。
然後我們吃完飯就去健身房玩,這個時候 owoovo 也加入了,表揚 owoovo 是健身巨砲。
然後我們就去便利商店買比賽要吃的東西,我是買 hershey。回到飯店後我為隔天泡了紅茶,跟邊玩 scrabble 邊看 cot 實作 maze 後就去洗澡,順帶一提浴室沒有乾濕分離,所以我只好泡澡,最後再玩了一下 scrabble 就睡了。
12.07 全國賽當天
一早起床我就開始反胃,就算吃了胃藥還是沒用,只能說心病真的是不好治,當下只希望我不要像北市賽一樣時間都花在吐上面。早餐我吃的不多,因為我有預感我吃多少就吐多少,到了考場以後我感受到更想吐,最後在他講完規則,正式開考前 3 分鐘我又跑去吐了,跟小丑一樣。
然後比賽就開始了,題目在這邊 :
子題我都忘得差不多了,如果改天題目出來了我再放連結
pA
給你兩個長度為
pB
給你一個長度為
例如一開始的 AABBACBC
,答案就是 3,換成 AAABBBCC
。
pC
對於
保證輸入沒有前導零。
pD
Output Only
你手上有兩種積木,分別長得像 XO
XX
跟XXXX
你有一個
有印象的有這些
4分
4分
6分
10分 每一區域都是恰好一個塗黑的格子
pE
有一個給定的長度為
決定一個長度為
將所有的
問你是否可以在有限次操作內將
pF
Interactive
有一個長度為
pG
給你一個長度為
pH
給一顆樹,問所有 degree = 1 的點倆倆之間的距離的平方的和對
pI
給一張不帶權的無向圖,要求回答
下面就是我比賽的狀況囉,暴雷
0hr : 比賽開始
比賽一開始我就先開始看題目,看完 pA 以後就覺得他是簽到題,sort 一下就好,所以我就邊調設定邊寫 default code 邊把 pA 寫完了,6 分鐘 AC,然後就去看後面的題目。
看完 pB 的第一想法是這種問題他就是逆序數對數,看了一下逆序的組合又只有 49 種,所以遇處理一下可以
pC 是個直接暴力建圖會好的東西,實作上就補個前綴零到長度一樣就好,
看到這邊我以為這次的題目是有按照難度排的,然後我就看到 pD 是 output only,稍微看一下確定他不是來嗆人的就跳過他去看 pE。
pE 我總覺得有在 Atcoder 上看過,賽後跟 Darren 在聊的時候他也這樣說,反正我那時候是不記得實作細節,只記得跟 exgcd 有關,所以應該是放到中間三小時打 OI 的時候。
pF 是大詭譎互動題,一看沒什麼感覺也就先跳過他。
pG 想了一下就發現是
pH 我之前有想要在魔鏡出過一顆樹對每個轉軸的轉動慣量,所以我知道一定可以用換根 dp 做,應該是 OI 的部分最簡單的題。
pI 看完第一眼的想法是他是個全點對最短路問題,基本上沒有辦法比
所以審完的感覺是 pA, pB, pC, pG 是水分,pE, pH, pI 是 OI,pD, pF 是防破台。
那時間分配應該是前四題 1hr,中間三題 3 hr,最後兩題用喇的 1hr。
然後我就又跑出去吐了。
吐完回來大概是 25 分,花了 10 min 就把 pB AC,然後 pC 又花了 12 min,接著 pG 花了 14 min,所以成功在 1:01 的時候拿下了 400 分,前面的配速挺穩的。
順帶一題我在做 pG 的時候第一次忘記把階乘遇處離到
1:01 400 分
接著就進入 OI 的部分,先去寫 pH,因為之前有想過,所以雖然有點複雜但寫了差不多 45 min 就寫完了,然後交上去只過點數超小的 subtask,一看就是有地方忘記取模,看了一下就找到問題,AC。
1:57 500 分
是個我喜歡的節奏,這個時候我再看了一次 pI,首先我先快速的想了一下我會什麼不是
類似詢問分治那個用通過這個點去減少重複算浪費的時間的方法,假設我現在隨機的選了
然後我就去實作,整個想 + 寫的時間只花了我 15 min,然後就 AC 了。
2:12 600 分
挺不錯的節奏,個人當下的體感是感覺最後一等線會是 700 多,二等線 600。所以還不到半場就感覺可以穩進選訓是挺不錯的。
然後我就去好好想 pE,pE 一個比較 trivial 的式子是假設最後做了
因此有解的條件應該是
然後我就先推了 exgcd 的式子,寫好 exgcd,接著就是最小化
寫到這邊的時候是 2:55 ,交上去以後 WA 了。
接著我就仔細的想了一下
對,我就這樣耍了快一小時的笨,debug 的同時去構 pD,發現的時候已經 3:47 了,交上去以後 73 分,WA。
73 分是
我跑去寫 pF,然後 4:07 的時候拿到了前面的 subtask。
4:07 708 分
寫完 pF 以後我回去構 pD 跟 debug pE,然後我就想說看起來是溢位,所以我就開了 int128,然後就過了,好欸。
接著我就跑出去吐了,也把我的一等一吐掉了QAQ。
4:32 735 分
這個時候我手上有 pD 的 6 分跟還在構 10 分,結果我一直在外面吐,吐到一半回去還交錯檔案想說怎麼沒有拿到分,然後又出去吐,吐完以後坐了一下才意識到我交錯檔案,發現的時候已經剩一分鐘了,最後是在結束前 15 秒上傳的,如果中間沒有亂吐就一等一了,因為 guagua 是 53 分傳的 QAQ。
比賽結束 : 741 rk 1
講白了一直到最後一小時我的感覺都是前五應該都 700,沒想到對大家來講 pI 是比 pE 難的,然後很多人也覺得 pB 或 pG 是難的,我個人體感是簡單到難 ACBGIHE,有點意外一等獎的剩下兩位 pI 都是用壓常過的,後來才知道 pI 是蔡孟宗出的,譴責壓常跟他亂開值域。
題外話是我搶到了 pB 跟 pI 的首殺,但嘔吐還是害我少了 10 分左右,我後來回去有把一個區域有一個塗黑的構完,大概長下面這樣。
不難構,如果我 pE 沒有耍這麼久的笨跟沒跑去吐浪費時間應該可以拿到的,但總之這也告訴了我我接下來首要要解決的應該是我的心病吧。
比賽結束後就是聽政大的招生,然後就拿到一萬五,晚上我們一團人一起去吃第 8 次和民,我跟 leolin 3:2 把帳單付掉,接著就回家開始寫這一篇跟踏上完成我的 15 天卡皮巴啦的祭品的路。
這次全國賽的結果我挺意外的,有很多我預期會打很好的人反而沒有打很好,不過這似乎也在告訴我我明年是真的有機會可以拚到國手的,希望我可以順利成為國手吧。
最後付上一個別人給我的有趣東西,讓我紀念一下。
我一直沒打什麼線上賽,我覺得我避戰的一個很大的原因是我對競賽這種東西其實有一種本能性的厭惡的感覺,尤其是我越在意的東西越有這種感覺,這是我目前最想處理掉的問題,畢竟一直吐也不是辦法啊,但打線上賽給我的感覺真的跟 vir OI 差很多,線上賽有一種非常不舒服的感覺,不像 vir OI 耍笨是純粹覺得我自己很爛,線上賽耍笨是有一種實體的不舒服感的。
不過剛好看到 dreamoon 講的這個 :
我想說的是,我是綠色。
我之後應該會繼續以戳題跟 vir OI 為主吧,畢竟我覺得我真的不適合打線上賽,但打 OI 還是好玩的,只是有點傷身。
沒意外今年最後的大事就結束了,寫到這邊的時候我還是不會做專題,而且已經半夜兩點了,我該睡了。
Upd : 為什麼我半夜寫文章贅字這麼多 = =。