這是 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，不過比賽就是會有遺憾的。
No comments:
Post a Comment