TOI 2023 一模（+ 一階心得亂寫）
一模
pA 國王的簽名照 (autograph)
[Communication, 3s/2 GB]
有一個 $5 \times 5$ 的網格，國王會在上面走 Hamiltonian Path，每一天走一格，兩個格子相鄰若且唯若他們共用一條邊界。
你每一天可以拜訪一個點（不同天可以重複），你的目標是最大化跟國王在同一個點的天數，如果你沒遇到，那你還是能知道國王來過了沒以及什麼時候來過。
具體來說，你可以呼叫至多 $25$ 次 Check($k$)，第 $i$ 次呼叫表示你第 $i$ 天造訪 $k$ 號節點，而回傳的值是
- $0$，如果國王當天在那個節點
- $d$，如果國王在這天之前來過，表示國王在第 $d$ 天抵達這個節點
- $-1$，如果國王沒有來過
在一次測試中，評分程式最多呼叫這個函數 $10$ 次。
Judge 是 Adaptive 的。
定義你跟國王在同一地點的天數是 $K$，那你的得分是
| $K$ | $0$ | $1$ | $[2, 8]$ | $9$ | $10$ | $[11, 25]$ |
|---|---|---|---|---|---|---|
| 得分 | $0$ | $0.08$ | $0.03K+0.15$ | $0.51$ | $0.75$ | $1.0$ |
| 分數 | 額外輸入限制 |
|---|---|
| $12$ | Judge 不是 Adaptive 的 |
| $30$ | 國王從 $1$ 號節點（左上角）出發 |
| $14$ | 當天的 Check(k) 不會影響該次 Judge 的 Adaptive 策略 |
| $44$ | 無額外限制 |
pB 最佳劇照 (stills)
[Batch, 1s/2 GB]
有 $n$ 個線段，第 $i$ 個是 $[l_i,r_i]$，你要找出若干個整數點覆蓋所有的線段，如果你選擇時間 $t$，則該點的不自然度是所有包含這個點的線段的 $|(r_i - t) - (t - l_i)|$ 的總和。
你要找到一組覆蓋的方式使得該方式所有點的不自然度總和最少，並且輸出其中一組最佳方案。
- $1 \leq n \leq 10^5$
- $0 \leq l_i < r_i \leq 10^9$ 且 $l_i, r_i$ 都是偶數
定義你找到的最佳解的不自然度總和是 $S$，而方案是覆蓋 $t_1,t_2,\cdots,t_k$，那
- 如果 $S$ 是最佳解且方案是最佳方案，那得分是 $1.0$
- 如果 $S$ 是最佳解但方案不合法或總不自然度不是 $S$，那得分是 $0.6$
- 如果 $S$ 不是最佳解，那得分是 $0$。
| 分數 | 額外輸入限制 |
|---|---|
| $11$ | $n \leq 1000, r_i \leq 1000$ |
| $15$ | $n \leq 1000, r_i \leq 10^7$ |
| $17$ | $n \leq 10^5, r_i \leq 10^6, \sum_i (r_i - l_i) \leq 5 \times 10^8$ |
| $57$ | 無額外限制 |
pC 密碼提示系統 (guesspass)
[Communication, 3s/2 GB]
有一個未知的密碼字串 $R$，長度為 $n$，包含前 $m$ 個大寫英文字母且每種至少出現一次。
你可以做出兩種詢問，兩種詢問都是給定一個嚴格遞增序列 $S$，定義 $X = R_{s_1}R_{s_2}\cdots R_{s_{|S|}}$，
GetCount($S$)會回傳 $X$ 有多少種不同的字元。GetRank($S$)會回傳對於所有 $X$ 的排列來說，$X$ 是字典序第幾小的答案，但若這個答案超過 $10^{15}$，會回傳 $-1$。
兩種詢問的代價都是 $5+|S|$，總詢問代價不能超過 $200000 = 2 \times 10^5$。
在一次測試中，評分程式最多呼叫這個函數 $5$ 次。
- $1 \leq m \leq n \leq 1000$
- $1 \leq m \leq 26$
- Judge 不是 Adaptive
假設在所有呼叫中，你的程式呼叫 GetCount 跟 GetRank 的總代價最大值是 $Q$，那你的得分 $S$ 是
$S = \begin{cases}0 & \text{if } Q > 200000\\\lfloor\frac{200000-Q}{3200}\rfloor\times 0.01 & \text{if } 40000 < Q \leq 200000\\ 0.5 + \lfloor\frac{40000-Q}{200}\rfloor\times 0.01 & \text{if } 30000 < Q \leq 40000\\1 & \text{if } Q \leq 30000\end{cases}$
| 分數 | 額外輸入限制 |
|---|---|
| $3$ | $n = m$ |
| $10$ | $m = 2$ |
| $20$ | $m \leq 10$ |
| $67$ | 無額外限制 |
pD 安逸旅行路線 (jaunt)
[Batch, 3s/2 GB]
有一張 $n$ 點 $m$ 邊有向圖，邊 $u \rightarrow v$ 的難度係數為 $d(u, v)$，代表如果 $u \rightarrow v$ 是路徑上的第 $k$ 條邊（1-based），則這條邊的辛苦程度是 $d(u, v)^k\mod P$，一條路徑的辛苦程度被定義為路徑上所有邊的最大辛苦程度。
輸出 $s$ 到 $t$ 的所有路徑中，最小辛苦程度的值，若不存在請輸出 $-1$。
- $1 \leq n \leq 1000$
- $1 \leq m \leq 5000$
- $2 \leq P \leq 10^5$ 且 $P$ 是質數
- $0 \leq d(u_i, v_i) < P$
- $1 \leq s, t, u_i, v_i \leq n$
- $s \neq t$
| 分數 | 額外輸入限制 |
|---|---|
| $8$ | $n \leq 10, m \leq 100$ |
| $16$ | $n \leq 100, m \leq 500$，圖沒有環 |
| $23$ | $n \leq 100, m \leq 500$ |
| $53$ | 無額外限制 |
比賽
小插曲是這場延時 46 分鐘，一開始是先延 10 分鐘，10 分鐘後又說延到 30 分，30 分的時候大家打開題本才急急忙忙說先不要開，說等教授宣布開始才開始，結果就一直延到 46 分的時候突然說開始，
一開始看到 Communication、Batch、Communication、Batch 的時候先涼了一半，
讀完題發現 A 是什麼噁，B 感覺最好做，C 可以亂做，D 是什麼怪，
A 先試了亂 random 直接本機就發現喔不對阿，我根本就在耍笨吧，
所以就直線去開 B 了，B 不帶權是經典題目，但這題帶了一個詭譎權重所以很自然地就會想到 $dp_i$ 表示上次拍照是在 $i$ 且右界在 $i$ 以前的區間沒有人被漏掉，想一想之後發現根本就只有 $l_i - 1, l_i, \frac{l_i + r_i}{2}, r_i, r_i + 1$ 是重要的，所以就快樂離散化然後 DP 算答案順便構解，寫了一下傳上去
1:13 B 0
詭異的是吃的竟然是 TLE，所以我猜我構解爆掉了，assert 一下發現
1:17 B 0
所以我就把構解關掉，傳上去得到
1:21 B 0
而且這次是吃 WA，完全不懂的時候又亂作亂想繼續吃 WA，
1:23 B 0
我覺得我大概是漏了不知道什麼東西，回去看題本才發現 $l$ 可以是 $0$ 之後把最小值改成負的就過了。
1:25 B 100
過了之後先去搞 C，一開始我還想 sort 之類的詭譎，但後來想想我要是能分辨前 $m$ 個我就可以直接快樂二分搜，所以我就想了一個不知道會多好的解，估一下應該有 40 ~ 60 分就先寫寫，
我的方法是先找到前 $m$ 個，所以就先維護已經找到的集合然後看看有沒有在裡面，
找完之後剩下的就快樂二分搜看看是誰，
因為一開始要是太不亂就會燒雞，所以先 shuffle 讓他接近中間，
寫完測 stub 的時候處處碰壁，打開一看才發現跟題本上說的不一樣，
努力看懂之後本機測過了，然後丟上去就吃了 WA
2:30 C 0
不懂發生什麼事了，但多測一下就發現我後面二分搜判錯人了，改完測一下就傳
2:34 C 52.61
跑去做 D，發現子題 3 之前可能 $\mathcal O(P(n + m)\log P)$ 對答案二分搜可能會過，
因為我沒有很想賭超大陣列，所以我算 cost 的時候是蓋根號表，也就是紀錄對每個邊來講，base $B = \sqrt P \approx 350$ 的兩位數各自長怎樣，
傳上去吃了 WA，
3:06 D 0
我發現我把起點當成 $1$ 號點了，明明就是 $s$，我超笨，
3:06 D 24
一看發現連子題 3 都沒過，感覺有點詭譎，但還是先跳 A，
A 我突然發現可以直接猜 $1, 2, 1, 2, \cdots$，因為國王根本就只會走黑白黑白，
C 多傳兩次看看 shuffle 會不會變好，但結果怎麼是變爛啊 qwq
3:13 C 50.94
3:14 A 21
3:15 C 50.07
稍微唬爛一下發現我根本不會唬爛，所以在 A 又多吃了笨分數，
後來有個子題是從 1 開始，所以可以直接猜 $1, 2, 3, 2, 3, \cdots$，
這段時間基本上就是 A 亂唬爛 + C 亂傳，
接下來的過程如果不小心有 C 的 submission 就是我在亂傳拚 random shuffle，
順便去寫了一個我現在也不知道在幹嘛的 D，
3:16 A 0
3:23 A 0.96
3:23 C 50.74
3:30 C 50.07
3:30 D 8
3:31 A 0
3:36 C 50.07
3:39 A 21.36
3:41 C 50.07
3:41 A 21.9
3:50 C 50.94
3:51 A 21.9
3:53 A 21
後來我想到 D 根本就可以跑 Dijkstra，而且距離只有 $0$ 到 $P - 1$ 所以可以快樂用 0-1 BFS 的概念做掉，
這樣複雜度是 $\mathcal O(P(n + m))$，應該穩穩地過子題 3，所以我就先寫下去了，
傳上去
4:10 D 24
得到的是 TLE，我以為我被卡常所以先加了 pragma，
4:12 D 24
4:21 D 24
4:21 C 50.07
4:23 D 24
這三筆 submission 我忘記發生什麼事了，但我記得就是我本機亂暴力生測資亂跑都很快啊，我完全不知道發生什麼事，
我甚至丟上去跑了 Testing 也超級快就跑出來，
結果我發現是我上一個爛解有東西沒拔掉不小心讓複雜度變成 $\mathcal O(P^2)$，超笨= =
4:24 D 100
莫名其妙的過了？？？
我原本是只有預期 47，但多賺不虧啊
回頭做 C，我發現 GetRank 我只有用到兩項有點浪費，但好像我也想不到可以好好弄的解，所以我想到的是一開始找相異的時候可以不要一個一個找，先一次跳一個 $magic$，要是沒有就可以全部偷懶掉，
4:41 C 0
智障才會拿 .size() 直接做減法= =
4:43 C 61.29
後來的過程就是我一直拿一堆東西亂調 $magic$，
4:43 C 60.22
4:44 C 61.02
4:44 C 57.62
4:45 C 60.02
4:45 C 60.29
4:46 C 58.82
4:46 C 60.02
4:46 C 60.62
4:47 C 59.42
4:48 C 60.22
4:49 C 60.69
4:50 C 59.42
4:50 C 59.82
4:51 C 60.69
4:51 C 60.49
4:51 C 61.49
4:52 C 60.62
4:52 C 60.62
最後好像是 $magic = 0.18\dfrac{n}{m} + 1$ 的時候最好。
比賽快結束前再去唬爛一下 A，然後就結束了。
4:56 A 9.24
4:59 A 21.36
賽後
Result:
| A | B | C | D |
|---|---|---|---|
| 22.26 | 61.69 |
出場問芒果他把 A 做到 89，他到底是什麼神仙啊 OAO
基本上這場我的問題就是把 A 丟掉沒有認真喇分，燒雞，
還有其實開 B 的速度可以再快一點的樣子，
現在打完二模的我很後悔一模應該再認真一點 qwq
一階
因為我記憶力燒雞了所以這邊大概就是一些亂記之類的東西 ><
Day 1
第一天我們先跑去台大混順便借日麻，然後就差點報到燒雞ㄌ
去捷絲旅寄行李的時候發現 Foxyy 跟 PixelCat 還有 victor.gao 一間，結果去師大才知道今年改成用 (年級, 名字) sort。
順帶一提以後去選訓營的人可以記得先去寄行李就可以不用搬去師大再搬回來，然後洗衣粉其實捷絲旅有可以買。
Day 2
整天都是蔡孟宗的課，這次除了複習了我以前聽過的東西還加了很多很多，
今天的時候芒果做出了 Articulation Triangle，雖然我還是沒聽懂教授後面的作法但我還是因為幫忙微不足道的證明所以蹭到了平時成績，好耶，
順便推坑教授寫 Escape Route 了，
晚上的體育課恢復成我一年級進來時候的樣子了，沒有下雨好棒
Day 3
今天是講 STL + sorting 的教授，所以今天我去補 virtual 了 JOISC 2019 Day 4，做出酷題目很開心，
但我好像還是當不了日本國手，果然我還是得變強。
Day 4
今天是 8e7 跟 WiwiHo 講課，講了很多 Communication 跟 Output Only 題，上課的時候我大概把 IOI Transfer 跟 Combo 做掉了，APIO 那題直接把我揍爛，TOI 自助餐也順便嗆了我不會寫程式，但晚上的體育課完我就突然想到要怎麼拿自助餐的 90 分了，好耶
忘記是不是這天芒果被竹科實中的老師發現在打 tetr.io，整件事情超🉐，想知道的還是去問芒果比較好。
Day 5
又是蔡孟宗的酷酷課，比較可惜的是今年沒機會聽 forest 跟 matching 版的 alias table 讓我有點小傷心，
晚上我就不記得發生什麼事了
Day 6
加菲貓教授的課，雖然不太需要聽但今天是模考前一天所以我大概只補題不開題，在芒果老師的教導下把 JOISC 2019 全數補完題了，
Day 7
一模，大概就在上面講完了，
晚上在打 JOISC 2023 Day 1，但因為我想不出題目躺在地上所以感冒了，真的不要躺在地上，
早知道就聽 WiwiHo 說的躺在地板上會感冒 qwq
JOISC 我打得不怎麼樣，燒雞
Day 8
JOISC 2023 Day 2 online mirror，打得算可以，反正整天都是 vjudge 教授講自動機，所以那也沒怎樣。
Day 9
JOISC 2023 Day 3 online mirror + vjudge，
早上是 UVa 教授的 UVa mashup，先不論 UVa 的題目輸入輸出很毒瘤，
vjudge 今天似乎抓不到他的 verdict，
因為 UVa 一度爛掉，所以我 claim 之後 vjudge 也不會好我就直接不寫後面兩題跑去 JOISC 燒雞了
（根據 PixelCat 的說法，後來是好的所以我好像有點小虧）
今天的壞事可能是 JOISC 真的打超爛= =，
可能我今天狀況本來就不好而且身體狀況燒雞再加上連續打讓我直接噴飛，
下午吃飯的酷事：芒果在講他是怎麼學會數學進入 TMO 的經歷，然後我因為鼻子不舒服去抽衛生紙被芒果以為是我被他嗆哭，
在感冒期間打資訊奧林匹克真的會燒雞，很🉐的事是有個搶角錐遊戲，結果最後一場我們一直送角錐，超好笑
Day 10
第一次體會輔導課，然後我講了一大堆的怪話，詳情請見選訓怪話集。 JOISC 2023 Day 4 好像打得有點差，燒雞。
Day 11
又推了一個教授寫 Escape Route，
但我的感冒好像在讓我亂講話（或是我腦袋短路但我在找藉口），
Day 12
養病休息 + 為二模祈禱，
壞事是 PixelCat 在地板上小睡一下也感冒了，雖然他二模打贏我但還是不要在躺在地板上，真的會感冒
Day 13
二模，等之後有開 judge 再來把我的燒雞歷程公諸於世。
附件
題本跟範例互動程式：
1A.pdf
stubA.cpp
1A_sample.cpp
1B.pdf
1C.pdf
stubC.cpp
1C_sample.cpp
1D.pdf