接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 216（ABC216）

AtCoder Beginner Contest 216（ABC216）

AtCoderBeginnerContest AtCoderBeginnerContest216 ABC ABC216

atcoder.jp

A - Signed Difficulty

文字列などで受け取って、$ X, Y $ を整数に変換する
提出コード

void solve(){
    string XY;
    cin >> XY;
    int x = 0;
    int y = 0;
    bool ok = false;
    for(char c : XY){
        if(c == '.') ok = true;
        else if(ok) y = c - '0';
        else{
            x = 10 * x + (c - '0');
        }
    }
    cout << x;
    if(y <= 2) cout << "-";
    else if(y <= 6){}
    else cout << "+";
    cout << endl;
}

B - Same Name

$ S_i = S_j $ かつ $ T_i = T_j $ を満たすものが存在するかどうか愚直に判定
提出コード

void solve(){
    int N;
    cin >> N;
    vector<string> S(N), T(N);
    REP(i,N) cin >> S[i] >> T[i];
    string ans = "No";
    REP(i,N) for(int j=i+1;j<N;j++){
        if(S[i] == S[j] and T[i] == T[j]) ans = "Yes";
    }
    cout << ans << endl;
}

C - Many Balls

上位bitから見ていく
各bitごとにNが立っているbitならAを出力し、その後bitの状態に関わらずBを出力する
提出コード

void solve(){
    ll N;
    cin >> N;
    for(int i=60;i>=0;i--){
        if(N >> i & 1){
            cout << "A";
        }
        if(i > 0) cout << "B";
    }
    cout << endl;
}

D - Pair of Balls

ある $ x $ は、ちょうど2つしか存在しないので、ある $ x $ に対し操作を行えるなら行うのが最適
各 $ x $ ごとに筒の一番上に存在する個数とそのインデックスをqueueなどで管理し、2個になったものから操作を行っていくのをシミュレートする
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<queue<int>> a(M);
    REP(i,M){
        int k;
        cin >> k;
        REP(j,k){
            int b;
            cin >> b;
            --b;
            a[i].emplace(b);
        }
    }
    vector<int> cnt(N, -1);
    queue<pair<int, int>> q;
    REP(i,M){
        int num = a[i].front(); a[i].pop();
        if(cnt[num] == -1) cnt[num] = i;
        else{
            q.emplace(i, cnt[num]);
        }
    }
    int used = 0;
    while(!q.empty()){
        auto [idx1, idx2] = q.front(); q.pop();
        used += 2;
        if(!a[idx1].empty()){
            int nxt1 = a[idx1].front(); a[idx1].pop();
            if(cnt[nxt1] == -1) cnt[nxt1] = idx1;
            else q.emplace(idx1, cnt[nxt1]);
        }
        if(!a[idx2].empty()){
            int nxt2 = a[idx2].front(); a[idx2].pop();
            if(cnt[nxt2] == -1) cnt[nxt2] = idx2;
            else q.emplace(idx2, cnt[nxt2]);
        }
    }
    if(used == 2 * N) cout << "Yes" << endl;
    else cout << "No" << endl;
}

E - Amusement Park

$ A_i $ の降順にシミュレートを行う
今 $ A_i $ を見ているとき、得られる満足度の総和は、 $ [A_i, A_{i+1} ) $ の区間の等差数列の和となる
その後、$ A_{i+1} $ に $ A_i $ の個数をマージしていくことで、 最大で $ O(N) $ 個まで見れば十分
これを $ K $ がなくなるまでか、$ 0 $ を番兵として、 $ 0 $ まで見終わるまで繰り返していけばいい
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    map<ll, ll> mp;
    REP(i,N){
        int A;
        cin >> A;
        mp[A]++;
    }
    mp[0] = 0;
    ll ans = 0;
    REP(i,N){
        auto [k, v] = *mp.rbegin();
        auto itr = mp.rbegin();
        dumps(K, k, v, ans);
        itr++;
        if(itr == mp.rend()){
            break;
        }
        else{
            auto [nxt_k, nxt_v] = *itr;
            ll sub = k - nxt_k;
            if(sub * v <= K){
                ans += sub * (k + nxt_k + 1) / 2 * v;
                K -= sub * v;
            }
            else{
                ll lim_k = k - floor_div(K, v);
                ans += (k - lim_k) * (k + lim_k + 1) / 2 * v;
                K -= (k - lim_k) * v;
                ans += lim_k * K;
                break;
            }
            mp[nxt_k] += v;
            mp.erase(k);
        }
    }
    cout << ans << endl;
}

F - Max Sum Counting

$ \max(A) \leq 5000 $ なので $ \sum _{i \in S} B_i \leq 5000 $ まで考えればいいのでこの範囲でDPする
$ \max(A) $ の制約があるのでこの制約の昇順にソートをしてDPを行う
$ dp[i][j][k] := i $ 番目まで見て、選んだ集合の総和が $ j $ で、$ j \leq \max(A_i) $ を満たしている $ (k = 0) $ もしくは、満たしていない $ (k = 1) $ のときの場合の数としてDPをする
提出コード

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<int> idx(N);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b){
        return A[a] < A[b];
    });
    vector dp(5050, vector<mint>(2, 0));
    dp[0][1] = 1;
    for(int i : idx){
        int lim = A[i];
        vector nxt(5050, vector<mint>(2, 0));
        for(int k=5049;k>=0;k--){
            nxt[k][0] += dp[k][0];
            nxt[k][1] += dp[k][1];
            if(B[i] + k < 5050){
                if(B[i] + k <= lim) nxt[B[i] + k][0] += dp[k][0] + dp[k][1];
                else nxt[B[i] + k][1] += dp[k][0] + dp[k][1];
            }
        }
        swap(dp, nxt);
    }
    mint ans = 0;
    for(int i=1;i<5050;i++) ans += dp[i][0];
    cout << ans << endl;
}