競程出題心得

前言

稍微紀錄一下大學之後出過的題，不然之後可能就忘了。

比較沒感情（？）的題可能就不會有心得。

NPSC 2022

高中組初賽 pF 取蜜柑

(https://tioj.ck.tp.edu.tw/problems/2303)

簡易題敘：兩個人在玩 nim，但每次要先擲骰子決定要選哪一堆，決定後可以自己選要拿掉那一堆的幾顆，問先手獲勝機率。

某天睡前躺在床上亂想想到的題目，當時想到解後覺得結論還蠻酷的就丟來這裡了。

但這題的結論有點太過簡單，在我眼中就是願意打個表就做完了。但我那時候我不確定打表這個技能對高中生來說多不多人知道，翻了翻以前的 NPSC 總覺得好像沒人出過這種題，所以就想說管它的還是丟丟看（X。

另外原本想要讓題目變成玩好幾輪，每輪的贏家會變下一輪的先手之類的，但感覺這樣會讓題目變醜就沒這樣做了。

最後這題有 14 隊過，以結果來看算還行吧，雖然比我預期的少一些就是了，看來那時候打表還沒在高中生中盛行（X。也可能是因為這年初賽三題中等題難度都差不多，有些隊跑去做其他題吧。

順便附上當時打的題解：https://hackmd.io/@abc864197532/BkOB-qjwi

國中組決賽 pA 數字換換換

簡易題敘：給一個 012 序列，每次操作可以選兩個相同數字把它們變成另外兩種數字各一，或是選兩個不同數字把它們都變成另外一種數字，問能不能把它們都變成 0。

原本我是把 012 變成三種顏色，然後只留下「不同數字 -> 相同數字」這種操作，然後丟在高中組決賽的簡單題，但後來好像有更適合的題目就把它移到國中組，同時大 nerf 了一下讓它變成一題簡單題。

當時我不確定在國中組放這種梗題好不好，但看其他裁判好像也沒啥意見就丟了，但我覺得從顏色變成數字 012 就已經是大提示了，所以應該不會很難才對。以結果來看也只有兩隊沒有做出來，算是有達成作為簡單題的目標吧。

國中組決賽 pF 拼拼圖

簡易題敘：懶得打，反正是六邊形蜂窩拼圖

一開始國中組初賽缺難題我就提出了這題，但一直被波路說想搬去決賽，所以後來（應該是蛋餅）生出了排序那題當作初賽 hard，而這題也就理所當然搬到決賽了。

反正就是一個標準的構造題，起初我還怕這樣不夠難想要加難一些，後來問了其他裁判才知道這樣就夠了，主要是因為看起來很噁心吧，它的實際難度應該沒很難，但前面的原因已經足夠讓它變滅台題了。

高中組決賽 pG 魔族與訓練

(https://tioj.ck.tp.edu.tw/problems/2311)

簡易題敘：有 $n$ 個事件與一個變數 $x$，第 $i$ 個事件會將變數 $x$ 變成 $\text{clamp}(x + a_i, 0, M)$，且若 $x + a_i < 0$ 會花費 $|x + a_i|$。請支援單一事件修改與區間詢問，詢問會給定 $x$ 的初始值，求依序經過區間所有事件後 $x$ 的值與花費為何。

那時候暑假亂想想到的題目，原本只有想到沒帶修改的版本的解，但後來發現它的性質好漂亮，就知道怎麼帶修改了。

當時覺得這題實在是太美了（現在還是這樣覺得就是了），所以就把它丟到 NPSC 決賽，然後還怕它不夠難所以多加了要算花費。但現在想想總覺得多算花費讓這題變醜了 QQ。

原本預期這題是一題中等題，可能會是這場比賽的決勝題，我那時候猜會有五隊過，其他裁判猜的也差不多，有的甚至猜了 10 來隊，結果嘛…，這題滅台了。這題會滅台起初還是蠻意外的，但後來從小方塊聽說 JOISC 有一題作法類似的題，然後場內只有 1AC，就大概知道我嚴重低估這題的難度了。

到目前為止我還是覺得這題是我目前出過最棒的題，歡迎大家來做 > <。

IOIC 2023

當時 IOIC 丟的題都是我之前出 CF 被 reject 的題，一共有三題。可能有人會覺得被 reject 的題目還出到其他地方聽起來很奇怪，但我覺得這些題目被 reject 只是因為太難或太經典而已，所以放到有教育性質的 IOIC 感覺也還可以。順便提一下近幾年的 IOIC 題目都已經在台大程式解題社 judge（https://oj.ntucpc.org/ ）上面公開了，也歡迎各位來寫寫看。

兩年後回頭看這些題為什麼會被 reject 覺得還是有道理的（就算我們的 coordinator 是現在惡名昭彰的 74TrAkToR）。以下按照被 reject 的順序講：

Day5 pF 滅台題

(https://oj.ntucpc.org/problems/131)

簡易題敘：定義一個由 AC 組成的字串的 cost $Ax^2 + Bx + C$，其中 $x$ 為 AC subsequence 的數量。給定一個由 AC? 組成的字串，求所有可能字串的 cost 總和，同時請支援字串的單點修改，每次修改後都要輸出一次答案。

一開始 propose 的六題中的其中一題，原本放在 Div.2 pE，當時還有為了 $q = 0$ 切一個 easy version，會生出這題只是我覺得把平方拆開維護的 trick 很酷，然後就隨手生出這題。現在只覺得我那時候有夠勇敢，主要是我那時候還不知道這是一個 well-known 的 trick 吧。

被 reject 的原因是我後來發現 1187F（也是某個跟這種平方有關的題）的官解作法可以直接套在這題上面，然後就變成一個經典的線段樹，我覺得不好所以就跟 coordinator 說我想要小改一下題目卡掉那個作法，然後跟他說完 1187F 的存在後他就覺得因為有類似題出現了所以應該要整題都被拔掉，所以就被 reject 了。那時候覺得很不能接受，一直覺得阿我都卡掉那個作法了為什麼還不讓我過，早知道就不要講之類的，記得被 reject 那天是 2021 全國賽 Day1，導致我那時候心情超差，不過是還好對全國賽表現沒太大影響。

不過兩年後的現在回去看這題真的慶幸那時候這題有被 reject，先不提這個梗其實還算 well-known 的問題，CF community 一直都不太喜歡實作量很大的題目，如果這題沒被 reject 的話那這場的 pD 跟 pE 都是偏實作的題，感覺就會不少人討厭。

後來這題到 IOIC 作為最後一天正式賽中後期的題，最後雖然沒有變成滅台題，但也只有一隊過就是了

Day3 pE 括號國

(https://oj.ntucpc.org/problems/113)

簡易題敘：給定一個由 () 組成的字串，請問它所有子字串的最長合法括號子序列長度總和為何？

因為前面那題被 reject 了，原本的 pD 又搬到 pE，所以就開始了整天被 coordinator 追殺新的 pD 的日子

這題是我 propose 的第一題，那時候是在想跟括號相關的題目時想到的，當初想著想著就想到一個很合理的假設，證了一下那個假設是好的後就讓這題變成一個梗題了（X

當初是被嫌怕撞題然後還是太難。怕撞題應該就是主因吧，畢竟這題一臉就會在哪裡出現的樣子，太難的話我到現在還是不懂就是了。撇開怕撞題的部份，我到現在還是覺得他是一題很完美的 Div.2 pD（論作法也很 CF style）。

後來這題到 IOIC 作為 Day3 團體賽的中等題，最後有 13/24 隊過，感覺也確實是 Div.2 pD 的難度吧 XD。

另外一提預期解大概只有 10 行，但那時候看到有人寫了 Treap，有點可怕。

Day1 pQ 球球分教授（構造題）

(https://oj.ntucpc.org/problems/155)

簡易題敘：定義 $f(x) = (x - a_1)(x - a_2)...(x - a_n)$，請將 $f(0), f(1), ..., f(2^{n + 1} - 1)$ 分成兩組使兩組的總和模 $m$ 相同

我 propose 的第二題，一開始 coordinator 同意了我們很開心，但不久後他發現他看錯題目，不會做現在的題目，然後一個橘還紅的 tester 不會做，就說這題太難了把他 reject，不過 coordinator 對這題的評價還蠻高的，會被 reject 純粹是太難。那時候不是很懂為什麼這題會太難，不過後來在 IOIC 只有 AC 做出來就能理解為什麼這題太難了。

印象中這題是當初高三作專題讀書讀到一個酷酷的定理，定理內容有點忘了，然後就把它的核心想法（正負相消讓 polynomial degree -1）出成一題構造題。雖然我是讀書讀到的，但我覺得這個想法只要會微分就不難想到所以才覺得他沒有很難，但畢竟這種定理相關的題丟在 CF 不太好，所以當時猶豫了很久要不要 propose 看看，但後來是真的沒題目了才試試看，被 reject 也沒有很意外，雖然對 reject 的原因（太難）還是有點意外。

決定要出在 IOIC 的趣味賽後也想了很久要怎麼把多項式的部份包裝的更好，但這真的太難了。

YTP 2023

因為大家都不想出水題所以我就出了四題水題

國中組初賽 p2 波奇與芒果假面

(https://oj.ntucpc.org/problems/300)

簡易題敘：給定 $n + 1$ 個長方體 $a_1, a_2, \ldots, a_n, b$，$b$ 的三個方向都是平行座標軸。問有幾個 $a_i$ 使 $a_i$ 經過旋轉後可以放的進 $b$，旋轉後仍需平行座標軸

高中組初賽 p1 虹夏？多力多滋？

(https://oj.ntucpc.org/problems/277)

簡易題敘：判兩三角形是否全等

簡單國中數學，順便教育一下不會好好用浮點數的人。

國中組決賽 p3 十一

(https://oj.ntucpc.org/problems/307)

簡易題敘：給定 $n$，輸出最大的數使得每個 digit 都非 0 且 digit 總和為 $n$ 且可被 11 整除

高中組決賽 p4 優奈與委託

(https://oj.ntucpc.org/problems/287)

簡易題敘：有 $2$ 個按鈕，一開始每個按鈕的狀態都是關的，每次操作可以將其中一個按鈕的狀態反轉。現在有 $n$ 個條件，每個條件會給定一個長度 2 且由 10X 組成的字串，代表相對應的按鈕的狀態要是打開，關起來或都可以。問要依序完成第 1 個條件到第 $n$ 個條件的最小所需操作次數為何。

原本想說缺簡單 dp 就亂出了這個，結果出完才發現有超簡單的 greedy = =。

NPSC 2023

國中/國小組初賽 pB 密碼測試

簡易題敘：給一個小寫字母組成字串，問最少要插入幾個底線才能讓相鄰兩個字元皆不相同。

隨便亂出的一題簡單題，但好像太簡單了一點（X

這場的兩題被定位在 easy 的題都太簡單，不小心讓進國中決賽變成手速大賽，我很抱歉。

高中組初賽 pE 買漫畫

(https://tioj.ck.tp.edu.tw/problems/2341)

簡易題敘：第一種漫畫有 $n$ 集，第二種有 $m$ 集，每一種漫畫買的集數必須要是一段前綴，每一集都在恰一間漫畫店販賣。問在最多去 $k$ 間漫畫店的前提下，最多可以買幾本漫畫。

沒錯，就是我在買漫畫時想到的題目（X

一開始想的題目是兩種漫畫只要是連續的集數就好了，因為我平常買漫畫的習慣就是這樣，然後 $n, m$ 都沒有那麼大，但弄一弄發現這樣題目好醜，到後來還發現自己假解了。後來多想了幾種版本的題目覺得這個版本最漂亮，所以就變成這樣出出來了。

原本想的解要二分搜，把這題跟其他裁判說才發現根本就可以雙指標，但覺得卡線性很糟糕所以還是有讓一個 log 過。不過賽中有人用 BIT 套二分搜兩個 log 硬砸過，什麼巫術？？

自己賽前預期過的隊大概在 25 隊附近，也就是跟以前的決賽線一樣。最後有 28 隊過，而且剛好前 25 名都有過，難得估的算準（X

國中/國小組決賽 pC 喵喵星球

簡易題敘：已知 1000 個 A 貨幣可以換 1 個 B 貨幣，1000 個 B 可以換 1 個 C，以此類推。給定兩種貨幣與分別的數量，問哪種價值比較大。

總之是我在玩手遊亂想想到的題目，剛好缺國中簡單題就放上來了

原本裁判都以為這種需要字串處理的題目會對國中生有難度，預期這題難度會是 easy 偏 mid，但我們太小看國中生了，以結果來看這題是妥妥的 easy 沒錯

國中/國小組決賽 pD 旅行

簡易題敘：給定 $n$ 個點，請構造一個最多 2000 個點的簡單多邊形經過所有點，$n \leq 1000$。

某天半夜四點躺在床上睡不著想到的題目，原本的限制是可以選 $2n$ 個點，然後可以用極角排序之類的可以壓到 $n$ 個點，但要丟國中組的話這樣太難了，所以就用 $2n$，順便調一下限制也讓 $n + 2$ 個點可以過。

而幾乎每個裁判都覺得這題會很少人過，大概都預測 $\leq 5$ 個吧，但事實是我們又被國中生打臉了。

高中組決賽 pF 守護魔摩市

(https://tioj.ck.tp.edu.tw/problems/2348)

簡易題敘：好麻煩喔，自己看

這題是我之前看著宿舍的自動門在開開關關想到的，題敘的晚上的魔法少女操作其實對應的就是有人去感應自動門讓它打開，然後魔力值對應的其實就是自動門開啟的大小。想到這樣的設定之後覺得很有趣就試著想著幾種題目，後來就覺得這種區間詢問的問題好像還不錯，而且作法還蠻漂亮的，就先扣著等機會出出來。

後來因為想不到 NPSC 高中組決賽要丟啥，就把這題丟到那裡了。原本有在猶豫要不要丟全國模擬，但那裡看起來不缺難題所以就作罷了。而剛好那時候高中組決賽缺 hard，我就把它當作 hard 出了。原本有在猶豫要不要加上帶修改，畢竟我實在是不覺得現在的版本是 hard（現在的版本我只想了十分鐘左右，而且不難寫）。但後來實在是太忙了，而且根據去年的經驗，這種看起來很奇怪的題會去想的人根本就不多，也就表示它會滅台了。因此最後就沒有帶修改了，我也不想寫（X

但畢竟作為 hard，我還是把題敘寫得嚇人一點，寫了整整兩頁（但幾乎沒有廢話），不過現在有點後悔就是了，如果我用原本自動門的設定看起來會美麗一些 QQ

最後當然果不其然的滅台了，雖然滅台主因可能是這份題目的中等題偏難，有空好好做沒有人開出來的題頂多只有兩隊吧。還是推薦大家來做做看這題，雖然看起來真的很噁心但我覺得還蠻精湛的 > <

全國模擬賽 2023

pG 吃午餐

(https://codeforces.com/gym/104830/problem/G)

簡易題敘：將第 $i$ 個人與第 $j$ 個人配對的花費是 $\max(a_i, a_j) + \max(b_i, b_j)$，求一組匹配使花費的最大值越小越好

某天跟同學去吃午餐想到的，題敘說的騎腳踏車與吃飯就真的是實際案例，主因是我騎腳踏車很慢但吃飯很快，變成同學騎到目的地還要等我，我吃完也要等他們，於是就生出了這題 XD。

因為那時候我們是三個人，所以我一開始都在想三個三個組隊可不可以做，但眾所周知一道題只要從 2 變成 3 就會變超難，到後來我就放棄了。後來改成現在的題目之後還有再掙扎一下 $n$ 奇數可不可以做（變成有一組可以三個人），但還是好難 orz，有人會的話可以教我。

原本在猶豫要丟全國模擬還是 NPSC，但當時覺得這題 style 比較適合全國賽所以就丟到全國模擬了，但丟完也被選上後才發現這題 subtask 完全不知道怎麼切，他也沒有什麼有引導性的特殊 case，不過後來想一想覺得全國賽不就都這樣嗎 XD，所以就硬是只切了一個 $O(2^n)$ 跟給驗暴力想法的 $O(n^2)$。

最後這題有 8 個人過，也是被定位為中等題的題之中最多人做的，雖然我預期會再多一點 QQ

IOIC 2024

Pre-exam pB 優惠券

(https://oj.ntucpc.org/problems/12)

簡易題敘：有 $n$ 種優惠卷，每一種有可以使用的時間範圍、有幾張以及每張的價值。請處理 $m$ 天的買東西操作，第 $i$ 天會使用價值前 $b_i$ 高的優惠卷。每次操作輸出使用的優惠卷的總價值。

想說在 pre-exam 出個簡單 stl 資結模擬還蠻不錯的，就隨手出了一個。

Pre-exam pE 最長共同回文子序列

(https://oj.ntucpc.org/problems/15)

簡易題敘：輸出兩字串的最長共同回文子序列

把兩個經典 dp 問題湊在一起，感覺有原但 pre-exam 應該沒差就想說算了。

原本想到的解是區間 dp，但把這題丟給 Fysty 後他說是不是兩個字串 reverse 之後對 4 個字串做 LCS 就好了，我就想說好像是欸，而且還比較好寫，所以就用那個作法寫了官解。

結果驗題的人用區間 dp 寫 WA 了，然後我們討論一下才發現 LCS 的作法根本就是爛的 XD，真是好險。後來發現 pre-exam 還是蠻多人踩到這個雷的，所以就出個駭客題到趣味賽了。

Day1 pE/F 隨機演算法（通靈題）

(https://oj.ntucpc.org/problems/65)
(https://oj.ntucpc.org/problems/66)

不知道怎麼講所以索性不講，我個人覺得這題出的蠻糟糕的（

Day1 pT 最長共同回文子序列（駭客題）

(https://oj.ntucpc.org/problems/80)

簡易題敘：hack 掉最長共同回文子序列的 LCS 假解

前面提過了。

Day3 pF 宇宙語

(https://oj.ntucpc.org/problems/31)

簡易題敘：給一個字串 s，問最少需要切成幾個子區間使每個子區間要嘛長度是 1，要嘛圍成環狀之後任兩個相鄰字元不相同

隨便亂想到的簡單題，然後題敘在發廚。原本想要丟在 NPSC 但感覺太難了就改成來這裡了。雖然這題簡單但意外的讓蠻多人吃毒的，那時候看到有人寫單調隊列或是線段樹之類的怪，反正我是不懂。

Day5 pB 排氣球

(https://oj.ntucpc.org/problems/44)

簡易題敘：給定一個每種數字至多出現兩次的序列，定義一個序列是好的若所有有兩次的數字的位置差為 $K$，$K$ 為序列裡面有幾種數字。你可以交換任意兩個相鄰數字，求至少要進行幾次操作才能讓序列變成好的。

某天亂想想到的問題，原本在我的出題題庫裡的版本是每種數字有好幾個，然後目標是每個數字的每個相鄰 occurrence 都要差 $K$，但 general 版本好像是 open problem，所以我出成 $K \leq 20$。

但那時候發現 OI 的資結空了很久沒人要搶，後來在題庫翻一翻發現有這題，然後想了一下發現出成可以每種數字只有兩個就變成很乾淨的資結題了，所以就打算出出來。

因為這場的資結位是 mid，我有點怕太難所以就切了很多個子任務，想說切個多一點讓下面的選手有點事情做，有點引導性也讓這題變簡單一些。最後計分板的結果我是蠻滿意的，雖然 AC 數還是比想像中少一些 QQ。

Day5 pE 爆裂魔法

(https://oj.ntucpc.org/problems/47)

簡易題敘：略

某天被家人抓去爬山（？）亂想想到的題目，一開始的題目跟現在的還有多加些設定，但我也有點忘了，反正那時候覺得他可以四邊形也有不嚴謹的證完，但不知道可以丟哪裡，後來因為今年 IOIC 多了 OI 比賽，就打算當作 OI 比賽的最難題了。

但後來在生這題的時候就發生了些問題。首先是我原本預期解是 $O(NMK\log NM)$，但我很後面才意識到有一個超簡單且常數超小的 $O(N^2)$ 解，所以就只好把 $K$ 的範圍調小。之後我在寫題解的時候又發現我之前沒證乾淨，有一個很小的 case 會沒有 monge 導致四邊形會錯，因為那時候死線已經快到了，就只好折衷把題目小調整一下讓他可以四邊形，而題目就這樣定案了。

我是覺得蠻可惜的，我覺得原本的題目還蠻漂亮的，但這樣改來改去就變得醜醜的，而且感覺一臉有原。後來又花了很多時間調時限，但因為持久化線段樹真的太胖了，只好把時限調大。但最後正式比賽還是被 becaido 直接用 $O(N^2)$ 壓常過，我明明就有寫一份常數很小的 $O(N^2)$，但我忘了開 pragma 了…

雖然說是最難題但我還是切了不少水 subtask，想說給一些願意喇分的人獎勵，但全部都喇到的也沒有很多，蠻可惜的。

Day6 pA 代打

(https://oj.ntucpc.org/problems/48)

簡易題敘：給定一個 rating 更新方式與兩個人打比賽的 performance，問在最多可以代打 $k$ 場的情況下一個人的最大 rating 為何。

沒人要出 dp 題就丟了，但好像太簡單了，原本預期難度應該要是中間難度的題，結果直接變成了個簽到。

Day6 pE 一起走的路

(https://oj.ntucpc.org/problems/52)

簡易題敘：給一棵樹與 $K$ 個人，問有幾種幫每個人安排一條路徑的方法使所有人走過的路的交集非空。

之前看錯某題 CF 題而誕生的題目，這種類型的排容感覺蠻有教育意義的就丟來 IOIC 了，但後來發現全方位木 dp 也可以做就是了

Day6 pI abc 分組問題

(https://oj.ntucpc.org/problems/56)

簡易題敘：給一個 abc 字串，支援單點修改與區間詢問「該字串最多可以切成幾的子字串使每個子字串都包含 abc 至少一個」

隨便亂生的 mid-hard 資結，原本以為會有不少人過，畢竟就只是線段樹的簡單應用而已，但最後滅台，有點難過。

台清交程式競賽 2024

pF Choosing Model Rockets

簡易題敘：有 $N$ 個物品，每個東西有權重與價值。對於所有 $i$ 從 $0$ 到 $C - 1$ 輸出選恰 $K$ 個物品且物品的所有權重 xor 值為 $i$ 的情況下最大的價值總和為多少。 $C \leq 63, N \leq 10^6$

這題的起源其實是 IOIC 2024，那時候波路在出題就丟了這個 XOR 背包，然後範圍只有 $C \leq 15$，然後我想一想就說好像有 $O(C2^C \log W)$ 之類的解，然後他改成 $C \leq 31$ 之後我又想到了 $O(NC^3)$ 的解，然後他就放棄了直接改題目了。順帶一提那題最後是乘法背包問題。

因為我覺得這題我的作法很精湛，但感覺丟高中比賽因為高機率滅台有點浪費（X，剛好那時候聽說今年的台清交是台大辦的，那就問了一下能不能讓我投題，被同意了之後就丟到那了。這段時間又想到複雜度可以壓到 $O(N\log N + C^4)$ 也就自然的把範圍調大到 $C \leq 63$ 了。

最後正式結果有兩隊過，雖然一隊是假解但我不知道怎麼卡，但一隊用的還是比預期解更好的解，也讓後面這題又在 Challenge 誕生了。

YTP 2024

國中組初賽 p5 球球遊戲

(https://oj.ntucpc.org/problems/465)

簡易題敘：有 $n$ 個球，一開始編號為 $1$ 到 $n$，模擬交換兩顆球或詢問某顆位置的球的編號。$n \leq 10^9$

國中組決賽 p3 蛋餅愛質數

(https://oj.ntucpc.org/problems/470)

簡易題敘：定義一個序列是好的若任兩數相加都是質數，求一個序列有幾個子序列是好的

一個好笑的梗題，不知道要丟哪就丟來這了

國中組決賽 p5 合成斧頭

(https://oj.ntucpc.org/problems/472)

簡易題敘：給一個 $n \times m$ 個合成台，每個格子上面都有石頭或木棍，問最多可以合成幾個石斧，物品合成後會在合成台上消失

應該是大二下那個學期的最後一個報告結束的時候，我在看別人玩 minecraft 的時候發現合成石斧的時候居然可以把石頭放在左邊，也就是下面兩種的差別：

OO   OO
OI   IO
 I   I 

然後我就亂噴出了一個簡單題，後來想一想覺得這樣的 greedy 好像也沒有到很直覺，就丟來 YTP 了。

結果最後只有兩隊過，有點意外，看到一堆人都有猜 greedy 取最上最左的是好的，但殊不知要是最左最上才是好的，有點悲傷。

國中組決賽 p11 水果優勢

(https://oj.ntucpc.org/problems/478)

簡易題敘：給一個 $n \times m$ 表格，每個表格可能有 $0$ 到 $k$ 的數字，你每次可以選一直排或橫列將所以位於此的數字都採集起來，問最少要幾次操作才能讓你 $1$ 到 $k$ 都有。$nm \leq 300$

高中組決賽 p4 羽球比賽

(https://oj.ntucpc.org/problems/445)

簡易題敘：兩個人在打羽球，但他們只記得每一局的發球方在左邊發球還是右邊發球，求先發球方的最大分數

大二下的時候修了羽球初級，在打羽球的時候亂想規則就想到了這樣的設定。原本預期解是直接 dp，但有點煩躁，後來又是在題目的時候才發現他有 greedy 解，但跟去年那題不一樣的是這個 greedy 漂亮而且不直覺許多，後來就直接把這個解當官解了。

最後結果也蠻多隊過的，滿意。

高中組決賽 p6 蛋餅愛拉麵

(https://oj.ntucpc.org/problems/447)

簡易題敘：考慮 LRU page replacement algorithm，給定一連串的 page，對所有 $k$ 從 $1$ 到 $n$ 輸出若 LRU size 為 $k$ 時會有幾個 page hit

一開始會想這相關的問題是在讀 OS 的時候讀到 Bélády's anomaly，然後就想說 FIFO 的話有沒有好的方法可以算哪些 $k$ 會下降，但想一想發現好難，後來就發現改成 LRU 的話好像還不錯，變成一個蠻經典的掃描線資結題，就決定出出來了。

最後結果好像也不少隊過，還行。

高中組決賽 p17 優奈與祕銀

(https://oj.ntucpc.org/problems/458)

簡易題敘：略

這題其實是從 2023 年初就誕生了，那時候跟這題一樣是看著宿舍的自動門亂想想到的，原本的設定是有 $k$ 個人每天都會在一天的其中 $m$ 個特殊時間點之一進出宿舍，問一個人在某個時間開始期望需要等多久才會有人幫他感應自動門，之類的。後來又加難（開始時間可以不一樣）又有再重寫一下題敘，就變成最後看到的版本。

因為那時候剛讀完 maspy 的生函大全所以知道這可以做，但生函放在高中比賽就是妥妥的滅台題，所以那時候其實猶豫了一下要不要丟 YTP，畢竟還是比較希望自己的題目賽中有人做出來，這樣比較開心，後來想說算了就還是丟到 YTP 了。

丟的時候是 YTP 2023，但因為一些原因導致這題被 YTP 留住，到了 2024 才出現，然後當然果不其然的滅台了，甚至連部份分都沒有人拿 QQ。雖然主因是決賽太多題了，大部份隊伍根本就不會去看太後面的題目。總之雖然我覺得有點可惜但也還可以接受。

NTUCPC Challenge 1

p4 飢腸鹿鹿

(https://oj.ntucpc.org/problems/4)

簡易題敘：前面的台清交題改成 $C \leq 511$

那時候台清交比完的時候已經有要辦 challenge 的打算了，所以當然就把這題丟了出來。

除了賽中的參賽者提出的 $O(C^2\log^2C)$ 的解以外，我自己也改良了前面的 $O(C^4)$ 提出了一個 $O(C^3)$ 的作法，總之兩個作法都會過，而且我都蠻喜歡的。

最後這題有 10 個人過，是除了簽到題以外最多人過的，有點欣慰。

p6 花田一鹿

(https://oj.ntucpc.org/problems/6)

簡易題敘：拼拼圖改成隨便亂挖一個空格

這題其實早在 NPSC 2022 之前就有了，因為這題其實是我國中科展的題目 XD。一開始在 NPSC 投的版本其實是 $x = 0$ 的情況，但後來因為挖中心就夠滅台且我那時候懶的寫解所以就只有挖中心了。題外話是我那時候其實很擔心會有人可能 somehow 聽過我的科展，然後可能就會不太公平，但後來想想那都是七年前的事了，現在的國中生那時候才六歲欸，而且那個科展也沒拿到多好的名次，網路上也根本查不到，後來就安心出出來了。

總之後來應該是到了 IOIC 2024 的營期前幾天我就心血來潮想說「喔如果我有一題噁爛題隨時出好感覺還不錯欸，可以防止各種突發狀況發生」，然後我就花了兩天把這題生完了。而那時候 IOIC 2024 最後一天因為一些意外差點開天窗就差點把這題用掉了，幸好後來沒有。

總之後來又過了一兩個月，因為我跟 wiwi 都有一題已經出過的題目的加難版本，某方面可能也是因為有這題才有 challenge 的出現吧 XD。在準備的時候我感覺我沒寫 visualizer 的話可能沒人會想要碰，要畫一堆六邊形可能很煩躁，所以就跟 chatGPT 合力搞了一個。

總之後來 challenge 也蠻多人 AC 的，畢竟在有兩個禮拜的情況下，只要肯花時間做應該是不難做出來。不過看一堆人寫 400、500 行的 code 感覺蠻爽的 www。

p9 鹿不敷出

(https://oj.ntucpc.org/problems/9)

簡易題敘：有 $N$ 個重量 $A$ 的東西與 $M$ 個重量 $B$ 的東西，你想要把他們分袋，每一袋的重量都恰好為 $K$，最小化沒被裝袋的物品數量。

某場團練的某題因為看錯題目而來的。其實這題就是一個正常的題目，丟到其他比賽也可以當一個很正常的題目，但因為那時候我們想要湊十題，所以我就把這題提出來了。作法其實是從隊友學來的，感謝他們。

這題測資有夠難生，隨便一個唬爛就很容易唬過，我在準備的時候嘗試了很久，但感覺最後的測資還是不夠強，但因為沒時間所以就直接上了。

然後正式賽第一天就出事，參賽者的 code 差點就要喇過了，還好 challenge 有說可以 rejudge，我就趕緊對著生了幾筆能卡掉的測資，然後中間還發現我的官解有個地方會爆 long long，好險還沒有人過就趕緊更新了測資。

到了第二天我還是覺得有點危險所以想要再加強一下測資，那時我腦中想像出了一種測資，如果能構出來的話好像會很強，但試著構了一下發現好像構不出來，我就懷疑了一下是不是真的構不出來就開始證明，後來就發現證完了，而且再推一下就發現原題其實可以做到更好！

後面就問一下能不能讓我新增子題，畢竟我覺得結論蠻漂亮的，不出出來有點可惜。所以「p9 新增更具挑戰性的子任務」這種看起來很荒謬的公告就誕生了。至少這是在第二天，影響到的人不多。

後面我有再多花點時間想辦法構測資，但真的好難就放棄了。以結論來說有拿分的 submission 看起來都很像預期的作法，但我還是覺得這題測資不夠強就是了 = =

p10 壅壅鹿鹿

(https://oj.ntucpc.org/problems/10)

簡易題敘：給 $n$ 個點，求 $2^n$ 個 subset 的凸包面積期望值。$n \leq 50000$

離十題還缺一題，我那時候就在想說有什麼題能改，弄一弄之後就把腦筋動到這題了。感覺這題很 Linear Regression 所以就稍微拜讀了一下 ideograph_advantage 的 AC code，再魔改一下就產出了可以過 $n \leq 50000$ 的 code 了欸，然後當然就順理成章出出來了。

但大問題是測資。這份 code 在有三點共線的時候會爛，然後我也不知道怎麼改，然後我也不知道怎麼好好生沒有三點共線且足夠強的測資，再加上沒多少時間了，我就直接去各種題目亂偷，像是這題跟上面提過的 Linear Regreesion 就直接上場了。

最後亂偷測資的下場就是這題 AC 的三個人有兩個是應該要 TLE 的解，一個是特判 $n \leq 2000$ 然後後面用半對的 code 喇過的（雖然那份想法是對的，只缺 debug），而且我也不知道怎麼生測資就只好放他們過了，感覺蠻可惜的就是了 QQ

ICPC 2024 Shanghai Regional Contest

沒想到還沒退役就有機會出 ICPC 比賽，還蠻酷的。

剛開始很擔心我們產不出難題會被中國人嫌棄，但以結果來說好像還好，而且看起來蠻難的（汗

這場最後也作為 3rd Universal Cup Stage 29，歡迎各位來 virtual！

以下照 propose 順序講。

pH Hexagon Puzzle

(https://qoj.ac/problem/9044)

簡易題敘：六邊形拼圖，略

為了讓中國人知道蜂窩拼圖的美好，所以就誕生了這題。後來上了 Ucup，現在全世界都知道蜂窩拼圖的美好了。

前面在瞎掰，其實是最一開始我們還沒有什麼難題，所以都把心力放在難題。因為我們是在 challenge 出的差不多的時候才收到出 ICPC 的事情，所以當時我就開始後悔把這題丟在 challenge，那題放在任何一場正常的 ICPC 比賽應該就是妥妥的滅台題，除非有 jiangly 之類的神來虐那就是另一個故事了。不過雖然說這題已經有簡單版公開過了，再出出來好像不好，但 NPSC 國中組好像也沒有 judge，感覺可能也還好…。

總之後來我就想說反正構造題 ICPC 經常都有，而且很容易水個不低的難度，於是我就開始想要生一個新的六邊形拼圖題，那既然之前是六邊形，那現在就改成三角形吧！但三角形很容易放不滿，所以就改成最多可以放幾個吧！

那時想出來之後就魔改了一下之前的 visualizer 然後拉著旁邊的小方塊一起玩，玩個半小時不到就會了。

畢竟我們之前都玩過蜂窩狀拼圖，多少也熟悉了一些基本的擺法，所以也不確定第一次遇到的人會不會花更多時間，但反正這題就先放在了整份題目難度中後的位置。後來我們的 coordinator 有找到比我一開始預期還要乾淨不少的構造方法，原本擔心會讓這題難度變低，但好像也還好。

實際出來的結果也蠻符合預期的，含打星有五隊過，而且開的非常散。ucup 也有 14 隊過，不過前 10 名只有三隊過就是了 XD。

pG Geometry Task

(https://qoj.ac/problem/9043)

簡易題敘：給定 $n$ 個方程式 $a_ix + b_i$ 跟 $n$ 個整點 $x_1, x_2, \ldots, x_n$，求將他們兩兩配對的值的中位數最大值。

一開始大家都怕沒有難題所以都在想辦法生難題，到後來發現難題太多了然後沒什麼簡單題。我看那時候題單還沒有什麼考察經典演算法的題就隨手生了一題經典的二分+貪心。

最後的結果就中規中矩，沒有什麼意料之外的事情。我故意讓這題需要處理負數整數除法的細節，好像不少人被這搞到紅溫 XD。

pL Lazy Susan

(https://qoj.ac/problem/9048)

簡易題敘：太長了，略

當時很缺簡單題，然後某天我跟出題群的一部份人因為某活動在吃合菜的時候就想到了這題的雛型。那時候只要求一個位移而已（也就是只要求現在輸出的第一個字元）。後來想一想之後發現就簡單區間 dp 而已，就投在了 easy 的位置。

後來被 coordinator 審完之後被升級到 easy-mid。後來我在生測資的時候覺得好難生，所以就把題目又改成現在的樣子（要求每一個位移），反正也就多一步是 dp 反過來做，我甚至懷疑 JOI 有出過一樣的梗但我想不起來，後來獲得同意之後就變成這樣了。

然後找人驗題之後覺得它應該比 E 難所以又把它的難度變成 mid，驗題只有杜老師有做出來，但我還是深信他不難。然後正賽…直接炸裂，含打星只有兩隊 XD。還記得那時候剛打完台中站（上海站跟台中站同一天比，這是個很不幸的巧合，第一次出題沒辦法在比賽中參與感覺有點糟= =）還在排隊拿寄放的包包之前就急急忙忙跟別人借了手機來看上海站封板前的計分板，然後看到只有兩隊過直接傻眼，還以為是自己看錯場。可能加了那一點東西（求所有位移）真的讓題目變不直觀很多吧。

後來上了 ucup 也才只有 17 隊過，我還是不太懂就是了。主要問題可能還是前面的題目偏難/實作導致最後沒時間吧，然後 M 看起來又比 L 可做多了，導致可能很多隊後面都跑去 M。不過可能它真的不簡單吧 XD。