Codeforces Round #286 (Div. 2)

老實說一句, 這場真的不想記下的
因為只做了3題, 然後題目也很難...
但還是有記下的價值的, 其一是因為這場是久違的virtual participate
雖然在公司內走出走入, 還是有很多時間浪費了
但由於這場真的比較難, 大部分人做了3題排名也很前了, 我覺得時間反而不是太大影響就是了..

有見及此, 竟然也拿到全場37名, 有點騙回來的感覺, 因為題D我認為是有可能做到的...
都想了個大概了, 可惜要用上SCC的概念, 我自己不熟悉而已...

Codeforces Round #286 (Div. 2)

題目在此: http://codeforces.com/contest/505/problems

A: (String, Ad-hoc)

題目很簡單, 給定一條String s, 問在任意位置insert 一個字母, 能否變成Palindrome
隨便輸出一個Palindrome就可以了, 要是不行的話就輸出"NA"

就...就是做吧, 但Code下去也是比其它題A難一點就是了...

B: (Graph)

給定一個圖, 可以有multiple edges, 每條edge有一種顏色, 然後給它一堆queries,
每個query問 兩個點 u , v 之間要用相同的顏色直接或間接連起來的話, 有多少種顏色符合?
看題目下面的圖解會更易明白

由於數據小的問題, 就直接DFS就可以了...
有趣的是, 我跑去看Editorial的時候發現Div. 1也有一條完全一樣的題目, 只是數據非常大
然後就已經一點思路都沒有了...果然算法最主要針對的是數據, 不是題目模型...

C: (DP)

題目給了一條number line, 上面只有0 - 30000 的位置, 某些位置上可能有某個數量的寶石
一個人原本站在第 0 點, 他一定要跳去第 L 點, 然後下一次他的移動距離可在(L-1, L, L+1) 3種內選擇, 假設他選了L-1,  再下一次的距離可在 (L-2, L-1, L) 裡面選...如此類推
問直到不能再移動的時候, 他可以獲取到最大限度的寶石數目

很Greedy很DP的感覺吧, 問題是L 最大可以是30000, 位置也有30000,  那麼只要DP State是2D以上, 已經超時 / Memory了...

這題開心的地方在於, 本來的思路是一直跑去想Greedy...
大約是像 "什麼時候會選 -1, 什麼時候會選+1...要是L變成1的話, 那麼以後全部都是1 肯定是最好的吧...." 這樣的
然後就開始想, 會不會是有什麼機關令這個人可以用"很快"的速度, 使他的移動距離變成 1 呢?
反正變成 1 的時候就完了嘛, 之後肯定是全部都移動 1 格, 把所有寶石都拿走
然後發現最快的"下降"速度, 也只是每次移動都 -1...
但在下降期間有可能會skip了一些有寶石的位置, 令答案不是最優...
所以應該不是簡單的Greedy, 不斷選 -1, 直接距離變成1 的方向了...

但DP是死路....這時有點運氣, 不知怎的先是發現題目定下30000這個數字很奇怪
然後再想到之前某一場某一題DP用過的一些技巧...就是把某一個Dimension減少的技巧...
說是技巧, 其實是Observation, 發現到數據只是嚇人的, 實際上不會全部用上, 也就不用開那麼大的Array...這題也是這個道理!

事實上, 考慮一下這個人最多跳多少步會去到不能再移動?
咦? 先假設這個人每次都選擇+1 吧...而他一開始最少的L是1, 發現大約跳240多步, 就會超越30000了 , 也就是跳出Number Line, 沒路了!
同樣的, 考慮他每次都選擇-1, 也是發現他大約跳240多步就會走到盡頭了 (其實這也是上述Greedy地最快令L變成1的結果)
那麼雖然移動距離好像有30000個選擇, 但相對起始狀態L的選擇只有24x+24x ~ 500個!

那麼就易辦了, 來定義DP State:
State(i,j) := 在第 i 點,  相對起始移動距離L的變化為j 時最多收集到的寶石數
Transition很簡單的, 只是每次跳下一個距離時要把實際距離算一下而已

 for(int i=d; i<=30000; i++){
        for(int j=0; j<500;j++){
            if(dp[i][j]!=-1){
                ans = max(ans, dp[i][j]);
                int rd = d+j-250;
                if(i+rd > 0 && i+rd <=30000 && dp[i][j] + v[i+rd] > dp[i+rd][j]) dp[i+rd][j] = dp[i][j]+v[i+rd];
                rd = d+j-250+1;
                if(i+rd > 0 && i+rd <=30000 && j+1<500 && dp[i][j] + v[i+rd] > dp[i+rd][j+1]) dp[i+rd][j+1] = dp[i][j]+v[i+rd];
                rd = d+j-250-1;
                if(i+rd > 0 && i+rd <=30000 && j-1 >=0 && dp[i][j] + v[i+rd] > dp[i+rd][j-1]) dp[i+rd][j-1] = dp[i][j]+v[i+rd];
            }
        }
    }

上面rd 是 real distance,  v[] 是寶石數

這場最開心的是, 在公司走出走入的情況下, 還能在比賽時間內 A-C都一棍過有不錯的排名...
還算是這樣了吧


順帶一題, 題E沒有看題目, 題D如之前說的, 是有SCC概念的題目
而且一定要用上Topological Sort, 但詳情就不清楚了, 也沒動力去研究了...這陣子有點心散
(其實是想花點時間跑去玩Unity跟Maya)