比賽前要把背包放在一個房間, 中途看見只有 9 種氣球, 代表只有 9 題, 即是很有可能要以罰時決勝負, 對我們有點不利, 因為我們的罰時一向都不是太好
其實比賽在 9:15 便開始了, 比去年準時很多. 我負責分題目, 感覺上沒有甚麼頹題. 不久後 whh 上 A, submit 後得到 WA.. 此時己經有些燥, 在開始便已經落後人. 幸好第 2 棍便過掉
A - tui (whh, 19 + 1WA)
中途 ff 告訴我 E 的題意, 我一看便知道是一般圖匹配, 這時還覺得挺開心, 因為有武器而且我覺得不會很多隊伍能做到. 不過由於代碼很長, 決定先放在一邊, 和 whh 研究 I, 很快發現用多一支 vector 一定不會使答案變差, 所以 vector 的次序並不重要, 便猜想可以把 vector flip 至第1, 2 象限再處理, 不過不是很確定, 所以交給 ff 和 whh 處理, 我則處理 G - string 的題目, 很快便想到可以用 suffix array (其實用 kmp 便可以), 於是便啪啪啪打武器, 中途和 ff 交替讓他做 H. 寫好 G 後 submit, 返回 WA, 不久後 ff 的 H 也 WA 了, 很差的開局. 約 15 分鐘後發現一些 for loop initilize value 寫錯了, 此時 ff 的 H 也過了
H - dp (ff, 67 + 1WA)
G - suffix array (gg, 74 + 1WA + 1RTE)
此時完全沒有興奮的感覺, 因為很多大學己經拋離我們 (台大好像己經 5+ 題). 此時 ff 和 whh 又沒有其它題目可做, 於是便打 general graph matching 的武器, 其中一行代碼是 g[i][j] = g[i][j] = -1, (馬後炮) 使我有點懷疑武器的可信度.. 不過還是要打, 順利過 sample, submit 後得到 TLE, 便給 ff 做 F (shortest path?) 和給 whh 做 I, 我則把60多行的 code 印出來做人肉 diff..
之後便是差不多一小時的空白, 我的 E 完全找不到 bug, 他們的 F, I 也嚴重卡題的情況 (加起來 WA 了 5 次), 而我隨便 gen 了一個大 case 發現會在一些 do{}while() loop 中 loop 死, 但又找不到 bug, 使我十分焦燥. 大約過了一半的時侯 ff 終於過了 F, 總算有些進展...
F - shortest path (ff, 166 + 2WA)
終於 4 題, 但罰時是在同題數中最高的. 我們的分工是: whh 做 I, ff 做 C, 我則做 B - 在去年的 training 中見過類似的, 做法十分麻煩, 是 segment 內嵌 BIT, 如果之前沒做過的話我也懷疑我寫不出.. 此時腦袋己經十分疲累, 但幸好是第 2 次寫, 故寫得頗順利, 提交卻得到 RE, whh 的 I 也繼續 WA, 愈來愈令人焦急.. 幸好 ff 的 C 一棍過了, 十分慶幸不用 debug C 這種題呢
C - evaluate expression + randomize (ff, 227)
不久發現 lower_bound() 有些位 handle 錯了, 改之, 終於過了 B, 鬆一口氣
B - segment tree + BIT (gg, 234 + 1RTE + 1WA)
之後看之前看錯題目的 D, 認真想了一想後覺得不太難, 便接著做, 是比較像"OI" style 的題目, 當然由我解決掉~
D - adhoc (gg, 260)
這時侯我們仍然有希望可以全清的, 因為可能 E 只是一個小 bug, 加上 I 有很多隊做到, 在剩下的 40mins 我們應該也可以做到. 但愈試 E, 愈是開始覺得是武器出錯.. 他們的 I 好像也試了另一個 approach, 但最終也是過不了.
完場後十分灰, 也不想知道自己的 ranking, 在發現 E 竟然可以用 bipartite matching 水過後更加燥.. 隨手畫一個 case 都可以炒掉 bipartite matching, 怪不得這麼多隊伍過了..
其實以我們的實力 9 題是可能的, 雖然開局很差, 但其實還是有很多機會可以全清 (例如放棄 general graph matching 的武器嘗試水, I 也應該更早放棄 iteration 的 greedy 算法), 不過還是輸了, 感覺十分差
今次分題目不是分得很好, 不過有數題也是有 (x, y) 的坐標 input, 但其實全部都不是"真正"的 geom 來的; 不過對台大這種 "三名高手型" 來說可能沒有甚麼差別吧
今次完全浪費了 whh 的戰力, 大部份時間都在試 I 的錯誤做法 (greedy flip vector), 希望 fuzhou 的題目可以讓 whh 發揮吧
No comments:
Post a Comment