接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 222（ABC222）

AtCoder Beginner Contest 222（ABC222）

AtCoderBeginnerContest AtCoderBeginnerContest222 ABC ABC222

atcoder.jp

A - Four Digits

4桁になるまで先頭に 0 を付け足す

提出コード

void solve(){
    string S;
    cin >> S;
    S = string(4-(int)S.size(), '0') + S;
    cout << S << endl;
}

B - Failing Grade

$ a_i \lt P $ の個数を数える

提出コード

void solve(){
    int N, P;
    cin >> N >> P;
    int ans = 0;
    REP(i,N){
        int a;
        cin >> a;
        if(a < P) ans++;
    }
    cout << ans << endl;
}

C - Swiss-System Tournament

書いてあるとおりにシミュレートする
$ i $ ラウンド目が終わった時点の順位は毎回ソートで求めればいい

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<vector<char>> A(2*N, vector<char>(M));
    REP(i,2*N) REP(j,M) cin >> A[i][j];
    vector<pair<int, int>> vp;
    REP(i,2*N) vp.emplace_back(0, i);
    REP(i,M){
        REP(j,N){
            int x = vp[2*j].second;
            int y = vp[2*j+1].second;
            char c1 = A[x][i];
            char c2 = A[y][i];
            if(c1 == c2) continue;

            if(c1 == 'G'){
                if(c2 == 'P') vp[2*j+1].first--;
                else vp[2*j].first--;
            }
            else if(c1 == 'C'){
                if(c2 == 'G') vp[2*j+1].first--;
                else vp[2*j].first--;
            }
            else if(c1 == 'P'){
                if(c2 == 'C') vp[2*j+1].first--;
                else vp[2*j].first--;
            }
        }
        sort(ALL(vp));
    }
    REP(i,2*N) cout << vp[i].second + 1 << endl;
}

D - Between Two Arrays

$ dp[i][j] := i $ 個目を $ j $ にしたときの場合の数としてDPをする
$ dp[i+1][j] = \sum_{0 \leq k \leq j} dp[i][k] $ となるので、累積和で更新していく

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> a(N), b(N);
    REP(i,N) cin >> a[i];
    REP(i,N) cin >> b[i];
    vector<mint> dp(3030);
    dp[0] = 1;
    REP(i,N){
        vector<mint> nxt(3030);
        mint sum = 0;
        REP(j,3030){
            sum += dp[j];
            if(a[i] <= j and j <= b[i]) nxt[j] += sum;
        }
        swap(nxt, dp);
    }
    mint ans = 0;
    REP(i,3030) ans += dp[i];
    cout << ans << endl;
}

E - Red and Blue Tree

$ R - B = sum $ とし、$ i $ 番目の辺を通る回数を $ cnt_i $ とすると、$ sum $ に $ cnt_i $ を足すか引くかの2通りになる
これは部分和問題としてDPをすることで解けるので、各辺が何回通るかをBFSなどで最短経路を求めたあとに復元を行い数える
そのままやると $ sum $ が負になるので、適当な定数を足した状態で行う

提出コード

void solve(){
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> A(M);
    REP(i,M){
        cin >> A[i];
        --A[i];
    }
    vector<vector<int>> g(N);
    vector<vector<int>> edge(N, vector<int>(N));
    REP(i,N-1){
        int u, v;
        cin >> u >> v;
        g[--u].emplace_back(--v);
        g[v].emplace_back(u);
        edge[u][v] = edge[v][u] = i;
    }
    vector<int> cnt(N-1);
    REP(i,M-1){
        vector<int> dist(N, INF);
        vector<int> pre(N, -1);
        queue<int> q;
        q.emplace(A[i]);
        dist[A[i]] = 0;
        while(!q.empty()){
            int v = q.front(); q.pop();
            for(auto nv : g[v]){
                if(dist[nv] < INF) continue;
                dist[nv] = dist[v] + 1;
                pre[nv] = v;
                q.emplace(nv);
            }
        }
        int cur_v = A[i+1];
        while(pre[cur_v] != -1){
            int nxt = pre[cur_v];
            cnt[edge[cur_v][nxt]]++;
            cur_v = nxt;
        }
    }
    vector<mint> dp(202020);
    const int base = 101010;
    dp[base] = 1;
    REP(i,N-1){
        vector<mint> nxt(202020);
        REP(j,202020) if(dp[j] != 0){
            if(j - cnt[i] > 0 and j - cnt[i] < 202020) nxt[j - cnt[i]] += dp[j];
            if(j + cnt[i] > 0 and j + cnt[i] < 202020) nxt[j + cnt[i]] += dp[j];
        }
        swap(nxt, dp);
    }
    cout << dp[base+K] << endl;
}