NCPC 2012

NCPC - Nordic Collegiate Programming Contest, 北歐四國之間的比賽, 亦是 NWERC 的預賽
這個比賽任何人都可以參加, 即使不是 KTH 學生也可以
雖然是 team match, 不過因為未認識其它人, 加上可以挑戰一下, 所以決定單挑

Scoreboard: https://ncpc12.contest.scrool.se/standings/?filter=1

=== 比賽過程 ===

A - compare 2 條 string 的 length, 超級大水題
D - 我用 dp 做, 其實有更簡單的做法, 不過沒有時間想得深入, 反正 coding 的時間不會差太多
J - dp on tree, 錯了一棍; 又其實有簡單的 greedy, 不過不明顯
C - maintain median, HKOJ 做過
B - 試了幾個 case 確定和 inversions 有關, 果斷 code
G - geometry, 看下去有點難, 不過仔細想後便看出重點, 錯了一棍
K - 2-SAT

之後看 F, 有點像 undirected postman 的變種, |V| 很小
比賽提供午餐, 到出面的 corridor 一邊吃一邊想
undirected chinese postman 可以用 weighted general graph matching 解之, 不過 |V| 很小, 應該可以用暴力做這一步
覺得這個方向正確, 吃完後便開始寫

錯了一棍後發現 disconnected 的 case 有問題, 便想辦法 fix
搞了一大輪後還是過不到, 於是看其它題目:
E - shortest path, 同時要 minimize turining angle 之類
I - 有點煩膠的 searching
J - 行李帶

E 好像很難 (事後發現看錯重點, 原來是要 minimize max 而不是 minimize sum)
I, J 都有機會
開始寫 I, 有點煩, 幸好一棍過了, 剩下大半小時
然後想 J, 應該是把有問題的 time interval 起出來
不過寫來寫去也有問題, 到最後 15 mins 時放棄再去改改 F 的 code 怒隊, 最後也是 WA

=== 完場 ===

最後得到第二, 輸了給 Omogen Heap
發現原來第一和第三都是由 今年瑞典 IOI team 組成的 [Shock]
最勁那個今年 IOI 金獎, 又有玩 IMO, 今日比賽單挑第三
餘下三人組成一 team, 今日比賽第一
現在的中學生真屈機 [adore]

發現 E 看錯了, 很可惜, 如果沒看錯的話一定做到
單挑 5hr ICPC 好像還是第一次, 和 team 的打法很不同:
- 只有 1 個人看題目, 要快速選題, 最好是參巧 scoreboard
- Coding 準碓度要求高, 因為不能一邊 debug 一邊由 teammate 做另一條
- 卡題會很嚴重
- 看錯題目機會增加
- 最後 2hr 會很累, 是時侯訓練體能嗎?