AtCoder Beginner Contest 229（ABC229）

atcoder.jp

Bondo416さんのNECプログラミングコンテスト2021(AtCoder Beginner Contest 229)での成績：798位
パフォーマンス：1562相当
レーティング：1473→1482 (+9) :)#AtCoder #NECプログラミングコンテスト2021(ABC229) https://t.co/kZE56q4uBK

— ボンド@競プロ (@bond_cmprog) November 27, 2021

A - First Grid

.#
#.

もしくは

#.
.#

のときのみNo

提出コード

void solve(){
    string S1, S2;
    cin >> S1 >> S2;
    if((S1 == "#." and S2 == ".#") or (S1 == ".#" and S2 == "#.")) cout << "No" << endl;
    else cout << "Yes" << endl;
}

B - Hard Calculation

実際にシミュレートをして繰り上がりが発生するかどうかをチェックする

提出コード

void solve(){
    string A, B;
    cin >> A >> B;
    int cur = 0, rem = 0;
    int ma = max(size(A), size(B));
    reverse(ALL(A));
    reverse(ALL(B));
    A += string(ma - (int)size(A), '0');
    B += string(ma - (int)size(B), '0');
    bool ok = true;
    REP(i,ma){
        int cur = rem + (A[i] - '0') + (B[i] - '0');
        if(cur >= 10) ok = false;
        rem = cur / 10;
    }
    cout << (ok ? "Easy" : "Hard") << endl;
}

C - Cheese

$ A_i $ の大きい順に使えるだけ使っていく

提出コード

void solve(){
    ll N, W;
    cin >> N >> W;
    vector<ll> A(N), B(N);
    REP(i,N) cin >> A[i] >> B[i];
    vector<int> idx(N);
    iota(ALL(idx), 0);
    sort(ALL(idx), [&](int a, int b){
        return A[a] > A[b];
    });
    ll ans = 0;
    for(int i : idx){
        if(W > B[i]){
            ans += A[i] * B[i];
            W -= B[i];
        }
        else{
            ans += W * A[i];
            W = 0;
        }
    }
    cout << ans << endl;
}

D - Longest X

条件を満たす区間を効率よく求められればいい
予め累積和を取っておくことで、二分探索やしゃくとり法で求められる

提出コード

void solve(){
    string S;
    int K;
    cin >> S >> K;
    int N = S.size();
    vector<int> cum_X(N + 1), cum_dot(N + 1);
    REP(i,N){
        if(S[i] == '.'){
            cum_dot[i+1] += cum_dot[i] + 1;
            cum_X[i+1] = cum_X[i];
        }
        else{
            cum_dot[i+1] = cum_dot[i];
            cum_X[i+1] = cum_X[i] + 1;
        }
    }
    int ans = 0;
    REP(i,N){
        int idx = upper_bound(cum_dot.begin() + i, cum_dot.end(), cum_dot[i] + K) - cum_dot.begin() - 1;
        chmax(ans, cum_X[idx] - cum_X[i] + cum_dot[idx] - cum_dot[i]);
    }
    cout << ans << endl;
}

E - Graph Destruction

後ろからUnionFindで連結成分の個数を数える
今見ている頂点を $ i $ 、$ i $ と辺で繋がっている頂点を $ j $ とすると、$ i < j $ のとき連結させればいい

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    REP(i,M){
        int A, B;
        cin >> A >> B;
        --A, --B;
        G[A].emplace_back(B);
        G[B].emplace_back(A);
    }
    vector<int> ans(N, 0);
    UnionFind uf(N);
    int cur = 0;
    int sz = 0;
    for(int i=N-1;i>=1;i--){
        cur++;
        for(auto nv : G[i]){
            if(nv < i) continue;
            if(uf.unite(nv, i)) sz++;
        }
        ans[i-1] = cur - sz;
    }
    REP(i,N) cout << ans[i] << endl;
}