IOI 2021

只是想打一下IOI的心得而已
可能還是流水帳請多多包含(?)

Before

其實到二模都還很擔心會不會當上國手，還有擔心自己的實力到底有沒有變強
因為一模是因為靠奇怪互動線性遞迴的題目才上去，啊二模唯一寫出來的題目也是IOI根本不考的東西
另外很好笑的是我這學期比前兩個學期還努力追學分，因為之前太混了XD這學期剛好要全部過才夠畢業的學分竟然夠了
謝謝所有即使我交作業很混還是讓我過的老師!

四模拿了一個不錯看的分數，如果我在國手線下150分甚至可以抵回來(?)因為這件事我大概可以claim二階很好追分(並沒有)
因為疫情的關係國培燒雞，我超期待的說，還想說今年想再寫一次國培紀錄QQ
唯一比較算是訓練的東西是tmt(卡恩)和我們google meet討論一些題目
第一次meet的時候是先丟題目討論，然後也講了去年的模考題，像是expected LCS那題好像就是暴力DP(雖然我不知道複雜度是什麼)
ZCK真的超級積極，丟了好多POI或是JOI、CSAcademy的題目，好多題目我都是第一次見
基本上沒有什麼想法，不過就算只是聽解也蠻困難的，有一些證明因為卡恩也是當場想所以有點久，我也沒注意聽就做自己的事了XD
第二次meet主要討論IOI2019，有事前看過題目之後感覺就好一點了(?)不過因為一直想要把line得多一點分所以也沒有太專心(X
感謝卡恩與zisk讓我腦袋有在動(?)

Day0

看到好久沒看到的ZCK與wiwi還有(隔著口罩)呼吸到新鮮空氣心情還不錯
晚上是練習賽
題目都跟去年一樣
唯一不一樣的是一題BFS
結果還不能破台，好好笑
不過差點在賽中因為唬爛弄出正解(?)
結束之後問了一下ZCK解，果然他會只是剛好在兩小時的最後才想到(?)

Day1

day1前一天打了一場div.2寫完ABCD看完F猜他的式子很漂亮就亂推AC了 然後E寫好久總算寫完
這讓我感覺狀態還不錯，對我來說可能寫水題也是一個穩定心情的方法(?)

我們三個人還有監考人員占用一整個會議室，間隔開來坐
原本是用acer的筆電但是後來變成msi的樣子，因為好像跑比較快

開賽的時候先打了模板
ZCK帶來的鍵盤的聲音來讓人滿是壓力XD
然後看紙本題目想
然後…就沒有然後了
parks看起來有點困難先放著了一下
candies看起來就很經典題，而keys也是沒有什麼想法
一直畫圖交替想兩題，大概花了一小時還是沒有什麼想法
三個人維持了安靜好久，然後ZCK開始動鍵盤的時候有夠可怕
只好姑且先去撈分，撈了keys的基本分跟candies的一點分數
仔細看了parks發現可以弄成類似2SAT的東西不過實作異常麻煩，而且我也忘記tarjan怎麼寫甚至跑去寫kosaraju(?)
不過花了好久拿到了70分，我覺得還算值得
接下來就繼續把candies的分數撈一撈，有一個subtask似乎是我唬爛得到的分數賽後才發現，唬爛就是爽
最後一直在想candies $l=0, r=n-1$ 的subtask就結束了

結束之後有點怕自己又是銅牌命，趕快問分數，結果大家都一樣好好笑，而且都是銀牌左右的分數，看來 day1 實在蠻難的

Day2

day1/2中間似乎吃了雙豚還是山嵐
day2前一天因為睡不著跑去看了IOI2014之類的，然後發現做不出來趕快看解以免影響比賽，好好笑
心中不想太多的雜事，很快就開賽了

打完模板開始讀題目，然後就遇到很欠嘴砲的水題(?)大概在25分鐘內就AC了，有點帶給我小小信心(X
剩下兩題開始讀
registers實在有點長，當然只能先去看dungeons
因為想說贏了好像強度就會加倍，所以原本想說只會贏log次，寫到一半突然覺得怪怪
後來發現應該是「贏了輸過的人的話那麼強度會加倍」，然後就不知道怎麼做了
跑去讀registers題敘發現實在超級長，結果是要實作取min跟排序，感覺就是跟19的vision或是12的odometer這種題一樣噁心
想一想覺得應該可以做很多平行化，而且去年的國培蔡孟宗甚至還講過平行化的bitonic sort，結果今年沒國培，好慘
先做了取min的subtask，實作比較的方式我是先做減法，然後就可以有絕對值，就有min了
平行化大概需要170個操作左右，和最後一個subtask要求150只差一點但是怎麼都壓不過，傷心
後來看著dungeons一直想他怎麼樣會加倍，突然就想到2的冪次分層
也就是說如果現在的強度 $z\in[2^i,2^{i+1})$ 就說現在在第 $i$ 層，那一定會輸 $2^{i+1}$ 以上的人、贏 $2^i$ 以下的人，而一旦贏了中間的人就會跳到下一層!
啊待在某一層的時候一定是一直輸大的、贏小的直到贏了一個大的，因為是一張functional graph所以可以用倍增法
總之整理了一下寫寫倍增法就有了時間 $(n+q)\log^2C$ 空間 $n\log^2C$ 的解，不過 $n=400000$ 開不下，開 $n=50000$ 丟上去六十幾分覺得還不錯
後來測了一下發現記憶體少一點就可以開得下了，所以嘗試壓常(?)原本想說用分根號、立方根的，後來發現可以開到 $10n\log C$ 的記憶體就想說可以一次跳 $(10^7)^{\frac{1}{10}}$ 倍，然後一直亂改改就 AC 了??
這應該是第一次在賽中遇到二的冪次分層，實在覺得出出這些題目的人都很厲害
比賽最後在努力修改 registers 的情況下結束，可惜沒有再撈到分數

比賽結束的時候聽到ZCK跟balbit分數都沒有很好，覺得很可惜，而且看到scoreboard大家的名次都在30~40名內，真的覺得有夠可惜qwq
原本想說自己會銀牌，沒想到看scoreboard竟然有30名內，還真的是很開心
真的是很有趣，因為聽說我的dungeons的空間是壓常而不是預期複雜度，因為壓常而得金實在是沒有想到XD
不過就很好奇到底怎麼不用倍增法或是HLD在functional graph上面做類似二分搜的事情了OAO，我只能理解可以用HLD讓空間是 $\mathcal{O}(n)$ 但是HLD可是超出IOI syllabus的(?)
晚上買了sukiya，好感動。

After

對於一開始的擔心，我覺得可能是有道理的，我們幾個人的實力和一年前比起來一定都有成長，但題目和其他選手也都比去年的他們厲害，我想能得到金牌無非還是一種好運吧！一個人的實力是一個浮動的區間，剛好想到怎麼壓常也是一種緣分吧

在二階左右的時候常用的筆電被我不小心摔壞了螢幕，現在先用暫時用的筆電，還好我的部落格好好放在github上可以好好修改(?)

我覺得IOI有點是給我一個理由耍廢不做事有點心虛
最近又有好多事情要做，例如趕完APCS camp的投影片XD 不過這樣也好，人生不找點事情做會無聊死，忙著不去胡思亂想還好多了。

最近和ot他們第一次團練ICPC，感覺我有夠菜，希望能好好融入他們

本來想這篇心得要不要打得像是 baluteshih 那篇心得一樣長，不過我好像不擅長鋪陳也不擅長回想所以就作罷了吧
好久沒有更新部落格了，大概慢慢就不太更新了吧