建中校內賽 & 北市賽心得

前言

北市賽終於結束了，這幾個月負責校內賽和校隊培訓害我翹了好幾堂微積分，有夠忙的，終於可以休息了。

校內賽

校內賽出題主要是顏子喬在負責，題目也幾乎都是他出的。我今年沒進二階之後就開始頹廢了，而且也沒什麼好的題目idea。
顏子喬超怪，他測資檔案用1-based編號(TIOJ 是 0-based)，然後範例測資放最後。
然後複賽的非典型是我架的，因為我很正常所以我測資檔案用0-based編號然後範例測資放最前面。
感謝8e7在IOIC出的two steps讓我有code可以抄。
在TIOJ寫special judge的時候，直接#include "testlib.h"然後用registerTestlibCmd(argc, argv);會爛掉，原因是TIOJ上argv的順序不一樣，解決方法是自己改順序或是用魔改過的testlib。
顏子喬今年有找人驗初、複賽的題，結果真的驗出測資出錯😔
抱怨一下，為了驗題所以我需要把這些題目搬到其他judge上，而codeforces雖然沒有子題聯集和沒辦法出除了互動題的非典型以外也夠用了(其實是我只知道可以放到codeforces上)，然後polygon設定子題超麻煩，要一個一個測資標記他是哪個子題的==

校內賽的結果其實讓我們有點意外，很多人不喜歡喇分，導致今年晉級線特低。

校內培訓

基本上就是拿著一年前的資讀簡報上課，然後我也順便複習。
有好幾堂培訓在禮拜二或禮拜四早上，上完之後還要趕去台大上微積分😔

模擬賽

我叫顏子喬去出2-SAT，因為之前IOIC的時候好像很多人不會2-SAT(這我QQ)，所以我覺得要讓大家都好好學一下2-SAT。
我出了兩題，一題是模擬，光是要打那題的題面就花了我很多時間，因為我發現我不太會敘述，修了很久才修到比較順，但還是有點難讀。
那題的很麻煩的分段函數不是我自己算的，我直接把每個斷點丟給chatGPT，然後他就幫我算好了。
另一個很麻煩的點是這題要寫浮點數比對，但我之後發現我可以從polygon偷上面的浮點數checker，就輕鬆解決了。
我本來預期會有人看不懂那題，所以特地提醒看不懂可以發Q&A，但結果沒有人問。

我覺得我出的另一題還不錯，推薦大家去寫。在測的時候發現免費的charGPT開thinking也做不出來我蠻爽的。

北市賽

前一天我複習了蠻多圖論的演算法，但是發現我約瑟夫問題不好，有點緊張。
因為我去年破台，所以我今年目標也是破台。但我其實很怕我被梗題梗到，然後被肘飛，而且選訓被梗題肘飛的經驗讓我蠻怕我會因為這樣被肘出全國賽晉級名額😔

題目懶得放了，因為有些我忘記了。

總之以下是我賽中的想法。

唉

開賽之前他叫我們開始之後先登入再做其他事，我本來在想要不要開賽之後先看題目，但想說還是算了。
他cms這次是設定成像JOISC那樣自己選連續的3小時打比賽，超怪。
而且他cms開放python交解，但賽後又說「我們規則就說只能用C和C++，你用python的自己檢討」，反正我是沒用python，畢竟我超熟C++。
寫完default code之後我開始看題目，從A開始看，然後發現pA和pB是看一眼就會的水題，pC, pD, pE看一眼看不懂他在講啥，pF是看一眼就知道他要幹嘛的經典題。

pC甚至沒有給範圍，所以我發現之後立刻發了question。

我寫完pA和pB之後去認真看pC，發現他是最小邊覆蓋，而我去年準備北市賽的時候恰好學過這個東西，我知道他的大小就是，是的最大匹配。當下看到的時候覺得超級白癡，為什麼會有人在北市賽出滿分要寫一般圖最大匹配的題❓但還好前面的子題是點數很少、和二分圖而且全部做完就有95分。

然後去試著解讀pE，因為pD看起來比較簡單。我一開始以為pE的答案跟他給的01序列沒有關係，亂寫了一個解交上去0分，才發現我是錯的。然後我就發現pE是這個，但我忘記kmp自動機怎麼寫了，所以先丟掉。

pF我想幫每個點算用某個顏色走到這個點的最短距離，這樣點數會變個，但直接開邊數會變，不好耶。花了一點時間觀察把轉移數量壓回就好了。

寫完pF交上去發現只過第一個subtask (轉乘時間=0)，然後發現我轉乘時間加錯地方了，超笨。

之後認真去看pD，因為我還不知道pC的是什麼意思。
發現pD是經典的圖上路徑數問題，而且還不用寫矩陣快速冪，發現這件事之後我就很開心地寫完了，因為我不想寫矩陣快速冪。

寫完pD之後我去上廁所，在廁所的時候想到pC的是一堆環和鏈，然後我就會做了。

上完廁所回去就把pC的每個子題都拿完，二分圖匹配我是寫Dinic，前幾天才寫所以寫超快。

寫完上面那些東西之後剩了一個多小時解決pE，一開始我試圖自己推kmp自動機，但推到一半發現要kmp，而我也不會kmp，後來我發現他限制很小，就乾脆暴力算kmp自動機的東西了。

這時候我開始有點緊張，然後擔心我算index會算錯，但正巧這題是01字串而且長度很小，所以可以直接map到二進位數字，所以我就用這種方法去比對字串。

因為pE很怪所以要寫大數把required substring的數量存起來(為了看他有沒有 某個2的冪次)，但還好沒有要輸出所以可以寫二進位的大數，寫很快就處理好了。

交了第一發pE之後發現我拿到0分，所以我就去寫暴力喇前兩個subtask，結果只過第二個subtask❓

暴力拿了分之後我就去確認我用dp算的答案是對的，我試了很多個01字串發現都是對的，所以還是不知道為什麼會沒過subtask 2。賽後我才發現我暴力比對共同前後綴的時候比對錯了，我忘了傳後綴的長度所以從開始對，然後這時候如果那個01字串是0開頭我就爆了，但我賽中完全沒試0開頭的字串，因為我以為問題會出在長的有點循環的字串上。

總之我最後都在debug，但完全沒找到錯哪。賽後才知道那題有一個很毒瘤的地方，他允許的等待時間要，而題目的背景和寫法讓我以為是，所以我暴力才會沒過subtask 1。

總分分，一等三，被爆打了QQ。

結果pE只有詹哲崴過，耍笨沒過好氣喔😡😡😡😡

反正順利進全國賽了，希望這一個月努力練習，全國賽可以拚到一等。

這次建中只有四個進全國賽，其中三個是高三，代表明年負責出校內賽的人只有一個人，好慘QQ

最後噴一下北市賽：題目品質有夠飄，題敘很難懂而且還有誤導，誰愛打誰打，反正今年是我最後一年了，不用管了🥳