競程出題心得

前言

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

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 的順序講：

滅台題

(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 作為最後一天正式賽中後期的題，最後雖然沒有變成滅台題，但也只有一隊過就是了

括號國

(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，有點可怕。

球球分教授（構造題）

(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

因為大家都不想出水題所以我就出了四題水題，但水題沒啥好講的所以就跳過了。想知道我出哪些的話可以看之前打的題解：https://hackmd.io/@abc864197532/SJuFFy5h3#/

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

懶得打