2022.12.18 -- 2022.12.24

Posted on Edited on In ,

第二篇周記，categories 寫日記只是為了避免之後這系列變成月記或是季記還有寫日記不想分成很多類。

Day -293 -- 2022.12.18 (CF 1774)

昨天晚上的比賽大掉分了，但在得知自己 FST 的時候並沒有什麼心情變化。 特別值得一提的題目是 1774E. Two Chess Pieces：

給定一棵樹，一開始有兩個棋子位在點 \(1\)，兩個棋子分別有可以以任意順序拜訪的點們：\(a_1, a_2, \ldots, a_{m_1}\) 以及 \(b_1, b_2, \ldots, b_{m_2}\)，並且最後兩個棋子必須都回到點 \(1\)。

你每一次操作可以將一個棋子移動一步，你需要保持兩個棋子的距離不超過 \(d\)，請問最少的移動步數是多少？

  • \(2 \le n \le 200\,000\)。
  • \(2 \le d \le n\)。
  • \(1 \le m_1, m_2 \le n\)。

我的做法比較暴力而且是 \(\mathcal{O}(n\lg{n})\) 的，因為有學弟來問所以就整理一下：

  1. 將所有點重新用 DFS 順序編號，重編號時會一併維護一個點的父親 par[v]、子樹的最小最大編號 mn[v]、mx[v]、深度 par[v]，並且會把每個點的 adjacency list 排序過。
  2. 用一個 deque 來記錄兩個點之間的路徑。
  3. 每次看哪個棋子的目標編號比較小就讓他往目標走過去。
    • 如果 mn[v] <= goal && goal <= mx[v] 就代表在子樹裡，因為 adj. list 排序過所以可以使用 prev(upper_bound(ALL(adj[v]), x)) 得到要往哪個小孩走；反之就代表目標要往 par[v] 走。
    • 這邊需要額外處理的是「往回走」的情形（不是往 par[v] 走），可以透過判斷要加進去的位置跟 deque 裡面的正數或倒數第二個位置來判斷。
  4. 在走的時候如果 deque 裡面有 \(> d+1\) 個點就代表距離 \(> d\)，這時就會把另一端的點 pop 出來。
  5. 最後因為要讓兩個點都移回根，需要再將答案加上兩個點的深度。

在做完之後看了題解發現他寫的超級精簡，需要用到以下觀察。

某一個棋子在 \(v\) 的時候另一個棋子一定在 \(\texttt{par}^d[v]\) 的子樹裡面。

也就是代表另一個棋子會經過 \(\texttt{par}^d[v]\)，所以可以直接把所有的 \(\texttt{par}^d[a_i]\) 加進 \(b\) 裡面；以及把所有的 \(\texttt{par}^d[b_i]\) 加進 \(a\) 裡面。

加完之後兩個棋子就完全可以分開來了！變得可以在 \(\mathcal{O}(n)\) 時間做完，而且超級好寫。用我之前的做法來看的話會發現他們的距離永遠會保持在 \(d\) 以內。

中午吃了弘爺當早午餐（好久沒吃ㄌ），稍微休息了一會兒就去收拾行李帶著飲料準備去坐火車了。希望五件發熱衣可以幫助我撐過這個冬天 OwO

晚上去西門吃晚餐，本來想吃沒吃過的拉麵，但發現手機快沒電了到時候一定會迷路就放棄了，鳥人在 18 號吃感覺就很虧 (?)，花月嵐排超多人，最後就決定吃 Coco ㄌ。掃 QRCode 點餐的時候手機只剩下 1% 電，還好來得及耶～

吃完後去雜誌瘋買了 Blue Lock 跟菜鳥煉金術師，再來本想去 animate 但是剛好遇到物品盤點 (?) 所以提前兩小時關門，改去虎之穴發現帶著飲料不讓進去只好先在外面喝完上廁所丟掉。想去買運彩壓阿根廷 2 : 1 法國又因為手機沒電不知道怎麼用又放棄了（還好沒買哈哈）。

回到宿舍的時候大約是 11:15 左右，發現 118 的同學在看世足於是就放棄先把行李抬上樓的想法去追完整場決賽。

本來以為上半場 2 : 0 法國要下去了，結果下半場 Mbappe 又上演驚天地的 90 秒進兩球追平。到了延長賽本以為會維持 2 : 2 進到 PK，卻看到在 E.T. 下半場阿根廷進了一球之後在禁區內手球被 Mbappe 追平。最後是法國十二碼全部都踢左邊被守爆才輸的（不過 Mbappe 三次踢左邊都進了），感覺完全是他在被隊友雷嘛 OwO

最後是直接在 118 睡了一個晚上，早上起床把行李搬到四樓才意識到沒有準備日文小考，燒雞 QQ

Day -292 -- 2022.12.19 (AT Custom Lockout)

早上上完日文課之後跟 ub33 ㄘ午餐順便討論了一些 PCCACamp 要做的事情，我覺得去年的時間實在是太趕了，甚至到了比賽當天還在改、換題目。

上禮拜 2023 OIS Round 2 那場我說要樹剖的題目完全是我在吃毒，我把題目轉化成強制在線的「單點加值、詢問點到根的權值和」之後就直接 claim 他只能樹剖，但其實可以再變成「子樹加值、詢問點權」就一樣也只要一棵 BIT，複雜度還少個 \(\log\)。

下午則是去 ub33 宿舍玩 (X) 思考比賽要出什麼咚咚 (O)，結果想出了一些我完全不會做的 idea，不知道最後能不能用上。

吃完晚餐後回宿舍打掃了一會兒書桌就開了一場 AtCoder Lockout，取了 ABC 裡面難度 18xx 到 23xx 的題目各一題來打兩小時，最後是寫掉了 18xx、20xx、21xx 的三題順利拿下分數，ub33 因為燒雞在 23xx 的題目（AC x 50 + WA x 1，超慘）導致最後掛蛋。

其中有一題看起來很幾何的題目我記得之前有看過，而這次終於把他做出來了！

平面上有 \(y = 100\) 跟 \(y = -100\) 兩條邊界線，以及一堆大小可以忽略的點 \(\{(x_i, y_i)\}_{i=1}^{N}\)。你要從 \((-10^9, 0)\) 推一個圓盤到 \((10^9, 0)\)，並且你不能穿過邊界線跟那些點，請問圓盤的最大半徑可以是多少？

  • \(1 \le N \le 100\)。
  • \(|x_i|, |y_i| < 100\)（\(1 \le i \le N\)）。

一開始的想法是二分搜半徑 \(r\)，並讓邊界線跟每個點都往外長 \(r\)，再去計算聯集出來的形狀能不能會不會完全蓋住。這時仍一度以為是噁心的幾何題，直到在紙上畫了幾個圓才發現一個重要性質：上下連通 \(\implies\) 左右不連通，可以用 DSU 做判斷。

而二分搜也可以被壓掉，實際上答案只會是某兩個點或是線之間的距離，所以就把那些距離都蒐集起來從小做到大就可以了！

打完之後看了沒做出來的題目題解，發現我完全沒想法的字串根本就是大水題，接下來就到處亂逛，去看了 0+5a 的 blog，又意識到應該回來做事才對，就開始寫這篇記錄ㄌ。

Day -291 -- 2022.12.20

Day -290 -- 2022.12.21

Day -289 -- 2022.12.22

本來打算要通霄弄完 SA 作業，但是直到凌晨兩點多我突然意識到今天是禮拜四，有早八體育課要上，就計畫著先睡到 6:30 再說。

不過顯然，我太懶了，根本不會只睡四小時在這麼冷的天氣爬起來，甚至睡到了 8:20 才下床。

趕緊洗漱完，騎著 Youbike 2.0 就往高爾夫球場去。但是意外就在短短的 20 分鐘之後來臨：金山寺站的 2.0 被禁用了不能停！懷著「放棄了吧」的想法，我繼續騎著車按照地圖上最近的 2.0 站的方向前行，又花了 20 分鐘的時間。因為那邊也沒有 1.0 的車了，當我走回到高爾夫球場的時候已經是 9:58 了，只好直接搭紅巴回學校。

[此處應有圖片]

不知道為什麼今天的紅巴是紫色的，途中有好多人都在問到底是哪一班，但是司機好像不知道他開的是紫色的 (?)

回到宿舍之後繼續寫 SA 作業，上次的進度是把虛擬機搞爛了連不到網路，經過了一個半小時的搶修，終究還是連不到網路，看來在下次作業之前要全部重做ㄌ。

在回顧上一次的作戰紀錄的時候意外發現其實 HW3 有交出一個 20 分的 submission，但是被後來的 submission 蓋掉了所以沒拿到分數 QQ

下午一點多去一餐吃炒泡麵，吃完大約兩點半就直接回宿舍睡覺，睡醒後已經是六點了，遂前往女二餐吃自助餐。久違的遇到了高中同學王さん，發現他最近也過的不太順利 ._.

晚上耍個廢之後就去玩 Terraria 了。

Day -288 -- 2022.12.23

玩到大約凌晨兩點之後就去 Youtube 找直播來聽。

來推一個可愛ㄉ VTuber 白玖ウタノ～從初配信之前意外滑到發現翻唱 ANIMA 很好聽就訂閱了，之後連開了幾次雜談跟歌回都碰巧有跟到，短短兩周的時間訂閱數已經從 1k 增長到 11k 了！

因為 ISSC 要我用 Word 給題目，但我只會用 Markdown 跟 LaTeX，於是為了研究怎麼裝字體，還有為了各種麻煩的排版問題弄了超級久。

感覺 LaTeX 跟 Word 對於初見都非常不友好，Markdown 相比之下實在好太多了。但 LaTeX 的模板給出來之後就很容易直接在上面做事，而 Word 就算有模板也很容易不小心動到；再來就是 google 到資訊的多寡差距太大了（也可能是我對 Word 相關論壇不瞭解），想知道 LaTeX 怎麼設定只要把指令打出來通常就能在 LaTeX 的 Stack Overflow 上找到，但是想找到 Word 的用法爬文爬了幾個小時還是只找到文不對題的東西。

上午七點半點決定要去睡覺，直到下午一點半醒來之後去吃新竹美食，吃完則繼續排版工作。

即將到聖誕節了，今天划手機幾乎都是跟聖誕節有關的貼文。因為感興趣就稍微查了一下 12 Days of Christmas 是哪些天，得到的結果是聖誕節 12.25 到隔年的主顯節 (Epiphany) 前一天 01.05 這 12 天。

反正這學期基本上是都炸了，不如就想想 12.25 到 01.05 要怎麼度過這「12 Days of Christmas」吧！第一個想法是每天 virtual 一場 OI 或 ICPC，但是段考畢竟還是要考，於是計畫暫時變成「前五天打 CF / AT、後七天打 JOISC + 三場咚咚」的感覺，希望有辦法做到 OwO

突然想到二手版上有人在徵機率作業教學，我才意識到好像又要有作業了。一陣子沒開 E3 了，發現 25 號下午要寫完機率 HW4，而 HW3 已經不知不覺間過去了。比起每次看著作業 deadline 一個接一個的從身邊飛過去，直接忽略他好像比較不會有罪惡感耶。

下禮拜包含體育有 6 科段考分別在一二三四四四，我要讀哪幾科才不會被二一啊。

直到晚上八點半終於把版排完了！到時候在出題心得那邊再把題目丟出來吧～套一個冰箱梗：

我每次望向題本，不是希望我學到的新功能可以利用在題本上，而是希望我對成品的期待降低到我可以把現在這份交差了事。

明天早上還要趕去台中開會，其實我到現在都不知道出這個到底能不能賺錢，又或是能賺多少錢。說到賺錢，我覺得夠好的題目（像是 IOI Seats、Aliens 等等）應該有 20k+ 的價值，因為在上面花的心力絕對不只有一個人的一兩百個小時；而一般的難題大約是 4k、中等題 2.5k、簡單題 1.5k 吧。當然這是指出題人認真想題目生題目的狀況，如果是隨便從別的地方偷題，或是官解寫爛、亂生測資、題意不清等等問題那麼該題的價值就會不斷下降……

說實話這幾年 ISSC 的題目讓我很驚訝，明明感覺上這是高中生一年中的大比賽之一，題目品質卻每況愈下。從 2019 年還有考察各種算法，到 2020 跟 2021 的時候題目各種卻出包、感覺幾乎變成手速大賽，今年的題目更是只能用黑人問號來形容。理論上如果有錢可賺一定會有許多有打比賽的人願意出題的吧？

順帶一題，Codeforces 一年一度的 magic 又可以使用了，目前我是偽裝成 International Master 的顏色 --- 橘色。沒錯，我從橘色變成橘色了 (?)

[此處應有圖片]

Day -287 -- 2022.12.24 (2022 ISSC)

今年當上了 ISSC 工人才意識到這個比賽是多麼落後 QQ

  • 11:00

本來是 11:00 要開評審會議，但是因為拉肚子導致出發時間更晚，直到 11:50 左右才抵達 ST039。

  • 11:45

到場之後先看到題本的排版消失了，等寬字體不見，還有 pJ 的範測被複製了一份塞到 pI 上 (?)

因為我 pH 的驗題解爛掉了所以在嘗試修它，之後突然想起 pJ 有 checker 要放上去，試了很久終於發現是 testlib.h 要放 domjudge 專用的版本才有效。

  • 13:10

快速吃過午餐之後就到了測機時間，聽旺陽學長跟掛長說前一天收到的測試賽 pC 沒有測資是臨時生的，而今天發現 pA 跟 pB 的測資也都是爛的，只好臨時手生一些測資。其中 pB 測資甚至只有範例測資 OwO

  • 14:10

看到工人開始打紅色以外的氣球，一問之下發現因為溝通不良導致工人以為只要打紅色的就好。最後決定把 pA 跟 pC 的顏色換掉，讓最簡單的 pC 變成紅色。

  • 14:30

比賽開始了，一片混亂。

有三個隊伍共用到別人的帳號，導致會有一些隊伍共用 submission 的成績，好在把全部人的隊伍都重新檢視一遍之後暫時解決掉這個問題，不過已經造成的影響只能透過賽後手動加扣分來解決了 QQ

場內好像沒有電子檔題本可以用，Judge 裡也沒有提供可以下載的範例測資，參賽者們要面對的是兩題有超長範例的 pH、pI（pH 甚至範例測資足足就佔了一頁半）。

  • 15:00

我發現比賽時間設定成三個小時而官網上是寫 2.5 小時，不過因為先前紙本說明上寫的也是三小時，我們討論了一下決定維持原樣。

結果後來又有人進來吵到底要不要維持三小時 ._.

  • 15:15

有人提問 pA 輸入測資結尾有沒有空白，雖然沒有但是有 \r\n，可惜他沒問到點所以我就放棄回覆「測資以 \r\n 結尾」了。

  • 15:37

終於有一隊 (pixelcat) 上傳了 pJ，可惜它的輸出連範例都過不了，幫 QQ

  • 16:05

最後還是決定要把行尾的 \r 拿掉並 rejudge，結果是「小象幫」超越了「隊伍名稱」早一分鐘拿到了首殺。

  • 16:20

發現 pA 限制有錯，每筆測資的空格數可能會超過 100 個。一開始先發了「空格數有誤」的 clarification，後來改成把不符合格式的兩筆測資刪掉再 rejudge。

  • 17:00

封版ㄌ，我的題目怎麼都變成防破台題了啦 QQ

  • 17:13

becaido 起飛。

  • 17:20

becaido 跟蝸牛同時在 170 min 過 pJ，雖然是蝸牛拿到首殺但 becaido 仍然是大一位。

  • 17:30

比賽結束，準備頒獎。

  • 18:xx

結束之後跟教授們吃了一間看起來就很貴的餐廳。感覺我就很不適合吃這種東西，每次喜宴感覺都是去吃生菜的 ._.

因為到了隔年的五月我才想起來要把東西丟上去，所以就寫到這裡吧 OAO。