CodeForces Contest #53

題目
Scoreboard

A - Square Earth?
看了兩次才看明題目, 我的做法是給每一點一個label, 最後兩點相減
看到很多人都用分case的方法, 但不少人寫漏了case, 因此得到了不少hacking 分:D


B - Martian Architecture
我的做法是先找出每一點的高度, 對於每一個update (a,b,c), 可寫成

add[a]+=c;
chg[a]++;
add[b+1]-=c+a-b;
chg[b]--;

之後traverse一次array便可求出每一點的高度

Submit 第一次錯了, 但又找不到bug, 用了5分鐘才發現是把所有query的答案加起而不是續個output...
Hacking 時發現有 O(QM) 的做法, 十分簡潔


C - Array
數increasing+decreasing sequence的數目, 由於想不到公式, 因此先找出細case的答案, 然後當然是OEIS :D
得出公式是 C(2n,n)-n
老老實實, 答案要mod P, 因此要找 n! 的 inverse, 其實上了CSCI2110 才懂做的
後來發現每個dp[n][k]都對應 C(n+k-1,n), 總算接受了條公式


D - Journey
其實是問所有pair的total path length
對於每點 (X,Y), 計算在 total path 中 X 和 Y 分別被加和減了多少次
但有些path 不是走 shortest path 的, 因此要對每條這樣的 path +2
很可惜地, 我漏數了一些 case, 因此在 system test 中 fail 了

最後由於有7個hacking 和很多人也 fail 了 D (pretest 很弱), 離奇地排到第 15
也升了紅色:D