接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 199（ABC199）

AtCoder Beginner Contest 199（ABC199）

AtCoderBeginnerContest AtCoderBeginnerContest199 ABC ABC199

atcoder.jp

A - Square Inequality

オーバーフローなどの心配もないので素直に判定をする
提出コード

void solve(){
    ll A, B, C;
    cin >> A >> B >> C;
    if(A * A + B * B < C * C) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Intersection

最終的な答えは $ \max(A) \leq x \leq \min(B) $ を満たす $ x $ の個数なので $ \max(0, \min(B) - \max(A) + 1) $ が答え
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    REP(i,N) cin >> A[i];
    REP(i,N) cin >> B[i];
    int a = 0, b = INF;
    REP(i,N){
        chmax(a, A[i]);
        chmin(b, B[i]);
    }
    cout << max(0, b - a + 1) << endl;
}

C - IPFL

愚直に文字列を作り直したりすると間に合わないので少し工夫する必要がある
今どっちが先頭なのかをflagなどで持っておくと、swapを行うだけでいいので十分に間に合う
提出コード

void solve(){
    int N, Q;
    string S;
    cin >> N >> S >> Q;
    string s1 = S.substr(0, N);
    string s2 = S.substr(N, 2*N);
    int x = 0;
    REP(i,Q){
        int t, a, b;
        cin >> t >> a >> b;
        --a, --b;
        // dumps(i, a, b, x);
        if(t == 1){
            if(x == 0){
                if(a < N and b < N) swap(s1[a], s1[b]);
                else if(a < N and b >= N) swap(s1[a], s2[b-N]);
                else swap(s2[a-N], s2[b-N]);
            }
            else{
                if(a < N and b < N){
                    swap(s2[a], s2[b]);
                }
                else if(a < N and b >= N){
                    swap(s2[a], s1[b-N]);
                }
                else{
                    swap(s1[a-N], s1[b-N]);
                }
            }
        }
        else{
            x = 1 - x;
        }
    }
    if(x) cout << s2 << s1 << endl;
    else cout << s1 << s2 << endl;
}

D - RGB Coloring 2

どの頂点をどの色で塗るかを全探索をすると$ \mathcal{O}(3^N) $ となり間に合わない
どの頂点を赤色で塗り、他の頂点を青と緑色で塗るかを考える
そうすると、赤色で塗った頂点以外の各連結成分が二部グラフになっていればよくその場合の数を数えればいい
そのため、どの頂点を赤色で塗るかをbit全探索をし、各連結成分ごとに二部グラフになっているかを判定する
二部グラフを満たす場合、グラフ全体の連結成分の個数を $ sz $、赤色で塗った頂点の個数を $ cnt $ とすると $ 2 ^ {sz - cnt} $ 通り答えに加算する
実際の実装では二部グラフ判定のために頂点数を拡張しているので $ 2 ^ {\frac{sz}{2} - cnt} $ となる
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> edge(N);
    REP(i,M){
        int a, b;
        cin >> a >> b;
        --a, --b;
        edge[a] |= (1 << b);
        edge[b] |= (1 << a);
    }
    ll ans = 0;
    REP(i,1<<N){
        int cnt = 0;
        bool ok = true;
        REP(j,N) if(i >> j & 1){
            if(i & edge[j]) ok = false;
            cnt++;
        }
        if(!ok) continue;
        UnionFind uf(2*N);
        int sz = 2 * N;
        REP(j,N) if(!(i >> j & 1)){
            for(int k=j+1;k<N;k++){
                if((edge[j] >> k & 1) and !((i >> k & 1))){
                    if(uf.unite(j, k + N)) sz--;
                    if(uf.unite(k, j + N)) sz--;
                }
            }
        }
        REP(i,N) if(uf.issame(i, i + N)) ok = false;
        if(ok) ans += 1 << (sz / 2 - cnt);

    }
    cout << ans << endl;
}

E - Permutation

$ dp[state] := $ すでに選んだ整数の状態が $ state $ かつ $ X_i \leq |state| $ であるような条件を満たしているときの場合の数としてbitDPを行う
$ x \notin state $ を満たす整数 $ x $ を追加する時、$ X_i = |state \cap x | $ を満たす $ i $ について、$ state \cap x $ に含まれる $ Y_i $ 以下の整数が $ Z_i $ 以下の場合DPの遷移が可能となる
そのため、上記の条件を満たすようなDP遷移を行ったときの $ dp[2^N -1 ] $ が最終的な答えとなる
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> X(M), Y(M), Z(M);
    REP(i,M) cin >> X[i] >> Y[i] >> Z[i];
    vector dp(1<<N, 0LL);
    dp[0] = 1;
    for(int i=1;i<(1<<N);i++){
        bool ok = true;
        REP(j,M){
            if(__builtin_popcount(i) != X[j]) continue;
            int cnt2 = 0;
            REP(k,Y[j]) if(i >> k & 1) cnt2++;
            if(cnt2 > Z[j]) ok = false;
        }
        if(!ok) continue;
        REP(j,N) if(i >> j & 1) dp[i] += dp[i^(1<<j)];
    }
    cout << dp[(1<<N)-1] << endl;;
}