読者です 読者をやめる 読者になる 読者になる

ICPC2016 模擬国内予選B

A

日本語を読む

紛失

B

グイッと実装.stringstreamは便利

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

// 頭が整理されてないまま書いた糞コード

int main(){
    string S;
    int a,b,c,d;
    while( cin >> S && S != "#" ){
        cin >> a >> b >> c >> d;

        for(int i = 0 ; i < S.size() ; i++){
            if( S[i] == '/' ) S[i] = ' ';
        }
        vector<string> to;
        stringstream ss(S);
        string t;
        while( ss >> t ){
            string a;
            for( auto c : t ){
                if( '0' <= c && c <= '9' ){
                    a += string(c-'0',' ');
                }else{
                    a += c;
                }
            }
            to.push_back(a);
        }
        swap(to[a-1][b-1],to[c-1][d-1]);
        string ans;
        for( auto l : to ){
            string a = "";
            for(int i = 0 ; i < l.size() ; ){
                if( l[i] == 'b' ) a += 'b', i++;
                else{
                    int j = i;
                    while( j < l.size() and l[j] == ' ' ) j++;
                    a += '0'+j-i;
                    i = j;
                }
            }
            ans += a + "/";
        }
        cout << ans.substr(0,ans.size()-1) << endl;
    }
}

C

座圧してセルの内外判定する気が起きなかったので平面走査

#include <bits/stdc++.h>
using namespace std;
// 計算量は O(N+窓の周長)

int main(){
    int N;
    while( cin >> N && N){
        map<int,vector< pair<int,int> > > seg;
        for(int i = 0 ; i < 50000 ; i++) seg[i] = {};
        
        
        //(1) 窓の入力 & x軸に平行な線分のみをy座標毎に列挙
        int px,py;
        int sx,sy;
        for(int i = 0 ; i < N ; i++){
            int x,y;
            cin >> x >> y;
            x += 20000;
            y += 20000;
            if(i){
                if( y == py ){
                    int a = x;
                    int b = px;
                    if( b < a ) swap(a,b);
                    seg[y].push_back({a,b});
                }
            }else sx = x, sy = y;
            px = x;
            py = y;
        }
        if( sy == py ){
            int a = sx;
            int b = px;
            if( b < a ) swap(a,b);
            seg[sy].push_back({a,b});
        }
        
        // (2) カーテンの入力 & カーテンの範囲を求める
        int x1 = 1e9,x2 = -1e9,y1 = 1e9,y2 = -1e9;
        for(int i = 0 ; i < 4 ; i++){
            int x,y;
            cin >> x >> y;
            x += 20000;
            y += 20000;
            x1 = min(x1,x);
            x2 = max(x2,x);
            y1 = min(y1,y);
            y2 = max(y2,y);
        }
        // 平面走査 & 正直あんましimosしてない
        vector<int> imos(50000);
        long long allans = 0;
        long long innerans = 0;
        long long innertot = 0;
        long long alltot = 0;
        
        for( auto vec : seg){                               
            int y = vec.first;
            for(auto s : vec.second ){
                for(int x = s.first ; x < s.second ; x++){
                    imos[x] ^= 1;
                    // for inner 
                    if( (x1 <= x and x < x2) ){
                        if( imos[x] ) innertot += 1;
                        else innertot -= 1;
                    }
                    // for all
                    if( imos[x] ) alltot += 1;
                    else alltot -= 1;
                }
            }
            // for all
            allans += alltot;
            // for inner
            if( (y1 <= y && y < y2) ){
                innerans += innerans;
            }
        }
        cout << allans - innerans  << endl;
    }
}

D

本質は強連結成分分解なのですが,O(N+M)のアルゴリズム使わなくてもO(N3)のワーシャルフロイドっぽい実装で代替できます(N:頂点数,M:辺数).

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

int main(){
    int N;
    while(cin >> N && N){
        bool g[110][110]={};
        bool g_src[110][110]={};
        int in[110] = {};
        double p[110];
        for(int i = 0 ; i < N ; i++){
            int m;
            cin >> p[i] >> m;
            while(m--){
                int j;
                cin >> j;
                --j;
                g[i][j] = true;
                g_src[i][j] = true;
            }
        }
        
        for(int i = 0 ; i < N ; i++)
            g[i][i] = true;
        for(int i = 0 ; i < N ; i++)
            for(int j = 0 ; j < N ; j++)
                for(int k = 0 ; k < N ; k++)
                    g[j][k] |= g[j][i] & g[i][k];
        bool used[110] = {};
        int color[110] = {};
        double p_to_col[110] = {};
        
        // 強連結成分分解
        for(int i = 0 ; i < N ; i++){
            if( used[i] ) continue;
            double bad = 1.0;
            for(int j = 0 ; j < N ; j++){
                if( used[j] == false and g[i][j] && g[j][i] ){
                    bad *= p[j];
                    used[j] = true;
                    color[j] = i;
                }
            }
            p_to_col[i] = bad;
        }
        // 入次数数える
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < N ; j++){
                if( g_src[i][j] and color[i] != color[j] ){
                    in[j]++;
                }
            }
        }
        
        // 入次数0の頂点のみに着目
        double ans = 1.0;
        for(int i = 0 ; i < N ; i++){
            if( in[i] == 0 and color[i] == i ){
                ans *= 1 - p_to_col[i];
            }
        }
        printf("%.10lf\n",ans);

    }
}

E

よく考えるとdはソートしてよさそうなのでソートすると,布団を片付けることを一切考えなくて良い状態になってハッピー. 頭が悪いので遷移に全ての部分集合をぶち込んでいるが,遷移を工夫すれば計算量落ちます.

#include <bits/stdc++.h>
using namespace std;
// O(M*3^N)

int s[110],d[110];
int N,M;

int dp[110][1<<16];

vector<int> bit[1<<15];
int sum[1<<16];

int dfs(int x,int bit){
    if( x == M ) return 0;
    if( dp[x][bit] != -1 ) return dp[x][bit];

    int ans = 1e9;
    /*for(int i = 0 ; i < (1<<N) ; i++){
        if( bit & i ) continue;
        ans = min(dfs(x+1,bit|i)+abs(sum[i|bit]-d[x]),ans); 
    }*/
    // 上と下は等価
    int sup = ((1<<N)-1)^bit;
    int i = sup;
    do{
        ans = min(dfs(x+1,bit|i)+abs(sum[i|bit]-d[x]),ans);
        i = (i-1)&sup;
    } while( i != sup );
    
    return dp[x][bit] = ans;
}
int main(){
    int t = 0;
    while( cin >> N >> M && N ){
        memset(dp,-1,sizeof(dp));
        for(int i = 0 ; i < N ; i++) cin >> s[i];
        for(int i = 0 ; i < M ; i++) cin >> d[i];
        for(int i = 0 ; i < (1<<N) ; i++){
            int t = 0;
            for(int j = 0 ; j < N ; j++){
                if( i >> j & 1 ){
                    t += s[j];
                }
            }
            sum[i] = t;
        }
        sort(d,d+M);
        cout << dfs(0,0) << endl;


    }
}

G

全てきひろちゃんとa3636takoが考えた.実装しただけ.

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

long long mod = (int)1e9 + 7;

long long b_pow(long long a,long long b){
    return b ? b_pow(a*a%mod,b/2) * (b&1?a:1) % mod : 1;
}

#define CCCCCC 4000000
long long f[4000010];
long long inv[4000010];

long long ncr(long long a,long long b){
    //cout << a << " " << b << endl;
    assert( b <= a );

    return f[a] * inv[a-b] % mod * inv[b] % mod;
}
int main(){

    // N!とN!の逆元を全て求めとく
    f[0] = 1;
    for(int i = 1 ; i <= CCCCCC ; i++)
        f[i] = f[i-1] * i % mod;
    for(int i = 0 ; i <= CCCCCC ; i++)
        inv[i] = b_pow(f[i],mod-2);
        
    int A,B,C,Sx,Sy;
    while( cin >> A >> B >> C >> Sx >> Sy and A+B+C ){
        if( A == 0 and B == 0 ){
            if( Sx != Sy ) cout << 0 << endl;
            else cout << ncr( Sx + C - 1, C - 1 ) << endl;
            continue;
        }

        if( A == 0 ){
            swap(A,B);
            swap(Sx,Sy);
        }
        long long ans;
        if( B == 0 ){
            ans = ncr(Sx-Sy-1,A-1) * ncr( (A+C-1) + Sy, A+C-1) % mod;
        }else{
            ans = 0;
            for(int a = A ; a <= Sx ; a++){
                long long X = ncr(a+A-1-A,A-1);
                int b = Sy - Sx + a;
                if( b < B ) continue;

                long long Y = ncr(b+B-1-B,B-1);
                long long Z = ncr( (A+B+C-1) + (Sx-a), A+B+C-1);

                ans += X * Y % mod * Z % mod;
                ans %= mod;
            }
        }
        cout << ans * f[A+B+C] % mod * inv[A] % mod * inv[B] % mod * inv[C] % mod << endl;  
    }
}