未能入圍！
| 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 了
沒有留言:
發佈留言