前言
Written by pooh at 2024/08/27
在暑假的末端 vir 完了 BOI 2018，題目有些蠻有趣的，大概是我逃避事實的其中一環。
也算是我從 4 月初後爆刷 atcoder 的驗收，希望有進步一些。
格式我是抄 Little Cube orz Blog 的
下面開始就會是大暴雷了。
Day 1
一些廢話
這場我是在從英國回台灣的飛機上 vir 的，因為馬航有提供免費的網路，結果因為我在飛機上沒睡覺所以回來時差超難調。然後一開始前半小時還想說還算舒服，結果後面就遇到超大亂流，超想吐，只好提早放棄。
題目
對不起我懶 QAQ
賽中過程
0:00
先讀了 pA ，腦中的想法大概是很像水母圖上的帶權匹配? 實作細節還沒想好，所以就先繼續讀。
接著看到 pB 發現他是超水的雙指針，所以應該等等會先寫他。
再來看到 pC 就發現一整個被嗆，他根本就是三維版的人生低潮，被抓到沒有好好補題，順帶一題那一題讓我痛苦到我甚至跑去改名，然後我還是不明白官解為什麼是好的，結果又遇到 = =，所以只會做一維的。
實際分數: 0 / 0 / 0
精神分數: 21 + ? / 100 / 10 + (22 要黃金比例搜)
0:28 & 0:32
pB 大概只花了 15 min 就寫好了，一上傳竟然吃 WA (BTW 飛機上網路慢到大概 0:30 才看到 verdict)，緊急 debug 一下一看就發現我不等號打錯，改了就 AC 了。
實際分數: 0 / 100 / 0
精神分數: 21 + ? / 100 / 10 + (22 要黃金比例搜)
這時候我覺得我對 pA 的細節還要稍微想一下，所以先去做了 pC 的 local test 跟 10 分的簡單子題
1:24
pC Local test 寫完，10分拿到，回去好好想 pA 的 Case。
實際分數: 0 / 100 / 10
精神分數: 21 + (79 感覺快出來了) / 100 / 10 + (22 要黃金比例搜)
中間跑去吐了一下，亂流真的太大了。
2:56
克服了亂流以後發現 pA 根本跟 關卡地圖 一個梗 (雖然好像在一開始就大概知道了)，所以先寫了只有樹的子題。
實際分數: 29 / 100 / 10
精神分數: 100 / 100 / 10 + (22 要黃金比例搜)
3:13
加上環爛掉了，大出事
實際分數: 29 / 100 / 10
精神分數: 100 / 100 / 10 + (22 要黃金比例搜)
3:49
決定先去拿暴力來對拍
實際分數: 29 + 21 / 100 / 10
精神分數: 100 / 100 / 10 + (22 要黃金比例搜)
4:24
對完拍也把 case 判乾淨了。
實際分數: 100 / 100 / 10
精神分數: 100 / 100 / 10 + (22 要黃金比例搜)
然後到這邊我就覺得暈到該休息了，所以我棄了 pC 的 22 分。
檢討
首先就是被抓到沒有好好補題，跟實作黃金比例搜不夠熟所以不敢試。
不然 pC 至少會有 63 分。
接著就是 pA 的實作還是沒有想清楚，如果不是有對拍這個能力我就爆炸了，而且實作也太慢了。
最後就是還是應該好好睡覺的 = =。
最終分數 : 210
好像就普通，跟我一起 vir 的人好像也是差不多或一樣的分數，pC真的太鬼了。
Day 2
一些廢話
這場我跟 Day 1 差了一個禮拜 vir，然後這個時候我的房間還在漏水，所以我的床佔據了我的地板，造成我的椅子沒地方放，所以我只好趴在床板上打。
我還在床板上打了 CF 跟一堆東東，現在還在上面打這篇 blog。
希望漏水快點好。
題目
賽中過程
0:00
讀完 pA 以後感覺就是我不會的貪心，性質很多又完全沒有性質的感覺。
pB 讀完以後直覺馬上想到 bitset 可以做到
pC 讀完後就感覺是 DP，然後可能找好方法合併就好，沒有想的很細節。
實際分數: 0 / 0 / 0
精神分數: 13 / 46 / 70
0:20
這大概是讀題之後的 8 min，我先把 pB 跟 pC 的輸入吃好。突然發現 pB 對於每個 ATCG 維護的 bitset 其實可以換成一個 hash 值，然後每個人的二維 bitset 也可以換成一個 hash 值，複雜度秒便
實際分數: 0 / 0 / 0
精神分數: 13 / 100 / 70
0:35
pB 一發 AC。
改去做 pC
實際分數: 0 / 100 / 0
精神分數: 13 / 100 / 70 + (30 bitmask 吧)
1:32
pC 先寫了 bitmask DP 版，結果只有 70，感覺自己假解了，跑去換奇怪的 ad hoc 作法。
實際分數: 0 / 100 / 70
精神分數: 13 / 100 / 70 + (30?)
2:10
中間一度 pC 又重拿了一次 70 分。結果發現我 bitmask DP 只是大小開錯而已 = =。 改了一下就 AC 了。
實際分數: 0 / 100 / 100
精神分數: 13 / 100 / 100
2:38
pA 有一個我自己覺得有點蝦的貪心，不敢寫。先去拿了暴力 13 分。
實際分數: 13 / 100 / 100
精神分數: 13 / 100 / 100
然後我就覺得該放棄了，跑去想專題，明明就有一個貪心想法然後覺得是爛的就不敢寫，混到了大概3:10才回來想。
3:20
證了一下我的貪心在不是環的狀況下是對的!
然後就去寫了
實際分數: 13 / 100 / 100
精神分數: 13 + 19 / 100 / 100
3:37 & 3:40
19 分拿到了，花了一點時間手動聯集
實際分數: 32 / 100 / 100
精神分數: 32 / 100 / 100
但這個時候似乎是受到不知道誰在關卡地圖的唬爛的啟發還是 IOIC 的隨機課有認真聽，我突然覺得可能我亂把環變成練可能可以喇到一些分數。
3:54
唬爛過了 = =。
完全沒想到的狀況。就這樣300了，有點開心。
實際分數: 100 / 100 / 100
精神分數: 32 / 100 / 100
檢討
首先 pC 花了超出該花的時間太多了，反倒是 pB 根本是賺到，因為才剛在專題遇到用 hash 證明某個東西，然後想法有點類似才讓我可以想這麼快。
接著是中間注意力渙散這件事，我覺得是因為我練的 OI 還不夠多，可能要再多打幾場，然後 pA 超過 13 分的根本都是撿來的，這也告訴了我唬爛真的是有用的。
最後是很意外的就這樣莫名其妙破台了，甚至比當年最快破台的還快，有點爽。
最終分數 : 300
好像大家 day 2 都打的比 day 1 爛，聽到很多 13 + (19) / 46 / 100 的。
兩天總分
總分 : 510
大概是 Rank 3， Gold。
但如果 day 1 pA 我有好好補題的話就可以到 Rank 1 了，不過如果正常其實 day 2 我大概只能拿 213。
只能說還好我有好好唬爛。
感覺就是注意力很不足跟想 case 還是太爛了，我 day 2 pA 的貪心好像改一改就是正解的貪心了，首要加強的應該是想 case 實作。可能要練一些大實作或甚至是 ad hoc，然後 OI 可能要多 vir 一點。