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

### コンテスト名
AtCoder Beginner Contest 356

### コンテストURL
https://atcoder.jp/contests/abc356

### 開催日
2024/06/01 21:00-22:40

---

## [A: Subsegment Reverse](https://atcoder.jp/contests/abc356/tasks/abc356_a)
**解法**
- 問題文通りに出力する
    - $1$ から $L - 1$ まではそのままの順（昇順）で出力する
    - $L$ から $R$ は逆順（降順）で出力する
    - $R + 1$ から $N$ はそのままの順（昇順）で出力する
```cpp: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](https://atcoder.jp/contests/abc356/tasks/abc356_b)
**解法**
- シミュレーションする
- `vector<int>` で各栄養素を管理する
```cpp: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](https://atcoder.jp/contests/abc356/tasks/abc356_c)
**解法**
- bit 全探索でシミュレーションする
- `1` を正しい鍵、 `0` をダミーの鍵とする
- $C_i$ 本の鍵のうち正しい鍵が $K$ 本以上なら $R_i =$ `o` 、 $K$ 本未満なら $R_i =$ `x` であるかを判定して、すべての $i$ について矛盾しなければ当該組み合わせは条件を満たす
```cpp: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](https://atcoder.jp/contests/abc356/tasks/abc356_d)
**解法**
- 再帰的に求める
    - 求める答えを $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` に注意する
- 手元で書いて法則を見つける
```cpp: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