# IOI 2021 Problem "Dungeons" 出題心得

## 緣起

二〇一八年九月五日，日本筑波國際會議場。IOI(國際資訊奧林匹亞) 2018的選手們剛結束第二天的賽事，身穿檸檬色選手衫的高中生們三三兩兩的往國際會議場的用餐室前進。
線上的分數板已經停止更新了。台灣隊的最終成績是：四銀。
我作為台灣隊的選手輔導員，不太甘心。
雖然銀牌的成績絕對不能算差，但是在「金牌數>銀牌數>銅牌數」的國際排名規則下，總會有些惋惜四位選手都與金牌擦身而過。
我沒能幫助選手們做到更多，表現得更好，所以作為輔導員不太甘心。
但是我的另一個身份，它的不甘心更是讓我難辭其咎。跟選手的本身實力毫無關係，完全是自己能力不足的問題。

——那就是IOI 2018題目投稿的「落選者」。

大約在二〇一七年十、十一月的時候，我投稿了兩道題目到正在徵求題目的IOI 2018籌備委員會。
我當時自認兩道題目都是頗有新意的好題。一道資料結構題、一道幾何性質題，不管當年籌備委員們的胃口比較偏向哪個領域，應該兩題中至少有一題會入選吧？
⋯⋯沒有。二〇一八年三月的時候，收到了全數落選的消息。
當下的我有點賭氣，網路上隨便找了下有哪裡可以丟題，發現APIO(亞太資訊奧林匹亞) 2018正在開放投稿，就把兩題原封不動的丟上去了。
之後我壓根就忘了APIO這回事，也沒有關注籌委會有沒有回信，也沒在看它們官網的更新動態。
直到比賽結束的那一天，我的社群媒體被各種選手討論題目的動態淹沒。
⋯⋯上了。不只一題，兩題都上了。
比賽總共三題，裡面有兩題是我的。
也就是說，我的出題能力被認定在「APIO以上、IOI未滿」的程度。而且是雙重認定。
簡直就像辛苦備賽許久，卻一面金牌都沒有，反而拿了兩面銀牌的選手一樣。
我很好奇，到底是敗給什麼樣的題目？IOI等級的好題，到底有多好？
幸運的是，幾個月後我得以透過輔導員的身份，參與IOI 2018兩段賽前的選題暨翻譯工作，詳細閱讀入選的題目暨題解，得到了答案。
——我輸的心服口服。

## 何謂「好題」
一道題目最主要的成分，可以大致分成兩類：一類是「性質與觀察」，另一類是「演算法與資料結構」。

從選手的視角來看，透過分析題目得出重要的性質或觀察，再將其適當的代入既成的演算法或資料結構中，概觀而言這就是解題的過程。

反過來說從出題者的角度，想構造出一道好題就得在兩類都有足夠優秀的內容。
亦即，一道好題最基礎的原料是：**至少一個「巧妙觀察」，加上至少一個「經典操作」**。前者可以鑑別一位選手的洞察力，後者可以鑑別一位選手的知識量，兩項都很重要，缺一不可。

基礎原料以外還有一些比較細項的要求，像是對於一些**非正解**（俗稱「喇賽」或「唬爛」）能有足夠的**抗性**；若想成為IOI的題目的話，所使用到的演算法與資料結構不得超出[IOI命題大綱](https://people.ksp.sk/~misof/ioi-syllabus/)的範圍，也就是**不能使用太過高等的知識**等等。

### IOI 2018 Problem "Seats" 好題分析
這邊以IOI 2018第一天第二題"[Seats](https://ioi2018.jp/wp-content/tasks/contest1/seats.pdf)"作為好題的範例。

#### 巧妙觀察
要將本題做到滿分，最重要的觀察是把「一些方格是否構成矩形」的巨觀問題微觀化，變成「全盤面是否僅有四個格子點的四周方格為三空一滿」的等價微觀問題。
在翻譯這題的時候，我一讀完題目就想起之前曾經做過的另一道題目（以下暫稱「黑格覆蓋」）：
> 你有一個$N\times M\,\, (N, M\leq 5000)$的黑白盤面，每一格非黑即白。你想用一些（跟座標軸垂直的）矩形把所有黑格蓋住（蓋到白格沒關係）。
> 但是用來覆蓋的矩形們不能彼此相交或相切（角落或邊相切都不行）。題目輸入一個黑白盤面，要求輸出一個覆蓋方式使得矩形面積和最小。
題目的來源我已經忘了。第一感是波蘭國內選訓(POI)的題目，但是也有可能是我記錯了。如果有讀者認得這題請讓我知道。

解法如下：
> 定義一個格子點滿足「填滿條件」若且唯若它周圍的四個方格為「三黑一白」或是「二黑二白且兩黑格為對角位置」。
> 先把盤面上所有格子點掃描一遍，把每個滿足「填滿條件」加進一個`queue`裡面。
> 現在開始把`queue`中的格子點依序`pop`出來，每次把該點四周的方格全塗黑，然後重新檢查周邊的八個格子點是否變成滿足「填滿條件」，
> 有的話就加進`queue`中。這樣一個類似BFS的過程，做完之後的最終盤面就是答案。

上述解法的核心觀察在於「盤面為合法矩形集合若且唯若它只有四白、三白一黑、二黑二白且黑格相鄰、或四黑的方格點」，與"Seats"的核心觀察如出一轍。
我第一次看到「黑格覆蓋」這題時，就覺得這題的所用到的性質非常巧妙有趣。
以好題的標準衡量，「黑格覆蓋」是一道巧妙觀察滿分但是經典操作不及格的題目。印象中POI有不少題目都是如此。

理論上來說，我只要有辦法拿著這個巧妙觀察，把它套上一個經典操作，就也有能力出得了IOI等級的好題。
但這就是當時"Seats"的出題者做得到而我做不到的事情。

#### 經典操作
本題滿分解法使用到線段樹一個非常經典的變形，其最著名的用法就是在解決非常著名的經典題「[矩形覆蓋面積問題](https://tioj.ck.tp.edu.tw/problems/1224)」(下稱「矩形覆蓋」)。
由於「矩形覆蓋」的題目和解法在其他許多地方都有記載，在此就不贅述了。
在翻譯"Seats"的很久以前我就知道「矩形覆蓋」了，不過從來沒有想過可以把它跟其他巧妙觀察結合起來出題。
盤面為合法矩形集合若且唯若沒有格子點滿足「填滿條件」，然後由於要額外判斷盤面是否恰有一個合法矩形，所以再額外判斷盤面是否恰有四個「三白一黑」的格子點，這樣就可以套用「矩形覆蓋」的線段樹變形了。
這就是"Seats"的聰明之處。如此一來不僅巧妙觀察，連經典操作也滿分了。

#### 抗唬爛
"Seats"沒有顯然的唬爛騙分方式。至少我看不出來。

#### 非高等知識
技術上只有用到線段樹，在IOI命題大綱裡面列在AL3b段落中。
性質的部分只有用到小學生等級的初等數學知識。

綜上所述，"Seats"是一道無可挑剃、非常標準的好題。

### APIO 2018 Problem "New Home" 不夠好(?)題分析之一
這是我投稿但落選IOI 2018的兩題之一，也是APIO 2018的第一題（[題目敘述連結](http://apio-olympiad.org/2018/statements-en.pdf)）。
我在Codeforces上有貼兩題的[題解](https://codeforces.com/blog/entry/59650)。

#### 巧妙觀察
乏善可陳。
最重要的一步是要發現本質上想維護一個斜率是$+1$跟$-1$的距離函數。這一步很關鍵，但稱不上特別有趣。
然後就很容易想到把$+1$跟$-1$拆開來做。新增或刪除一個點只會影響局部$O(1)$個線段的性質也很平凡。
剩下的就只是考參賽者究竟看過多少經典操作而已。

#### 經典操作
本題的滿分解法用到另一個線段樹的變形：「時域線段樹」，也就是把一般用來處理一維空間的線段樹放在時間軸上。
空間的部分則是先把所有物件跟詢問按照座標排序後一一插入時域線段樹內，非常標準的離線問題手法。
整體而言，我自認本題在經典操作方面的內容滿豐盛的。

#### 抗唬爛
略有缺陷。
滿分解法的時間複雜度是$O(n \log n)$，但是很容易被常數小的$O(n \log^2 n)$騙過去。
這也的確實際發生了，據我所知有參賽者使用「時域線段樹＋堆」的$O(n \log^2 n)$作法獲得滿分。
C++內建的`priority_queue`的$O(\log n)$常數很小，而且在這個使用情境下常常不會跑滿，基本上很難卡掉。

#### 非高等知識
技術上使用到線段樹(AL3b)和排序(AL3a)，概念上或許也跟分治(AL2)和合併排序(AL3a)有關。
性質上也只用到國中數學的程度。

### APIO 2018 Problem "Circle Selection" 不夠好(?)題分析之二
我投稿但落選IOI 2018的第二題，也是APIO 2018的第二題。
題目與題解同前述連結。

#### 巧妙觀察
讓刪除者只詢問周邊特定面積內的潛在被刪除者，基本上靠直覺就可以想得出來。
但是反過來從潛在被刪除者的觀點估計詢問總量，而且要發現到刪除者兩兩互斥，這兩個觀察都滿精闢的。
最後利用刪除者半徑的單調性定期重建資料結構也很有趣。
整體而言我自認不錯。

#### 經典操作
不及格。
重建用到的倍增法算是本題唯一值得一提的經典操作，但只靠倍增法撐起一題實在很貧乏。

#### 抗唬爛
本題最致命的缺陷就在這裡。
這題有一個可以完全不用觀察性質、不動腦筋，無腦只靠超出範圍的高等工具就獲得高達87分的作法：
> 把圖旋轉一個隨機角度，把每個圓用與座標軸平行的外切正方形包住，然後直接上KD樹。

由於旋轉隨機角度的關係很難卡掉。實際上很多參賽者都這樣做了，只要看看得分板上有多少87分就知道了。

#### 非高等知識
只考慮正解的話，只有用到二分搜(AL3a)跟倍增法(AL3b, 包含在「最低共同組先」項目裡)。
但是實務上高等參賽者大多都會選擇無腦刻KD樹，而它是命題大綱AL3b段落明訂禁止使用的高等資料結構：
> Some of the harder algorithmic topics are explicitly marked as excluded. It is guaranteed that there will not be a competition task that requires the contestants to know these areas.
> Furthermore, the tasks will be set with the goal that knowledge of Excluded topics should not help in obtaining simpler solutions / solutions worth more points.
> -- IOI Syllabus p.5

所以前述缺陷事實上也嚴重影響到了這個層面。

### 題目分析總結

| 題目名稱 | 巧妙觀察 | 經典操作 | 抗唬爛 | 非高等知識 |
|:-------|:---------|:---------|:-------|:-----------|
|Seats | 100/100 | 100/100 | ✔️ | ✔️ |
|New Home | 50/100 | 100/100 | ⚠️ | ✔️ |
|Circle Selection | 100/100 | 30/100 | ✖ | ✖ |

結論：兩題都輸得毫無懸念。

## "Dungeons"的原型

IOI 2018距今已經快三年了。奇怪的是，我不只連那麼久以前的上述反省內容，就連當初進行自我反省的場景都記得清清楚楚。
那是一條寬敞明亮的走廊，位於筑波國際會議場的二樓。走廊的左邊是一排成列的明亮落地窗，右邊則是挑高的白色牆壁。
走廊上一般擺放著設計簡潔的桌椅，可以讓人一邊享受從窗外灑進來的陽光一邊舒服的坐著休息，但是今天為了讓出給選手走動的空間全數被搬到了內側牆角。
完賽的選手們在背後穿梭，就我一個人站在那裡盯著牆角的桌椅發呆。
⋯⋯精確來說是「乍看在」發呆，但其實腦袋正高速運轉著。我在腦海中的知識庫裡翻箱倒櫃，尋找任何可以達到IOI等級的好題原料。
然後我想起了這題（[CF 702F](https://codeforces.com/contest/702/problem/F)）。以下是該題的簡化版題敘：
> 有一間服飾店販售著$n\,\, (n\leq 2\cdot 10^5)$種衣服。第$i$種衣服的價錢為$c[i]\,\, (1\leq c[i] \leq 10^9)$。
> 現在有$k\,\, (k \leq 2\cdot 10^5)$位客人進入服飾店，其中第$i$位客人有$b[i]\,\, (1\leq b[i] \leq 10^9)$元的預算，並且每一位客人都會使用下列策略購買衣服：
> ```
> for(int j=1; j<=n; j++) { // 從1到n依序枚舉第j種衣服
> if(b[i] >= c[j]) { // 如果預算足夠
> b[i] -= c[j]; // 買一件第j種衣服
> }
> }
> ```
>
> 每一種衣服的庫存都是無限大，所以不用考慮客人把某種衣服買光的情形。
> 對於每一位客人，求出他（她）所購買的衣服件數。

本題的標準解法如下：
> 定義`ans(j, x)`為一位顧客枚舉到第$j$種衣服、且預算剩餘$x$元時，在第$j$至第$n$種衣服之間總共會購買多少件衣服。
> 我們有以下轉移：
> ```
> ans(j, 0..c[j]-1) := ans(j+1, 0..c[j]-1)
> ans(j, c[j]..10**9) := ans(j+1, 0..10**9-c[j]) + 1
> ```
> 因此可以使用支援分裂合併和區間加值的持久化樹堆(Treap)。令`treap[j]`表示`ans(j, ...)`，從`treap[n]`開始倒著做到`treap[1]`。回答詢問時只要查詢`treap[1]`相應的節點即可。

是一題毫無巧妙觀察可言，純粹推廣資料結構知識的經典操作題。這是Codeforces Educational的題目原罪。

但是讓我靈光乍現的不是標準解法，而是以下的[趣味另解](https://codeforces.com/contest/702/submission/42080556)：
> 定義一件衣服為第$k$級，若且唯若該衣服價錢$c\in [2^k, 2^{k+1})$。
> 同時定義一位顧客為第$k$級，若且唯若該顧客的剩餘預算$x\in [2^k, 2^{k+1})$。
> 注意到顧客在第$k$級時，買得起所有第$0$至$k-1$級的衣服（下稱低級衣服）、買不起所有$k+1$級以上的衣服（下稱高級衣服）、並且買得起**至多一件**第$k$級的衣服（下稱同級衣服）。
> 而且顧客**絕對不會跳過**任何一件低級衣服不買。
> 所以分析該顧客在第$k$級時的行為，只有以下兩種：
> > 1. 不斷購買低級衣服，直到預算降級（或逛完所有衣服）。
> > 2. 不斷購買低級衣服，然後購買一件同級衣服，購買完馬上預算降級。
>
> 所以可以把服飾店分成$\lceil \log_2 10^9\rceil=30$層，每層只依序擺放同級跟低級衣服。
> 每來一位顧客就放到相應樓層，每層可以簡單二分搜找到該顧客降級的位置和該級購買衣服總數，然後將該顧客降級並重複以上操作。

我當初耳聞上述另解時就覺得非常巧妙。它用到的單調性非常隱晦，尤其是$c[j]$並沒有排序過，基本上整個性質結構就藏在`b[i]-=c[j]`的減法操作裡面。
對我來說，只看到減法就聯想到倍增法這點非常不可思議。
這個做法的經典操作方面尚嫌不足，但是巧妙觀察肯定滿分。
於是我想：要是可以再多套上若干經典操作的話⋯⋯

接著就在走廊上來回踱步了十來分鐘，嘗試發想將上述另解改造的手段，但是沒有想出什麼特別好的方法。我便停下思考，跟著選手去吃飯了。
此後的IOI 2018行程我都沒有再碰這件事。
但是我記得，那十來分鐘內所聯想到的其中一個觀點很有趣：
> 想像把整個顧客購買衣服的過程，從最後一刻倒帶到最剛開始。
> 時光倒流的觀點看來，一開始有一個很小的數值$x$，它要從$c[n]$遍歷到$c[1]$。
> 基於「某些機制」，$x$遇到特定$c[j]$時會發生`x+=c[j]`的事件。
> 而當$x$的最高位元提升的時就會「升級」。

當下我沒能想出所謂的「某些機制」究竟能填入什麼。畢竟在「服裝店購買衣服」的設定下，你有可能是之前有$x+c[j]$元，買了$c[j]$之後變成$x$元，或是之前就只有$x$元，之後沒有買$c[j]$。時光倒流的時候只知道結果是剩下$x$元，但是「究竟有沒有購買」的資訊無法恢復。

——但有那麼一瞬間，上述觀點給我一種「在遊戲中打怪，經驗值滿槽升級」的意象。
那感覺真是有趣。

## 從原型到半成品
時間來到二〇一九年八月初，也就是足足十一個月後。那年暑假我沒有回家，而是留校做研究。
那個時候似乎正流行著一款遊戲叫做[Agar&#46;io](https://agar.io/)（或著說，在我的Youtube Feed上流行）。
我在觀看Agar&#46;io遊戲實況的時候，聯想到了以下題目草稿。有看過或玩過Agar&#46;io的讀者想必一眼就能看出跟該遊戲機制的高度關聯性。
> 在一個二維座標平面上，散佈著許多大大小小的圓。
> 這時有一位玩家登入遊戲。玩家的圓出現在原點$(0,0)$的位置。
> 玩家的圓有兩個屬性，一個是「顯示半徑」、即在螢幕上畫出的圓半徑，另一個是「能力半徑」、某種程度上代表玩家的能力值。
> 由於遊戲繪圖引擎的機制，一開始玩家的「顯示半徑」為$0$。
> 接下來繪圖引擎會讓玩家的圓在圓心固定的情況下逐漸膨脹，膨脹到「顯示半徑」等於「能力半徑」時停止。
> 但是有可能在膨脹停止之前，螢幕上顯示玩家的圓碰到其他的圓（即「顯示半徑」加上該圓半徑等於兩圓心距離）。
> 這時會進行以下運算：
> > 1. 如果玩家的「能力半徑」大於等於該圓的半徑，那麼玩家會把該圓「吞噬」：「能力半徑」會增加該圓半徑的量。繪圖引擎也會更新「顯示半徑」膨脹的目標值為新的能力半徑。
> > 2. 否則玩家被該圓「吞噬」，玩家就輸了，遊戲結束。
>
> 現在給定盤面和玩家的「能力半徑」，問玩家的最終結局（輸贏、以及最終兩項半徑數值為何）。

但那之後沒過幾秒就想出了解法：
> 把所有的圓照到原點的距離（圓心距離減半徑）由小到大排序，命名為$c[1]$到$c[n]$。
> 之後從$1$到$n$依序計算把$c[i]$吞噬所需的最小初始能力半徑。是一個轉移$O(1)$的動態規劃（DP）。
> 回答每個詢問只要在DP陣列上二分搜即可。

這個題目草稿過分簡單了，不滿意。所以嘗試把它改難：
> 如果玩家有外掛呢？例如說，如果碰到一個會吞噬自己的圓，就把它強制斷線？或是把它的（能力）半徑強制改成上一個成功吞噬的圓半徑並直接吞噬？

結果還是沒過多久就做出來了，之後的幾個版本也是。
最後過了一段時間才發現本質上的問題在於不管是哪個版本，單調性都太強了：只要玩家的初始能力半徑越大，結局的兩項半徑數值都越大。
所以就激發了下列版本：
> 既然不爽「大者恆大」，那就直接強制讓小的變成比大的還大好了！也就是變成`r+=(r>=x?x:y)`的機制，其中$y$可以比$x$大。

這個版本就難多了，一開始想了幾分鐘都沒想出作法。
但接著突然靈光乍現，腦中閃過「在遊戲中打怪，經驗值滿槽升級」的意象，然後就回想到之前在IOI 2018想到一半的另解。
再來就發現依照玩家當前能力半徑的最高位元分級，就可以做了。

想到這裡，覺得這個版本的題目挺有意思的，就跑去打開筆電，稍微擬了下題目敘述還有子任務，心想這題或許可以投稿到哪裡的小型區域比賽也說不定。

## 從半成品到完成品

之所以不投稿到IOI，是因為它還存在以下幾個缺點：
1. 雖然跟好題的評斷標準關係比較弱，但是我覺得它的題目設定不太自然：為什麼外掛可以讓半徑`+=y`，而且可以比原本大小還大？這外掛也太爛了吧，直接不管三七二十一都`+=y`不是讓玩家更有優勢更好嗎？
2. 跟CF 702F一樣，這題還是有辦法用Treap做。轉移變成`ans(j, 0..x[j]-1) := ans(j+1, y[j]..y[j]+x[j]-1)`和`ans(j, x[j]...) := ans(j+1, 2*x[j]...)`，基本上大同小異。

那段時間我正好在看某部地下城(Dungeon)主題的日系後宮動畫，然後有一天突然不知道腦袋被什麼打到，心血來潮想把背景設定從Agar&#46;io變成這種風格，於是把題目敘述中的每個元素都對應過來：
> 1. 二維平面上的$n$個圓 $\rightarrow$ $n$個地牢連成單向鏈結串列（二維本來就是騙人的，照距離排序之後本來就是一維問題）
> 2. 能力半徑 $\rightarrow$ 玩（ㄋㄢˊ）家（ㄓㄨˇ）力量值
> 3. 第$i$個圓到原點的距離 $\rightarrow$ 解鎖第$i$個地牢入口大門的最低所需力量值$e[i]$
> 4. 第$i$個圓的半徑 $\rightarrow$ 第$i$個地牢內的敵（ㄋㄩˇ）人（ㄓㄨˇ）力量值$s[i]$（反正動畫裡打贏的就直接收服，力量值直接加過來貌似十分合理）
> 5. 第$i$個圓的「外掛半徑」 $\rightarrow$ 第$i$個地牢打輸的話，敵（ㄋㄩˇ）人（ㄓㄨˇ）施捨的道具實用度$p[i]$。

但是轉譯過來之後出現了新的題敘自然性問題：之前敗給其他的圓被吃掉很合理，現在敗給敵（ㄋㄩˇ）人（ㄓㄨˇ）好像⋯⋯不太方便被吃掉？
於是就設計了兩個「輸掉之後要怎麼辦」的模型：
> A. 在同一間地牢不斷重試直到打贏。（每次打輸力量都會增加$p[i]$，所以遲早有一天打的贏）
> B. 引入生命數量的概念，主角每打輸一次就犧牲一條命進到下一間地牢。

想了一會之後，發現模型A有一個非常小品且有趣的性質：只要在一間地牢輸掉，那麼活著走出那間地牢的時候，主角的力量值至少倍增。
但相比之下覺得模型B的題目敘述更加自然，所以當下的我還是比較喜歡模型B。
可惜的是模型B本質上沒有改變Treap可以做的事實。

接下來幾天，我閒下來的時候就時不時的在想模型B要怎麼卡掉Treap。
嘗試過引入一些其他的遊戲概念，不過要不是把題目改得做不出來，不然就是卡不掉Treap。
如此這般試了一陣子之後，逐漸浮現一種感覺，覺得自己沒有「看破」這題考點的「本質」，於是就開始改往這個方向思考。
最後在某一天，往學校圖書館的人行道路上，我想通了：
> 這題本質上的結構，就是利用跟$s[i]$比較大小的結果做某種「分枝」（branching）：比$s[i]$大的時候會發生一件事，比$s[i]$小的時候發生另外一件事。
> 然後解法本質上在做的事情，就是想辦法執行某種高效率分枝預判（efficient branch prediction）。
> 高效率的點在於把預判錯誤（misprediction）的代價（cost）綁定到「主角力量值倍增」的事件上，來限制預判錯誤的總量。

或許是被「分枝」這個用語給提示到了吧，我接著想到以下改法：
> 那就比$s[i]$大的時候走一條路，小的時候走另一條路？

然後差不多在走進圖書館的時候，我發現這個改法成功卡掉了Treap。
所以接下來在圖書館的時間都沒有在認真做研究，而是一整個下午都興高采烈的在改寫題目跟設計子任務。
一邊寫的過程還一邊發現可以把「解鎖大門」的條件拿掉，並把生命數量的概念擴展成HP（血量），最後就變成了以下的版本：
> 有一座地下城，裡面有一位主角、$n$個敵人（編號$0$到$n-1$）、跟$n+1$間地牢（編號$0$到$n$）。
> 第$i$個敵人位在第$i$間地牢內，且擁有兩個屬性：力量$s[i]$跟傷害$d[i]$。
> 主角一開始進入地牢$x$，擁有力量$t$跟血量$h$。主角每次進入地牢$i$的時候，就會跟敵人$i$戰鬥：
> > 1. 如果$t\geq s[i]$，那麼主角勝。戰鬥獎勵為`t+=s[i]`，且獲取獎勵後主角會接著進入$w[i]\,\,(w[i]>i)$。
> > 2. 反之，如果$t<s[i]$，那麼主角敗。戰鬥獎勵為`t+=p[i]`，但主角會受到傷害`h-=d[i]`。接下來：
> > > 2a. 如果主角的血量「歸零」（$h\leq 0$），則遊戲結束。
> > > 2b. 否則主角會接著進入$l[i]\,\,(l[i]\leq w[i])$。
>
> 此外，當主角進入地牢$n$時，則遊戲結束。
> 現在要模擬$q$位主角。對於每位主角的初始地牢$x$、初始力量$t$、和初始血量$h$，輸出遊戲結束時該主角的地牢編號、力量及血量。

以下是我對於此版本是否為好題的分析。

#### 巧妙觀察
變成了CF 702F另解的對偶版本，需要根據敵人的最高位元分層。
整個性質結構就藏在`t+=s[i]`的加法操作裡面。
我覺得只看到加法就要聯想到倍增法，跟CF 702F另解的減法聯想同樣不可思議。

#### 經典操作
每一層需要在樹上動態規劃（樹DP），以及倍增法找預判錯誤點。
層層之間也形成一種倍增法的結構。

單看其中一個工具絕對不足100/100分。我覺得DP可能佔個30/100分，前綴加個「樹」或許再加個10/100分。
此外，倍增法大概也能算個30/100分左右吧？不過用到了兩次，而且使用的動機完全不同、互相獨立。
所以⋯⋯$30+10+30\times 2 = 100$？

#### 抗唬爛
千辛萬苦總算讓噁心的持久化Treap不可做了。其他的唬爛方式我想不到。

#### 非高等知識
樹（DS5）、動態規劃（AL2）、倍增法（AL3b）。一切合法，謝謝指教。
嚴格說起來持久化（AL3b）跟Treap（AL3b）也不算高等工具，但是不管怎樣前述三項絕對都比這兩個來得初等。

#### 總結

| 巧妙觀察 | 經典操作 | 抗唬爛 | 非高等知識 |
|:---------|:---------|:-------|:-----------|
| 100/100 | 100/100 | ✔️ | ✔️ |

所以我決定將這題投稿到IOI 2020。

## 子任務設計
一題的子任務為何不太會影響該題本身有多好或不好，只是要協助細分各程度的選手能力而已。我覺得基本上只要把題目切出大致的難度線、決定每個關鍵性質或工具要分配給哪個等級的選手就可以了，剩下的就讓IOI主辦方去微調吧。
我的分法如下：
> A. 難度：「水」（約路人程度）
> > 1. $n, h \leq 10$
強行模擬就可以拿到的分數。用到的性質是每個玩家每遍歷$n+1$個點一定會至少扣一滴血，所以強行模擬每個詢問的時間複雜度是$O(nh)$。
此外我也在題解文件中給出另一個強行模擬的時間複雜度上界：$O(n+h+\max_i s[i])$，因為模擬$h + \max_i s[i]$步後如果還沒死就一定已經強過所有敵人了，只要再頂多$n$步就到終點了。

> B. 難度：「易」（約銅牌程度）
> > 2. $w[i]=i+1,\,\, l[i]=i$
> > 3. $s[i]=p[i],\,\, l[i]=w[i]$
受到模型A所啟發的兩件子任務。用到的性質都是「只要輸了，要馬原地死亡要馬離開時力量倍增」。

> C. 難度：「中」（約銀牌程度）
> > 4. $s[i]=s[0]$ （`len(set(s))=1`）
> > 5. `len(set(s))<=10`
提示性的兩件子任務。希望啟發參賽者發現「把力量接近的敵人集中處理會有好事發生」。
由於要處理擬樹（pseudotree）的程式碼稍微難寫一點，所以我判斷比子任務2、3難。

> D. 難度：「難」（約金牌程度）
> > 6. $l[i]=w[i]$
> > 7. $l[i]>i$
> > 8. 無額外條件
三件子任務都必須要先發現「可以倍增處理敵人能力值」的性質。
從6到8基本上沒有要求什麼新的觀察，只是覺得如果沒有擬樹（子任務6、7）的話說不定會有意想不到的部分分數解法。

## 驗題
我找了四位IOI前選手來驗題：[<span style="color:red">**matthew99**</span>](https://codeforces.com/profile/matthew99)、[<span style="color:red">**c_sunshine**</span>](https://codeforces.com/profile/c_sunshine)、[<span style="color:red">**briansu**</span>](https://codeforces.com/profile/briansu)、和[<span style="color:red">**NoLongerRed**</span>](https://codeforces.com/profile/NoLongerRed)。由於覺得子任務5會給他們過多提示，所以給他們的題目版本只有子任務1到4和6到8。

### 得分及作法：<span style="color:red">**matthew99**</span>

| 子任務 | 1 | 2 | 3 | 4 | 6 | 7 | 8|
|:------|:- |:--|:--|:--|:---|:------|:-|
| 得分 | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ |

滿分。而且是我預期的正解。
除此之外他還發現跨層使用的倍增可以不以2為底數，如果用3或4之類的當底數可以節省記憶體，不過每層的詢問時間會多常數倍。

### 得分及作法：<span style="color:red">**c_sunshine**</span>

| 子任務 | 1 | 2 | 3 | 4 | 6 | 7 | 8|
|:------|:- |:--|:--|:--|:---|:------|:-|
| 得分 | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✖ |

子任務1到4的作法跟我想的一樣，但是他利用路徑單調向右的性質，給出了子任務6和7的另解。
不過使用到的工具過於高級：線段樹分治套持久化Treap。嚇死我了。

### 得分及作法：<span style="color:red">**briansu**</span>及<span style="color:red">**NoLongerRed**</span>

| 子任務 | 1 | 2 | 3 | 4 | 6 | 7 | 8|
|:------|:- |:--|:--|:--|:---|:------|:-|
| 得分 | ✔️ | ✔️ | ✔️ | ✔️ | ✖ | ✖ | ✖ |

子任務1到4的作法跟我想的一樣。感謝他們讓我確定這題的難度大致符合我的想像，並且讓我獲得了「這題感覺的確有比APIO 2018的兩題好」的評論，讓我信心大增。

## 入選後
這題其實二〇二〇年時就入選IOI了，不過當年是備選題，隔年IOI 2021才成為正式題。
題目敘述在此：[官方英文版](https://mirror.ioi2021.sg/statement/dungeons-ISC.pdf)、[各國翻譯版（含中文版）](https://mirror.ioi2021.sg/statement/dungeons.zip)。

### 題目敘述
入選之後審委會（ISC）把題目敘述做了一些更動，例如說把沒用的純故事性性質（$l[i]\leq w[i]$）刪掉，但最主要的是把題目背景設定大量「和諧化」了。
血量、傷害、跟死亡的概念全部都被移除，而且沒有移除的部分也使用了更加委婉的用字，如「敵人(enemy)」變成「對手(opponent)」、「戰鬥(battle)」變成了「遭遇(confront)」。
附帶一提，日本隊把官方英文版的和諧用語又反向翻回我版本的「敵（てき）」跟「戦闘（せんとう）」。さすが日本人（草）

### 子任務

#### 水
由於血量的概念不見了，所以ISC採用我的另一個上界來設計子任務。

#### 易
ISC採用了我的子任務3。子任務2跟3本質上運用的是同一個觀察，所以兩個本來就互為替代品。
不過由於血量的概念不見了，只好使用路徑來做分枝（branching）。

#### 中
兩個都被採用了。

#### 難
ISC採用了子任務8和<span style="color:red">**matthew99**</span>壓縮記憶體用量的解法。
我在投稿的題解文件附錄中有提到<span style="color:red">**matthew99**</span>和<span style="color:red">**c_sunshine**</span>的作法，而我猜ISC可能覺得不想給線段樹分治套持久化Treap分數吧？

## 後記

沒有意外的話，"Dungeons"應該是我在競技程式圈最終的告別作了吧。
高中畢業之後就長期幾乎沒有作題跟打比賽了，所以隨著時間過去、競程的記憶凋零，我編出IOI題目的機率只會嚴格遞減。
所以二〇一八年時就有預感，這題可能就是競程生涯最後的孤注一擲了。
很感謝"Dungeons"能讓我的競程生涯以最完美的結局收尾，也成為我最好的大學畢業禮物。
如此一來我在競程方面就沒有遺願了，也準備好邁向人生下一個階段了。

接下來的這一段，作為競程告別作的心得文的最後一個段落，很有可能就是我在競程圈所留下最後的文字了。
我決定回顧一下這整段"Dungeons"編題的旅程，並給有意願出題投稿到IOI的前輩、同輩和後輩們，以我非常主觀的想法，分析設計IOI題究竟需要什麼：
> 1. 大量的基礎知識。
> > 此項目大致對應到好題標準的「經典操作」方面，想在「經典操作」拿到滿分的必要條件就是自己看過夠多操作。這也說明了為什麼歷年IOI出題者中常有資深競程選手或資工系教授的名字。
> 2. 擁有足夠強的觀察力、或是認識大量的題目性質與觀察。
> > 此項目大致對應到「巧妙觀察」方面。前者跟後者在解決高等競程難題都是非常必要的，這也說明為什麼資深競程選手喜歡跟數奧選手組隊。
> 3. 聯想力/創造力、以及快速判定題目可做性的能力。
> > 出題者可以從看過的題目、大學上過的課、看過的書、甚至玩過的遊戲、看過的影片、讀過的漫畫等生活經驗出題。當你開始嘗試變造題目、甚至憑空發想題目時，你要有辦法在足夠短的時間以內運用上述兩項能力，判斷當前題目版本究竟可不可做，大致難度為何，以及「經典操作」或「巧妙觀察」兩方面是否足夠好。如果不可做、太難、太簡單、或不夠好，要有辦法運用聯想力跟創造力走出當前的死胡同。
> 4. 思路不一樣的朋友。
> > 就像幫我驗題的幾位選手們所做的一樣，這樣的朋友可以幫助你發現自己沒想到的作法或細節。透過跟他們的討論也可以幫助釐清自己的想法。
> 5. 恆心。
> > 跟選手不一樣的是，出題者必須拋棄「五小時內做不到更好就收手」的心態。雖然用到的技能集合高度相似，但比賽是百米衝刺、出題卻是野外拓荒。不僅方向不明確，也不能保證一條思路是不是可以帶你走到終點。所以你至少要能夠耐得住那條路的長，比五小時還長非常非常多的長，你才有機會看見那條路最終帶你到了什麼地方。
> 6. 信心。
> > 但即便如此，拓荒開出的小徑走到了盡頭，也還是不能保證結尾就足夠優秀——你只知道那個終點憑你的能力已經沒有辦法再變得更好了。我覺得我在APIO 2018的兩題都是這樣，雙眼可及之處已經不存在改進的方向了，也就是卡在了局部最佳解。這時也沒有辦法再做什麼，只能換個種子當新的起點，勇敢的用顱骨內那坨真・神經網路，從頭再重跑一次梯度下降法。但是永遠都要保持信心，相信下一次會更好。要對自己長年累積的能力有信心，相信自己。
> 7. 愛。
> > 很久很久以前的一天，比IOI 2018還要早的一天，我在某次與朋友聊天中提到了CF 702F的趣味另解。我以興奮得兩眼發光的態度展示那個解法，以及我覺得它在我看來有多麼酷炫。但是得到的回應卻是「要是比賽我肯定不寫這種東西。我肯定寫持久化Treap。」
> > 他是對的。比賽得分要緊，才沒有參賽者管你解法優不優美，性質巧不巧妙。在最短的時間內、花費最少的精力、獲取最多的分數，這才是身為選手唯一的硬道理。
> > 但是⋯⋯喜歡的東西不被認同的感覺，真的很讓人不甘心。
> > 我是真心覺得它很酷，覺得它值得被參賽者認識。
> > 或許這份心情，才是我願意為了一個報酬金等於零的項目，在二〇一九年八月初到九月底，整整八週的期間如此不計成本的燃燒自己寶貴的空閑時間的原動力。
> > 雖然或許得花上好幾年的光陰，但是時間終究證明，它的確值得。
> > 對我來說，這樣就夠了。