資訊之芽 2023 算法班第一階段認證火烤 出題心得
這題其實原本是出給 4/21 的交大競程一期中考的，但當時由於題目太難就換了簡單的題目上去。
想法
因為是出給競程一，所以這題的靈感來源其實是一樣我出的去年競程一期末考的 Wifi。當時這題因為變數太多（跟 TOI 2021 初選學的）導致很不好拆包裝，好像連一個 submission 都沒有，現在放在 Codeforces 上也沒有人來寫 QAQ。
4/5 的晚上是生出 prototype 的 deadline，這題好像是在 4/4 晚上迸發出來的。一開始先想到了上面的 Q1，然後馬上發現可以變成 \(\mathcal{O}(\sqrt{s})\) 段區間，再過了一陣子也都想不出更好的解。
隨後我就想到可能可以出 Wifi 反過來的版本：之前是問給訊號問第 \(k\) 大，現在不如就給最大值問任意一組訊號吧！這就是 Q2 的原形。
當下我就試著看能解到什麼程度：首先是先發現了她有個看起來就很對的 greedy 性質，接著畫了一下又 claim 她有優超性，這時我確定這題用李超線段樹就做到 \(\mathcal{O}(n \lg^2 n)\) 或是 \(\mathcal{O}(n \lg n)\)，但我不確定 convex-hull trick 能不能處理優超性函數，所以 deque 的解被我畫了個問號。
隨後，我去翻了一些講義，發現只要有優超性的函數就能直接套這個做法上去，而市面上通常不會看到 convex-hull trick 放在非線性函數上，我就覺得這題一定要找地方出出來，讓我之後可以拿來當例題用。
（當時還有想到幾題跟這個函數沒關係的題目，之後或許會丟到 YTP 或 IONC 吧？）
生題
這題的解沒有花很多時間來寫（至少比題解快多了），之後 HNO2 有幫我看過確認想法應該是好的，不過當我丟到競程一的時候就被說太難了 QQ。
就這樣，題目被封存起來，直到競程一期中考的前兩天，CatAgain
敲我讓我看資芽 Slack 的訊息，我才知道我要負責出一題期中考，而且其他
subject 已經被領走了，剩下一題
DS。翻了一下上課講義，發現還沒教線段樹、BIT 等樹狀結構，也沒看到可以用
std::set 或
std::map（雖然好像可以？），我意識到我好像沒剩下多少種題目可以出了。
接著我看了一遍其他四題，一題裸的 priority queue 做 greedy（water）、一題建虛點做 01-BFS（mid）、一題後來被換掉的題目（water）、還有一題看不太懂但感覺也是水題的題目（water），感覺好像我再出水題就會有一大堆人破台了？
當時我也沒打算一定要用這題（hard），我就又想了一個簡單的 DS 題（easy-mid），然後把這兩題都丟上去讓 PM 選。最後出乎我預料的選了 hard 的那題，並提出了「增加 \(C = 1\) subtask 方便觀察函數圖形」、「提供範例圖片（本來就有打算提供）」，我就把測資生一生等人來驗題。
由於不知道怎樣的測資才算強，我大概想了幾種方法：
- 純 random
- 只在少數幾個位置蓋基地台
- 所有位置的信號強度總和很小
- 把所有是基地台的位置都 \(-1\)
- 全部的值都加上一個常數
- 遞增 / 遞減排序
上述幾種都會在生完基地台之後在官解上先跑過一次去讓 \(b_i = s_i\) 再調整結果。而後續驗題又陸陸續續的多了四五種類型的測資。
擔心這題只有一個人驗會不夠，途中我又戳了幾個人來幫忙驗題，可惜恰逢期中考年（怎麼大學永遠都在段考），最後只有 PolarisChiba 跟 nella17 可以來幫忙，感謝他們各貢獻了半天來幫我驗題 >////<！也因此這題的測資變強了很多，本來甚至是暴力加上怪剪枝就能直接 AC，現在也已經卡掉了已知的所有唬爛方法。殘念的是，目前這題還沒有其他人拿到 AC。
現在剩下的就只有題解的部分了。我本來以為大概花五六個小時就能做完題解，但由於 nella17 只在最後一天有空，所以基本上從晚上八點到考試當天的上午十點就是在生測資、改測資跟寫題解中度過。
上午八點半，我在寫最後一個子題，突然就意識到：\(b_1 \ge b_2 \ge \cdots \ge b_n\) 有 \(b_i = b_{i+1}\) 的情況也要特殊處理，那麼那個子題到 AC 的難度區間是不是太小了？就把 \(n \le 3000\) 跟 \(b_1 \ge b_2 \ge \cdots \ge b_n\) 的配分都提高了一些，並把限制從非嚴格遞減改成嚴格遞減。
重新生測資並 background rejudge 之後，我發現本來給 \(C \cdot b_i \le 60\) 子題的解竟然吃 TLE 了！檢查一遍測資跟解發現沒有問題，於是就將問題歸咎於除法次數太多，只好把那個子題的 \(n\) 也下調又重新 rejudge 一次（如果 C 語法班考試時會覺得 judge 有點卡那是我的鍋 QQ）。
稍憩一下，下午兩點從床上起來繼續完成題解。因為我作死把子題性質改了導致函數圖形要全部重畫。本來還想用題目中的函數演示一下是怎麼做
convex-hull trick 的，但最後連優超性的證明都還來不及寫。
驗題
發現 pA 跟 pC 的官解爛了，pA 是戳到了 UB 但測資沒有出問題，pC
是官解用 int，但實際上應該要用 long long。
我真的不懂要怎麼好好唬爛，我唯一會的可能就是想辦法套個 random 上去 QQ。身為出題者的時候更是如此，對自己的題目根本無從下手。
也或許是越難的題目就能想到越多種唬爛的辦法？
考試
好像不能透漏太多。
不知道是誰在考試開始約 45 分鐘時戳了 Rejudge all submissions 的按鈕，結果 judge 大概就🔥火力全開🔥了快半小時？之後絕對不要再把「火」放進比賽名稱了......
本來我 claim 我的題目一定不會有人 \(> 25\) 分，然後大約會有 \(10\) 人拿到 \(25\) 分，幾個人拿到 \(10\) 分，不過 baluteshih 覺得這題可能只有競賽選手會開，其中某人可以期待一下。
他燒雞。
這題最後的結果是 [25 分] * 1 + [10 分] * 11 + [0 分] * 56，不確定是我對資芽學員 or 現役高中生實力的誤判比較嚴重，還是我對這題題目難度的低估比較致命。
考試途中有一個有趣的提問：「子題分數是取聯集還是交集？」
說實話，取交集聽起來很好玩耶，哪天辦愚人節比賽應該就要這樣搞w
結語
這是第一次為出題寫心得，本來去年 IONCamp、校內賽、花中模考、ISSC 等比賽都有打算寫心得的，但是 IONCamp 是太累，拖了幾天就沒心情了；其它則是沒什麼認識的人或參賽者，讓我也沒動力寫心得。
當某天我能為一些題池裡的未解題目生出滿意的解，我還蠻想要找一些人辦類似 LYB 邀請賽的咚咚的，也不知道在大學時期有沒有這種機會（也不知道我的大學時期還有多久 uwu）。
對這場考試的難度，我 claim 如果放到 TOI 初選線會在 380 上下。其中 D 跟 E（不考慮對於 interactive 的不熟悉程度）該有 \(> 60\) AC、A 跟 C 該有 \(\sim 30\) AC、B 可能會有人拿到 65 或 100。
比起這題 wifi2，我覺得 Wifi 更適合出成 OI
題（方便用子題來 debug），而這題的子題其實沒有太大的用處，反而丟去 ICPC
可能會更好？但我還是比較喜歡出 OI
題就是了。畢竟大部分的比賽我都沒辦法看到參賽者的螢幕畫面，只要他們沒有上傳我就不知道他們在做什麼。看到參賽者一步一步的拿到子題們的分數，遠比看著只有
0 與 1 的記分板要有趣的多。
PolarisChiba 在驗題時精神出了一個很巧妙的解法：把函數都取倒數，算完答案再取倒數回來，這樣算答案時每個函數就會變成兩條直線，也不用再通靈那個奇怪函數的性質了！
這個解聽起來超讚，如果隔幾天寫完能拿 AC 我就把他補進題解裡面吧～