【ABC356】AtCoder Beginner Contest 356【C++】

コンテスト名

AtCoder Beginner Contest 356

コンテストURL

開催日

2024/06/01 21:00-22:40

---

A: Subsegment Reverse

解法

• 問題文通りに出力する
  • $1$ から $L - 1$ まではそのままの順（昇順）で出力する
  • $L$ から $R$ は逆順（降順）で出力する
  • $R + 1$ から $N$ はそのままの順（昇順）で出力する

ABC356A.cpp

#include <iostream>
using namespace std;

int main(){
    int n, l, r;
    cin >> n >> l >> r;

    int cnt = 0;
    for(int i=1; i<l; i++){
        if(cnt){
            cout << " ";
        }
        cnt++;
        cout << i;
    }

    for(int i=r; i>=l; i--){
        if(cnt){
            cout << " ";
        }
        cnt++;
        cout << i;
    }

    for(int i=r+1; i<=n; i++){
        if(cnt){
            cout << " ";
        }
        cnt++;
        cout << i;
    }

    cout << endl;
    return 0;
}

B: Nutrients

解法

• シミュレーションする
• vector<int> で各栄養素を管理する

ABC356B.cpp

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;

    vector<int> A(m);
    for(int i=0; i<m; i++){
        cin >> A[i];
    }

    int x;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> x;
            A[j] -= x;
        }
    }

    for(int i=0; i<m; i++){
        if(A[i]>0){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

C: Keys

解法

• bit 全探索でシミュレーションする
• 1 を正しい鍵、 0 をダミーの鍵とする
• $C_i$ 本の鍵のうち正しい鍵が $K$ 本以上なら $R_i =$ o 、 $K$ 本未満なら $R_i =$ x であるかを判定して、すべての $i$ について矛盾しなければ当該組み合わせは条件を満たす

ABC356C.cpp

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> A(m);
    vector<char> R(m);
    int c, a;
    for(int i=0; i<m; i++){
        cin >> c;
        for(int j=0; j<c; j++){
            cin >> a;
            a--;
            A[i].push_back(a);
        }
        cin >> R[i];
    }

    int ans = 0;
    bool flag;
    for(int i=0; i<(1<<n); i++){
        flag = true;
        for(int j=0; j<m; j++){
            int cnt = 0;
            for(int l=0; l<A[j].size(); l++){
                if(i & (1<<A[j][l])){
                    cnt++;
                }
            }
            if((cnt>=k && R[j]=='x') || (cnt<k && R[j]=='o')){
                flag = false;
            }

            if(!flag){
                continue;
            }
        }

        if(flag){
            ans++;
        }
    }

    cout << ans << endl;
    return 0;
}

D: Masked Popcount

解法

• 再帰的に求める
  • 求める答えを $f(N, M)$ とおく
  • $N$ が $n$ ビットで表されるとき、 $k = n - 1$ とおく
  • 右上の領域は $\text{popcount} (M \ \text{and} \ (2^k - 1)) \times 2^{k - 1}$
  • 左下の領域は 2 進数表記したときの $M$ の $2^k$ の桁が $1$ ならば $N - (2^k - 1)$ 、 $0$ ならば $0$
  • 右下の領域は $f(N - 2^k, M)$
• 1LL に注意する
• 手元で書いて法則を見つける

ABC356D.cpp

#include <iostream>
using namespace std;

const int MOD = 998244353;

int popcnt(long long int x){
    int cnt = 0;
    while(x){
        cnt += x & 1;
        x >>= 1;
    }
    return cnt;
}

int bitlen(long long int x){
    int cnt = 0;
    while(x){
        cnt++;
        x >>= 1;
    }
    return cnt;
}

long long int f(long long int n, long long int m){
    if(n==0){
        return 0;
    }
    if(n==1){
        return m & 1;
    }

    int k = bitlen(n) - 1;
    long long int a = popcnt(m & ((1LL<<k)-1)) * ((1LL<<(k-1)) % MOD) % MOD;
    long long int b;
    if(m & (1LL<<k)){
        b = (n - ((1LL<<k)-1)) % MOD;
    }else{
        b = 0;
    }
    long long int c = f(n - (1LL<<k), m) % MOD;

    return (a + b + c) % MOD;
}

int main(){
    long long int n, m;
    cin >> n >> m;

    cout << f(n, m) % MOD << endl;
    return 0;
}

参考

• https://atcoder.jp/contests/abc356/editorial/10138