未能入圍!
1242 | real | 56 | 2:06:19 | 16:22 | -- 1 wrong try | -- | -- | 1:35:29 1 wrong try | 2:02:19 |
但,這年度的賽事還是應該記下來...
今場比賽 - 粗心 + 疲累
回顧整場比賽
0) 對,這場比賽的題目不太難
1) 如果 C 的 recurrence 沒有犯那個錯誤,多數能夠空出 >1 小時的時間去解決 B
(不過,以今場的狀態,大有可能在 Large case 栽在 overflow 手上...)
2) 如果 A 沒有犯那個低級錯誤,那這次比賽我就水過了...
(死了的原因,可能是 Submission Time 是 20:36 吧... 哈哈...)
1) + 2) 的「如果」都沒有發生... 可想而之今次的 粗心 或 狀態 都太差了...
就是題目都懂做,偏偏要犯的錯誤都犯了...
題A 做得比較笨
居然走去寫了樹
不過也不是寫了很久...
而且 small input 也通過了...
然後就趕快去下載 large input
在本機跑了一下... Runtime error ?
原來是 node 數目的上限想錯了...
debug了一下,消除了 RTE
看了頭 3 set data,貌似沒有問題
就 submit,趕快往下一題
── 但是,在 debug 時,我忘了在另一個相應的位置更改變數的值...
所以 large data set 就這樣掛了...
然後到 題B
看了一看,有貪心的感覺
不過想了想,算法沒有即時想出來
就先去看 C
──
不不不... 貪心 和 DP 很難比較
不過 題B 應該是無論如何都可以在 contest time 時限內想出來的
只是,我沒有想到,我後來被看起來應該不太難的 題C 卡住了好久、好久... ...
然後因為「既然投放了那麼多時間,就應該把它先解出來」
看完題 C
想了一想,是 DP + Counting 吧
用紙筆畫了 sample test case
發現可以在 set 的 cardinality 及 最大元素 做 DP:
DP[NUM][MAX] := 有 NUM 個元素 及 最大元素為 MAX 的 set 的數目
DP[1][X] := 1 for X >= 2
狀態轉移要用到 nCr
當 Recurrence 寫好後
代碼沒多久就寫好
而樣例也通過
就下載 small input,提交
Incorrect
── 雖然在 DP[M][N] 往 DP[N][X] 狀態轉移的 edge
我用很大的字體寫下了 (x-n-1) C (n-m-1)
但我居然在 code 的時候寫了
DP[N][X] += (x-n-1) C (n-m-1)
正碓的應該是
DP[N][X] += (x-n-1) C (n-m-1) * DP[M][N] !!
太太太太太太過粗心了...............
在這個情況下
題 C 卡了好久
(本應可以在 ~45分 交解決)
拖延到... 最後忍不住,暴力解決 small input
至後來再過了不知多久(大約是 1:30左右吧)
想猛然想起有一樣好東西叫做 OEIS
我把 small input 提交了... 通過了...
此時看了 scoreboard
X ! 要 56 分以上才有 1000 名之內
此時間時間剩下 大約一小時
既然要解兩題才能晉級
只好繼續上題 C
因為已知 sequence 準時沒錯...
就照著 OEIS 的 recurrence 寫出來
怎料... 一寫就寫了大半個小時...
還不通過 small input
這個時候心情極之煩躁...
── 狀態太差了... 而且又粗心
終於... 在 2:0x 才提交了...
再看 scoreboard
又看了時間
對於 B,應該無能為力了
這個時候
才後悔為甚麼不做 B...
(其實,是因為自己的 C recurrence 那個錯誤消耗了大量時間
(太嚴重,太不可接受了...)
最後,就是落得
A large 沒通過(跟往年一樣- -)
C 通過了
分數跟 第1000名 平手
不過時間上輸了...
所以明天要打 Round 1C 了
沒有留言:
發佈留言