校內 ICPC 模擬賽 心得

模擬賽題目：2015 ICPC Singapore

連結：https://open.kattis.com/contests/niih2v

之前的我們：我們打競程打健康的。
現在的我們：為了出國一起捨棄GPA OwO

心得

天使宗哲設錯日期，設到明天晚上，調整後延後10分鐘考www
比賽時間：2020/11/05 18:10~23:10

開頭小差曲：我們到了一間不是電腦教室的地方上機，原齊想用vim，文元想用sublime，但我的筆電只有vim，所以比賽開始後文元現場直接裝，sad。

一開場我先看pC，第一次知道ICPC的題敘超可怕的長，裡面的劇情用詞超強的 <- (這不是重點XD)

pC: n表示接下來有n個食譜，每個食譜有m個數字表示combine在一起，必定由上往下的食譜進行合併，合併過後的數字不能單獨跟他沒有合併過的合併，然後合併的條件是

  1. 合併過不得單獨跟沒合併過的合併
  2. 合併過的可以一起跟沒有合併過的合併
  3. 呈2，或是可以一起跟合併過的一起合併

看完後跟文元(SAD)、原齊說我的想法，我們同時表示：「裸的DSU啊！」，然後交給DSU刻超快的SAD刻。

中間小插曲：文元突然轉不過來第3點怎麼刻，我就說：沒做過的砍掉，每一個dsu的size總和一定會等於剩下的。C就這樣被首殺掉了。

然後我看pE，看到一半後被抓去想pI，就三種字母，給分別三種的數量，將其排列但相同字母的不能相鄰，我想了一下，資芽算法班貌似在DP那章有紅藍綠著色問題，但我又忘了怎麼轉移，現場推我腦袋燒雞，交給原齊後他也宣告放棄，於是就跟他們說pE想法。

我只說了一半(誰叫我只看一半ㄎㄎ)，順便他們跟我解釋pF，後來發現pE完全就是模擬題(模擬比賽算penalty)(而且一堆人AC了)，他們趕緊刻完AC後交給我寫pF。

pF: 每隻細菌都有自己適合的[U,L]，表示溫度範圍，然候有n隻細菌，每個保溫箱有固定的溫度，求最少需要多少保溫箱。

其實pF沒有很難，但一開始原齊想法錯了導致送上去兩次WA，後來他製造了奇怪的測資把自己的想法ban掉OwO，我就重刻。由於我沒有好好維護while導致某些比較大的測資會infinite loop，我又WA了兩次，而且我的code超級不clean，於是原齊打算重刻，果然刻完送上去AC了。

這讓我想起打R6時天兆常跟我說：「不會玩女鬼就不要玩; 不會玩大盾就不要玩！」我現在想：「不會刻while就……好好維護啊！然後code乾淨一點！」(我真是欠譴責OwO)

後來我們pG想不出最優解，原本想說是greedy，但文元說dp才對，可是沒想法。
pG題序如下：
有一個stack，裡面有一排數字，逐一取出分堆。
分堆定義：

  1. 取出後可以加起前一個並組成一堆
  2. 依序以左至右的每堆數量必須為非嚴格遞增
  3. 呈1.取出後可以選擇併入前一堆，或是自立一堆
    題目所求：最多分幾堆

最後我們21:45就先離場了，總共打了3hr35m。

總之，ICPC加油啦！我會好好練 clean code的 QAQ