ACM ICPC 2010 - Kaohsiung 戰記

照舊是由我分題目。這次只有一份題目, 和training的時侯一樣。分好後便設定好vim, gedit等環境, 這次用的是Linux, 加上keyboard十分順手, 令打字速度提升了10%。一開始看到J, 立即發現是很簡單的動態規劃, 便上機了。寫到一半呀暉告訴我A是赤裸裸的最大生成樹, 加上看到不少隊伍過了A, 便先寫A, 秒殺之。

24 min - Problem A - MST (1Y ; GagGuy)

過了後繼續寫J, 過了樣例便提交, 返回WA。此時whh的F可以做, 是很經典的二分圖匹配, 便換他上機。不久, 發現了J的錯處, 改之, 第2個Yes。

37 min - Problem J - DP (2Y ; GagGuy)

過題後呀暉問了我題D的一些東西, 和最近點對有關, 我便告訴他中大一直以來的做法, 便列印whh的F並由呀暉做D。我便隨手拿起G看看, 原來是prufer code, 211才剛學完, 不過不太肯定做法, 便先用樣例來試驗。過了不久, 便傳來呀暉射鵰的聲音。

50 min - Problem D - Closest pair (1Y ; Fai)

此時whh也找到F的錯處了。我便找呀暉討論一下G, 確定了做法。本來我打算寫的, 但是呀暉告訴我B是一條計算幾何的題目, 我想用些時間準備一下, 便很放心的把G交給呀暉。同時, whh的F也過了。

56 min - Problem F - Bipartite matching (1Y ; whh) 

B是一條和判斷相似圖形有關的題目。由於數據很小, 應該可以用很直觀的方法做。於是便先計劃一下怎樣寫。不久, 便傳來第5個Yes。

64 min - Problem G - Prüfer code (1Y ; Fai + GagGuy)

由於頭5條都做得頗順利, 使我們一度在scoreboard上稱霸。此時的分工是由我做B, 呀暉做E - 一條頗麻煩的題目, whh看H - 一條很長的題目。準備了一會後, 我便開始寫B。寫的過程不算順利, 很多細節要處理。因此中途先給呀暉做E。然後就開始卡題了。我的B和呀暉的E都不斷返回WA, 眼見其它大學不斷超前我們, 而我們又沒有題可以過, 使我十分焦急。幸好, 呀暉的E在第3次提交時通過了。

172 min - Problem E - Ad Hoc? (3Y ; Fai)

我繼續做B, 而呀暉和whh聯手看H。H是一條graph題, 但看似不簡單。這時我才發現理解錯了B的題意, 但更改也不算太麻煩。可惜仍是返回WA。此時他們的H想到了做法, 便先給他們寫H, 可惜又返回WA。此時剩下一小時多一點, 已經有不少隊伍9題, 我們又卡了2題, 使我再一次十分著急, 便先出去吃東西冷靜, 並整理了一下思路, 決定換另一種方法寫B。而他們再看一次H後, 發現好像理解錯了, 把題目深化了很多。回來後重新寫B, 並處理了有重點的case, 但仍是WA。幸好, 在封board後18分鐘, 我們的H在更改後通過了。

258 min - Problem H - Shortest Path (2Y ; whh)

剩下40分鐘, 而我又覺得B差一點就能過了, 呀暉的C好像又很有想法, 使我一度想過上9題的希望。接下來的時間都是我和呀暉交替寫B和C, 可惜最後B仍是不能通過, C則不夠時間完成。最後以7題結束, 排名12。

ACM ICPC 2010 - Jakarta 戰記

這是 IsolatE 有史以來最發揮到 teamwork，很認真也很開心的一場 acm。
Scoreboard : http://competition.binus.ac.id/icpc/result/final.html


一開始便夾好了由我分題目，自己分到了數條graph的題目。通常 A 較簡單，但一看 A，怎看也很難，先放下。然後看看 B，二叉樹計數，直覺是動規規劃。這時whh已差不多完成 C。再想了一會 ，whh 便作出了比賽的第一個提交，發現是全場第一個提交，1Y。我接著上機做 B，但再想一想，發現有些地方不清楚，便先給呀暉做 D。然後看到 F，疑似是強連通分支，這時呀暉提交了 D，WA。此時 whh 可以做 I，不久呀暉發現 D 的錯，第2個Yes。緊接著 whh 的 I 也很快 1Y了。輪到我上 F，很熟練的寫出強連通分支，寫完提交，WA。 然後想起SCC收縮後形成的是有向無環圖，我卻當成了樹，很低級的錯誤，修改，第4個Yes。之後呀暉上機寫I，我則看whh給我的E，也是和樹有關的題目，十分合我的口味。一開 始想到了輕重邊割分，但細心想，可以用簡單的 DFS+LCA 代替。不久，呀暉完成 J，提交，WA。在等待列印的時侯，我上機寫 E，由於有武器的關係，很快便完成，過不了樣例，由於未有其它題目可以上機，因此可以很奢侈的輸出訊息除錯。中途呀暉發現 J 的錯，第5個Yes。發現找LCA出錯了，但又找不到是哪裏錯。時間一秒一秋的過去，終於發現打少了一個分號，眼殘了。改回，立即過樣例，提交，1Y，第6個Yes。和whh討論B，呀暉則研究A。B的動態規劃是O(N^3)，應該超時，因此遲遲未敢上機。whh指出總時間應該會是O(N^2) ，於是便開始寫了。寫到一半覺得很多細節，便先讓給呀暉做 A，中途whh 發現可以最後才乘以C(m,n)，把動態規劃降為O(N)! 這時想起武器中有求C(n,r) mod P 的快方法，便很興奮的打下去。這時和上一次過題目差不多一小時了，有點焦急。過樣例，提交，返回RE。和whh一起除錯，同時呀暉提交的 A 也 WA了。這時兩題也卡了，有點危機的感覺。試了一個case，發現迅速RE了。原來理解錯了武器中的參數，立即修改，擔心了一會long long的問題，這時呀暉的 A 也改好了，不久我也提交 B，出現第 7 和第 8 個 Yes。剩下兩題，一題是有點難的數學題，另一題竟是training中見過的AC自動機+DP，但我沒有太大信心可以寫出。這時分工是 whh 和呀暉想 G，我想 H。需然知道 H 解法的大概思想，但很多細節也很麻煩，預計在比賽中做到的可能性不高。不久後便封board了。差不多時侯他們的 G 也可以寫了，呀暉和whh每人負責一部份，不久便完成了。提交，TLE。想辦法優化，再改，再試，第2個TLE。這時大約餘下20分鐘，焦急，再改，再試，再提交。最後，第9個Yes就出現了(293+3)。興奮得跳了起來。最後以9題結束。後來得知冠軍也是9題，就感到有些可惜，如果之前做回training時做不到的那題AC自動機的話，我有信心在半小時內完成 H，不過比賽就是會有遺憾的。