Coding Phase
一入房, 沒見到甚麼勁人
分數的分佈是 250 500 900
看完250, 由於 maxDen 十分小, 因此立即想到窮舉 A,B
搞左一輪, 慢慢的解決掉 (203)
之後不知為甚麼想先開 900, 看完題目後感覺不難
但有想過 900 不會這麼簡單, 懷疑佢 valid 的 range 並不是 [x,INF) 的 form, 於是寫左個 program generate test case 試, 得出來的結果又好像 work
又見很多人 submit 了 900, 於是便開始 code, 過程十分順利, 幾乎沒有錯, 過sample便submit了 (636)
由於做到900 心情很好, 便滿有希望地開 500
看完題目第一件想到的是 greedy 唔 work !
呃..
之後朝著 dp 的方向諗, 又真係好似可以用 dp
Define dp[i][left][right] = 第i個有left influence傳去左面和right influence 傳去右面
由於 500+500/2+500/4+... <1000, 所以大約是 N*10002
看起來很合理, 剩下15-20分鐘, 便很興奮地揼.. 啪啪啪
很順利的把 sample 都通過了, 在完場前3mins submit
Challenging Phase
做500的時侯已經想到很多人會用greedy做500!
所以 intermission 時已經出定 greedy 的 exceptional case
一開
果然有不少一看便知道不正確的方法, 不過估唔到連greedy都有好多種.. 有對 influence greedy 的, 有對影響人數 greedy 的, 有雙重 greedy 的.. 真係諗得出都有
看到一個用"double greedy"的, 睇明佢段 code 再諗左個反例, 由於做左3題, 因此當時很勇敢的 cha 下去
Challenge success
+50! 還想如果3題全過再加上 challenge 的分數就是一場完美的 SRM 了
可是, 突然發現自己的500被cha掉了, 灰哂
不過仍然無阻繼續嘗試cha別人的 code
差不多夠鐘時看到一個肯定錯的, 但又不太明白他在幹甚麼, 於是gen左一個大數據去cha佢, 可惜失敗, -25
最後以剩加分25結束
System test
看divison summary, 很多人都提交了500級900, 其中900的submission比500還要多
而且自己也莫明奇妙的入了頭100(好似係)
system test 開始後不久, 就發覺唔係好妥.. 900果行放眼盡是 failed system test
再看看自己也是同一命運, 但很幸運地有+25 的優勢 (突然變得非常重要, 因為突然大剖份參賽者只pass了250), 居然還可擠進頭100
Rating 的升幅也是近數月來最大的, 而且創了新高
很莫明奇妙的一次SRM
No comments:
Post a Comment