Codeforces Round #301 (Div. 2)

經過GCJ的失敗後, 慢慢調整腳步回復正常

前幾天在公司看到了這場只有Div. 2 的Round

就跑去打了

話說原本的計劃是半休閒地打的

但這場的性質, 我認為是較陷阱型, 就是那些讓你不斷HACK人和被HACK的題目

本身題目能學習到的也不少, 但沒有前幾場那麼多

可能這場要真正參加才行吧...

我其實也是Virtual Participate的

但無奈在題B 的Implementation上卡了很久, 也被人發現我在做冗員就開始給我工作了

結果還是完了Virtual Participation之後當練習地慢慢打

題目方面除了是陷阱型, 題C我認為是題目1999...我理解完全錯誤 導至一直想不通

也不明白為何會這麼多人AC...下面再詳說吧~ 重點是題C-E (Div,1 的頹題) 學習到的東東

Codeforces Round #301 (Div. 2)

題目: http://codeforces.com/contest/540/problems

A: (Math, Greedy)

這題在老細的壓力下完成, 直接地說, 我是看Sample猜題目直接做直接交一棍AC...

題目就是給了兩個平時單車用的密碼鎖的密碼, 問你從第一個轉到第二個最少要多少下

就是每個digit greedy地看順時針轉還是逆時針轉較好了

B: (Math, Greedy)

沒想到這題卡我那麼久 害我WA了很多棍...

其實題目沒什麼好想的, 題目說明 n 個數字裡面給你 k 個 (n肯定是odd number)

然後問你能否把剩下的 n-k 個數字填上, such that SUM <= X && Median >= Y

思路大約就是Greedy地填, 由於想SUM<=X, 我們能填最少的都填最少 (i,e, 1)

但又想Median >= Y, 所以把n 個數字排序後,(假設已填好)  頭 n/2  個數字可以是1

中間那個數字及之後的直接填Y

這樣肯定SUM是最少的同時, MEDIAN 又 >= Y, 最後查一查SUM是否真的 <= X就好了

問題來了, 這題好多Case需要分析考慮...

例如可能給你的 k 個數字全部都 < Y, 而 k > n/2, 則答案直接是 -1

還有很多其它可能性...

簡單來說, 思路是這樣做的了, 但很多Case如果沒考慮就很易WA / 被Hack...

這題做Div. 2 的B 也算是有點難了 我個人認為 即場玩的話應該很多人都是Hack這一題來得分吧 以下是很難看的AC Code:

#include<bits/stdc++.h>
using namespace std;

int n,k,p,x,y,p1=0,p2=0, sum = 0;
vector<int> ans;
int main(){
    scanf("%d%d%d%d%d", &n, &k, &p, &x, &y);
    for(int i=0,a; i<k; i++){
        scanf("%d", &a); 
        sum += a;
        if(a < y) p1++; else p2++;
    }
    if(p1 > n/2) printf("-1\n");
    else{
        for(int i=0; i<min(n/2 - p1, n-k); i++) { ans.push_back(1); sum ++; }
        for(int i=0; i<n/2 - p2 + 1; i++) { ans.push_back(y); sum += y;}
        
        if(sum <= x) for(int i=0; i<ans.size(); i++) printf("%d ", ans[i]);
        else printf("-1\n");
    }
    return 0;
}

C: (Graph)

題目自己看, 看完再來看是我腦殘還是它語癌

題目給了一個 N*M 的Grid, 是典型用BFS 問由 S 能不能到 T 的問題

題目中說明每一格如果經過了一次, 會有裂痕, 第二次再經過就會掉下去了

本身格子有些已經裂了, 而S 是肯定裂的 (這個對Implement上有些影響)

問能否由S 到 T?

好了 我一直到不久前的理解是....我看到是 side view, 也就是說如果一格裂了

再到那一格, 玩家會直接掉去下面一格,  要是下面一格也裂了,就再掉...這樣

這樣的話問題就很複雜了, DFS/ BFS那種沒什麼次序的Transverse好像不行, 因為先走那一格都會影響到往後所有path...不能隨便走走走一直走到終點

反正就是沒什麼Idea

搞了很久, 甚至看了Editorial也不明白....到最後..真相是

題目的Grid 是Top View...所謂掉下去是...該格不能再走而已...

這樣就很簡單了..變回普通的BFS問題

但也沒這麼直接

首先由於題目要求的是走到T 那一格然後掉下去

所以如果T 本身是裂的, 那只要有Path到達就好了

如果T 本身沒裂, 則它旁邊最少要有 2個 "沒裂的格子"

(數"沒裂的格子"時要數上起點 S, 即使 S 已經裂了, 但如果它是T 的鄰居, 可以直接走去T使T變裂)

另外 S = T 也是Special Case, 處理方法是看 "沒裂的格子(不算S)" 是否 >= 1

基本上剩下的就是用BFS 看有沒有PATH能從S 到T 

當中注意的是每格不是用 isVisit[] 來看能不能走, 是直接看是不是裂的 (或者終點)

要是裂的直接當不能走, 要是能走的, 走完 (把點PUSH入QUEUE) 後 把該格變裂

#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,tx,ty;
char w[505][505];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
queue< pair<int,int> > q;
bool bfs(int cx, int cy){
    q.push({cx, cy});
    while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        if(x == tx && y == ty) return true;
        q.pop();
        for(int i=0; i<4; i++){
            int nx = x+dx[i], ny = y+dy[i];
            if(w[nx][ny] == '.' || (nx==tx && ny==ty)) {
                q.push({nx,ny}); w[nx][ny] = 'X';
            }
        }
    }
    return false;
}

int main(){
    scanf("%d%d", &n,&m);
    int cnt = 0;
    for(int i=1; i<=n;i++){
        getchar();
        for(int j=1; j<=m ;j++) w[i][j] = getchar();
    }
    scanf("%d%d%d%d", &sx,&sy,&tx,&ty);
    for(int i=0; i<4; i++) if(w[tx+dx[i]][ty+dy[i]] == '.' || (tx+dx[i] == sx && ty+dy[i]==sy)) cnt++;

    if(sx == tx && sy == ty){
        puts(cnt >= 1? "YES":"NO");
        return 0;
    }
    if(w[tx][ty] == '.' && cnt <= 1) { puts("NO\n"); return 0;}

    if(bfs(sx,sy)) puts("YES");
    else puts("NO");
    return 0;
}

這題聽完也會覺得思路也是直接但又是很多Case要Handle要考慮, 又一題Hacking 爆分的題目...

還好這場沒參加...

D: (Math, DP, Probability)

這題學到東西了

首先題目很直接

是一個猜包剪dup的遊戲

由於題目數據, 基本直接就想到是 dp(x,y,z) 的形式了

formula也很快寫出來了

但反而是每一個Event的Probability有點難數

打和的情況也在想怎樣Handle的時候

最後看Editorial發現我一直理解 "equiprobably" 都有點錯誤

題目中: At some moments of time two random individuals meet (all pairs of individuals can meet equiprobably)

開始我的想法是每一種出現的機會是 1/3...

但它用的字眼是 "all pairs of individuals" 總覺得意思不一樣  也好像不用搞得很複雜
(如果是原本的想法, 數 species A 的數目 再算 n 隻入面抽中它們其中一隻的probability 就是 pairs of individual中 會抽到A 的機率....總之很複雜...這也令我更肯定我一定要重溫 (重新學習) Probability了...)

總之原來不用簡單複雜化, 又用nCr 又什麼的

題目說什麼是equiprobably, 就直接數那個東西的數目

在這題中是 "all pairs of individuals"

那就直接數啊... 所有可能性 就是 N =  r*s + s*p * p*r   <---s,r,p 是剪, dup, 石頭的數目

然後假設那一pair是 rock 跟scissor, 就是 r*s / N 啊...

剪刀死了 就把數目減一再DP啊...

注意這兒是直接沒有數打和的情況, 不論分子分母都沒有數!

我不知有沒有term, 但我形容的是, 在它考慮 "probability space"時已經直接排除打和了..很聰明正確的做法

所以就是這樣了 

設 DP(R,S,P) := probability to make the island have R rocks, S scissors, P papers left

這題用Top-Down絕對更易做

 int rp = (r+1)*s + s*p + (r+1)*p;
 int rs = r*(s+1) + (s+1)*p + r*p;
 int sp = r*s + s*(p+1) + r*(p+1);

 if(rp)
     dp[r][s][p] = (r+1)*p*1.0 / rp * DP(r+1,s,p) ;
 if(rs)
     dp[r][s][p] += 1.0*r*(s+1)/rs * DP(r,s+1,p); 
 if(sp)
     dp[r][s][p] += 1.0*s*(p+1)/sp * DP(r,s,p+1);
 return dp[r][s][p];

可能會有一種物種已經全死光了, 所以要查一下 if(rp), if(rs)等等 看是不是有可能出現這個組合

那麼石頭會贏的Probability

就是 Sum DP(i, 0, 0)  

另外2個會贏的Probability也是這樣做, 下面是一棍AC的Code
(這題沒什麼陷阱, 是想到就做到的題目, 我認為C是更難的...)

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int R,S,P;
double dp[105][105][105] = {0};

double DP(int r, int s, int p){
    if(r > R || s > S || p > P) return 0;
    if(dp[r][s][p]) return dp[r][s][p];
    
    int rp = (r+1)*s + s*p + (r+1)*p;
    int rs = r*(s+1) + (s+1)*p + r*p;
    int sp = r*s + s*(p+1) + r*(p+1);

    if(rp)
        dp[r][s][p] = (r+1)*p*1.0 / rp * DP(r+1,s,p) ;
    if(rs)
        dp[r][s][p] += 1.0*r*(s+1)/rs * DP(r,s+1,p); 
    if(sp)
        dp[r][s][p] += 1.0*s*(p+1)/sp * DP(r,s,p+1);
    return dp[r][s][p];
}

int main(){
    scanf("%d%d%d", &R, &S, &P);
    dp[R][S][P] = 1;
    double a1,a2,a3;
    a1=a2=a3 = 0;
    for(int i=1; i<=R; i++) a1 += DP(i,0,0);
    for(int i=1; i<=S; i++) a2 += DP(0,i,0);
    for(int i=1; i<=P; i++) a3 += DP(0,0,i);
    printf("%.12f %.12f %.12f\n", a1,a2,a3);
    return 0;   
}

E: (Binary Indexed Tree, STL, Ad-hoc)

昨天終於最後AC了這一題....雖然也是有一半是靠Editorial啦...

這題新學到的東西不多  倒是應用了不久前學的東西!

就是 用BIT 來Count 一個 Array的 # of Inversions!

這題當然沒這麼簡單, 單單是把位置 map去一個 O10^5)大的array再用這個技巧

已經是又要用STL的Map又要STL的Set (當然可以不用...但反正這些都不是Complexity的Bottleneck就算了)

題目要求的答案可以分開兩部分算:

第一部分就是用這個技巧

我自己卡是卡在第二部分沒想通...現在想就很合道理了:

For 每一對連續受影響(有swap過)的 index, 它們本身的inversion已經用BIT (第一部分算了)

但它們之間 沒Swap過的數字與它們的Inversion(如果有)則沒有算, 這就是第二部分

方法其實很簡單, for 每一個swap過的數字 x ,  找回它原本的index, 數它們之間有多少個數字也是swap過的, 減走它們! 因為這些swap過的數字不論有否跟 x 組成inversion, 它們也已經在BIT那部分受考慮了,  減走它們正正是 "沒被SWAP過的數字" 數量, 這些數字肯定跟 x 會形成inversion.... 找 x 原本的位置可以用Binary Search做

這樣的話總結來說是 O(n lg n)的算法

這題最開心的是, 之前新學的Trick可以派上用場...也算是有真正apply這個技巧的經驗!!

但要是我能改改那些不小心的習慣, 例如 array開小了導至Runtime error 等等.... :o)

這也是這題為什麼多人AC的原因

因為第二部分(我卡的部分) 其實不難想, 主要是要懂用Merge Sort / BIT 去找 # of inversions

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;

int n, bit[200010] = {0};
map<int,int> mp;
set<int> st;
vector<int> swapList, value;

void update(LL x){
    for(; x <200010; x+=(x&-x)) bit[x]++;
}

LL query(LL x){
    LL ret = 0;
    for(; x ; x-= (x&-x)) ret += bit[x];
    return ret;
}

int main(){
    scanf("%d", &n);
    for(int i=0,l,r; i<n; i++){
        scanf("%d%d", &l, &r);
        if(mp[l] == 0) mp[l] = l;
        if(mp[r] == 0) mp[r] = r;
        swap(mp[l], mp[r]);
        st.insert(l); st.insert(r);
    }

    int tmp = 1;
    for(set<int>::iterator it = st.begin(); it!= st.end(); it++){
        swapList.pb(*it); value.pb(mp[*it]); mp[*it] = tmp++;
    }

    LL ans1 = 0, ans2 = 0;
    for(int i=value.size()-1; i>=0; i--){
        int id = mp[value[i]], tt = i;
        ans1 += query(id);
        update(id);
        int pos = lower_bound(swapList.begin(), swapList.end(), value[tt]) - swapList.begin();
        if(pos < tt) swap(pos, tt);
        ans2 += swapList[pos]-swapList[tt] - (pos-tt);

    }
    printf("%I64d\n", ans1+ans2);


    return 0;
}

看看能不能在下星期內也學回GCJ 1B / 1C 的題目吧...要是清掉了就沒什麼累積的東西了~