Zenn
🔵

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

2024/06/03に公開
C++
競技プログラミング
AtCoder
アルゴリズム
tech

コンテスト名

AtCoder Beginner Contest 356

コンテストURL

https://atcoder.jp/contests/abc356

開催日

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;
}

参考

Discussion