JOISC 2025

第一次四場 JOISC 全跟，來打個簡單的心得。

結果

• Day1 59/35/100
• Day2 81/100/60
• Day3 87/19/100
• Day4 66/100/51

總分 858，Mirror Rank 8

老實說能打到 Rank 8 還蠻意外的，畢竟我已經超級久沒打 OI 了，不知道是不是比較少人每天都打的關係。跟之前打 OI 時比起來明顯能感受到我現在的實作能力已經能把我幾乎全部想的到的東西都寫下來了，之前常常想到但實作噴 bug 就顯得有點可惜。

下面就照題目講，就不講每場的過程了。

Day 1

exhibition

一開始想到一個作法以為是簡單題就先寫了個暴力驗驗看，然後寫了 WA 想一想才發現那是錯的，只有 $A_i = i$ 才會是好的。後來越想越意識到它很難就去想 subtask，後來比賽中段慢慢想到 $N \leq 400$ 跟 $A_i \leq 5$ 怎麼做，到後面一小時其他題動不了了才慢慢把它們都喇完。

fortune

大概花了半場做這題但只有可憐的 35 分。大概開始想半小時之後我就想到 $2\sqrt{n} - 1$ 的作法，可以拿到 35 分，而且只有用到 append。但後來多想了超久還是沒想到要怎麼運用可以亂 insert 這件事，所以一直在嘗試優化前面的 append 想法，但始終不會，太難了。但分享一下我的只要 append 的作法，個人覺得蠻精湛的：

紀錄目前有幾個 0 跟幾個 1，如果現在的數字是 $x$ 且含這個已經出現的 $x$ 數量是 30 的倍數，我就把 append 一個 $x$。假如說我已經 append 了 29 個數字，那我就把剩下的全部 append 進去，這樣最多長度為 59。

假設第 29 個字元是 0 且前 29 個字元有 $y$ 個 0，那我可以確定 0 的數量為 $30y$ 加上前 29 個字元以外有幾個 0，也就可以還原有幾個 1 了。

travel

從頭開始想所以最後才發現這是簡單題。想沒多久就想到倍增但一時想不到怎麼算跳 $2^0$ 步的距離就先寫了個暴力，寫完之後多想一下才想到可以啟發式合併。

Day 2

ambulance

剛看完題目覺得什麼鬼只會 $O(n4^n)$，再多想一下想到可以把對角的當成一組之後 greedy 就會 $O(n2^n)$ 了，再多想一下就想到可以枚舉 greedy 取到哪一條線，再多想一下就想到枚舉完可以花 $O(T)$ 判完了。

這題可能是今年 12 題我最喜歡的題了吧，慢慢優化的每一步我都覺得很漂亮（就算不難想到），美中不足的地方是我的複雜度是 $O(n^2T)$ 但被卡常了，看蠻多人都用這個複雜度過的。

stamps

一開始以為是怪題就沒想，後來另外兩題都沒想法就撿起來想，然後猜到關鍵性質（一定存在交換可以讓 pair -1）後就馬上本地打了個表驗驗看，驗完確定是對的就變大水題了。

thief

一開始從星狀圖開始想，很快想到一個 $2 \log n$ 次的作法，後來就直覺想到重剖，最慘會問到 $2\log^2 n$ 次但怎麼可能跑得滿。不過那時候細節還沒推的很清楚，也不確定每個子樹平行問這件事到底要怎麼實作/是不是好的所以就先丟著。等到拿完 A81 跟 B100 之後還有兩個小時就先花個半小時想完細節然後就開始實作，一開始沒覺得很麻煩但越寫越不對勁，最後寫了 340 幾行，有夠可怕，但我大概只花一小時就寫完然後也沒花多少時間 debug 就過對拍了，傳上去就理所當然拿到了，感覺是我人生實作力的巔峰（X。

話說當天寫完這題之後晚上團練我又寫了一個大概 250 行的三維幾何，然後也沒什麼 debug 就過（雖然還是吃了一個 penalty），我不知道我這天實作嗑了什麼藥，希望再多給我來一點（X。

Day 3

brave

一開始沒啥想法，想一想覺得他函數換斜率的次數應該是 $O(n^3)$ 吧，所以就寫了一個 $O(kn^2\log L)$ 的解想說喇個 $n \leq 50$，$k$ 是換斜率幾次。然後… 他就過 $n \leq 400$ 那筆了 XD。

所以這是 $k = O(n)$ 的意思嗎？那麼好。我就把判一個難度的複雜度從 $O(n^2)$ 壓成 $O(n\alpha(n))$ 想說應該可以多過 $n \leq 1600$，但沒有。後來我就在二分搜的時候多唬爛一下，先算好其中的 $\sqrt{L}$ 個難度的值之後每次二分搜就只要 $O(\log \sqrt{L})$，然後就喇過了。

非常抱歉，我根本整題在靠賽。

conference

想了大概兩個小時的 ABC 版本沒有什麼進展，最後一小時在喇分的時候才開始嘗試做只有 AB 的版本，最後大概剩 15 分鐘才想到 13 分那筆（詢問沒有 C）然後寫不完，感覺有點可惜，早點開始碰那筆應該是可以開出來的 = =。

multi

一開始看到 output only 就沒很想做，但後來半場另外兩題都燒雞的時候撿起來做一下，再讀清楚要幹嘛之後就瞬間會 $n = 4$ 了，然後寫完之後就瞬間又會 $n = 32$ 了，有點神奇。後來做 $n = 48$ 的時候因為忘記 $n = 3$ 只要 $L = 1$ 卡了一下，想起來之後才做完。

Day 4

circuit

因為是互動題而且看起來很怪所以半場之後才在碰這題。感覺鍊的 subtask 就亂二分搜一下就好了就開始寫，過了 $r \leq 70$ 之後就馬上想到分塊一下二分搜常數比較小，寫完之後稍微調一下參數就過了。

後來繼續推二元樹的 subtask，亂湊一下發現 $a \land b = \lnot(\lnot a \lor \lnot b)$ 之後就做完了，同樣再亂分塊一下就過 $r\leq 120$ 了。

想說這題大概就這樣了就先停了，後來剩半小時的時候我不知道要幹嘛就想說來亂唬爛這題。反正前面兩種分別是處理深度很深跟深度很淺這兩種極端 case，然後我就亂想了一個唬爛解：

• 亂取 $k = 14$ 條最長鍊，用鍊的 subtask 的解做完。
• 之後假裝剩下的森林深度很淺，直接用二元樹的 subtask 的解做完。

感覺很合理就開始寫，但最後沒來得及 debug 完，賽後大概五分鐘才找完，然後開一隻新的帳號傳就被我喇過了…，感覺有點殘念。

migration

開場想說「這題不是就直接做嗎」然後就開始寫，然後寫完傳完 TLE 了才發現那樣隨便都可以構出 $O(n\sqrt{n})$ 的測資，總之後來就又多想一下想到啟發式合併，但直接併是兩個 log 感覺不會過，又再多想一下才終於想起每次都被我忘記的線段樹合併，不知道之前有沒有寫過但反正就是動態開點，沒多難寫。

uiro

30 分是典而且很好寫所以開場就先寫掉，後來嘗試直接想 $A_i \leq 20$ 那筆，想要在線段樹直接維護但不知道怎麼做也沒想到什麼性質可以套。之後退而求其次就去想了 $A_i \leq 2$ 那筆，但也多想了一段時間才會，而且我用到的主要想法（沒有 2 可以選就一定會選 1）感覺完全沒有套在後面 subtask 的希望，太難過了。

賽後看計分板才知道這題原來那麼簡單嗎？雖然我到現在還是不會，菜。