【c++】ABC356 A-D問題解説【ACコード付き】

# AtCoder Beginner Contest 355
A,B,Dの3完。

Aに10分かかった時には終わったかと思ったが、B,Cは比較的スムーズに実装できた。（CはずっとWAだったが）

Cも

レートは506→564の+58となり、+50を継続するのが目標だったので最低ラインはクリア。パフォーマンスも過去最高の942となった。

C問題がずっとACできず、その上D問題に取り掛かるのが遅れたことが悔やまれる。Cを1回目の実装でサクッとクリアしていたら、もしかしたら水色パフォまであったかもしれない。

しかし、過去を振り返ってもしょうがない。

来週も初中級者が解くべき過去問精選100問を引き続き積み上げていきます。

https://atcoder.jp/contests/abc356

## A - Subsegment Reverse
長さ$N$の数列 $ A = (1,2,...,N)$に対して、$L$ 項目と $R$ 項目の間を反転して出力せよ、という問題。

$L$ 項目と $R$ 項目の間だけ逆転させて表示させる部分で、条件分岐をややこしく考えてしまい、10分ほど掛かったのが反省。

```cpp
int L, R, N, tmp;

int main()
{
	cin >> N >> L >> R;
	for (int i = 1; i <= N; i++)
	{
		if (i > 1) cout << " ";
		if (L == i) tmp = i;
		if (L <= i && R >= i) cout << tmp + R  - i;
		else cout << i;
	}
	cout << endl;
	return 0;
}
```

## B - Nutrients
$M$ 種類の栄養素について、$N$ 品の食事で1日当たりの摂取量を摂れているかを判定する問題。

ひたすら栄養素ごとに1日の摂取量を足し合わせて、全ての栄養素で十分かどうか判定する。個人的にはA問題よりもわかりやすい問題で、3分ほどで実装できた。

```cpp
int N ,M;
int A[109];
int X[109][109];
int dp[109];

int main()
{
	cin >> N >> M;
	for (int i = 1; i <= M; i++) cin >> A[i];
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin >> X[i][j];
			dp[j] += X[i][j];
		}
	}
	for (int j = 1; j <= M; j++)
	{
		if (dp[j] < A[j])
		{
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}
```

## C - Keys
正しい鍵とダミーな鍵を合わせて $N$ 本持っている。そのうち特定の鍵を刺してドアが開くか $M$ 回テストを行った。このドアは $K$ 本以上の正しい鍵が刺さったら開き、そうでないと開かない。可能性のある鍵の組み合わせ(正しい鍵とダミーの鍵の組み合わせ $N^2$ のうち、条件に矛盾しない組)の数を出力せよ、という問題。

ちょうどビット全探索の演習問題をやっていた日だったので、ビット全探索でひたすら検証し、可能性のある鍵の組み合わせの個数を出せばいいと思ってコンテスト中に実装したのが以下。

ただテストケースの1/3がずっとWAで、コンテスト中には原因がわからなかった。

```cpp
// これはACコードではありません
long long N, M, K;
long long C[1009];
char R[1009];
bool R_key[1009];
long long A[109][109];
bool key[109];

int main()
{
    cin >> N >> M >> K;
    for (long long i = 1; i <= M; i++)
    {
        cin >> C[i];
        for (long long j = 1; j <= C[i]; j++) cin >> A[i][j];
        cin >> R[i];
        if (R[i] == 'o') R_key[i] = true;
        else R_key[i] = false;
    }
    long long ans = 0;
    // ビット全探索
    for (long long i = 0; i < (1LL << N); i++)
    {
        long long tmp = i;
        long long count = 0;
        for (long long j = 1; j <= N; j++)
        {
            if (tmp >> (j - 1) & 1)
            {
                key[j] = true;
                count++;
            }
            else key[j] = false;
        }
        if (count < K) continue;
        bool valid = true;
        for (long long i = 1; i <= M; i++)
        {
            long long num_true = 0;
            for (long long j = 1; j <= C[i]; j++)
            {
                if (key[A[i][j]])
                {
                    num_true++;
                }
            }
            if (num_true >= K && !R_key[i])
            {
                valid = false;
                break;
            }
            if (num_true < K && R_key[i])
            {
                valid = false;
                break;
            }
        }
        if (valid) ans++;
    }
    cout << ans << endl;
    return 0;
}
```

コンテスト終了後、配列ではなくvector、indexを1からではなく0からに変更して実装したのが以下。

```cpp
// こちらがC問題のACコードです
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> key(m, vector<int>(n, 0));
    vector<string> r(m);
    
    for (int i = 0; i < m; i++) {
        int c;
        cin >> c;
        for (int j = 0; j < c; j++) {
            int a;
            cin >> a;
            key[i][a - 1] = 1;
        }
        cin >> r[i];
    }

    int res = 0;
    for (int i = 0; i < (1 << n); i++) {
        vector<int> tf(n);
        for (int j = 0; j < n; j++) {
            tf[j] = (i & (1 << j)) ? 1 : 0;
        }

        bool jud = true;
        for (int j = 0; j < m; j++) {
            int ck = 0;
            for (int p = 0; p < n; p++) {
                if (key[j][p] == 1 && tf[p] == 1) {
                    ck++;
                }
            }
            if ((ck >= k && r[j] == "x") || (ck < k && r[j] == "o")) {
                jud = false;
                break;
            }
        }
        if (jud) {
            res++;
        }
    }
    cout << res << "\n";
    return 0;
}

```

## D - Masked Popcount
以下の式を998244353で割った余を求める。
$\&$はビット単位AND演算で、popcount(x)はxを2進数表記をした時に1が出てくる回数。

$$
\sum_{k=0}^{N} \text{popcount}(k \& M)
$$

数式通りに $O(N)$ のループを回しでビット単位AND演算を行い、ビットが立っている数を求めたのが以下。（TLE）

```cpp
long long N, M;

int main()
{
	cin >> N >> M;
	long long ans = 0;
	for (int i = 1; i <= N; i++)
	{
		long long tmp = i & M;
		for (int j = 0; j < 60; j++)
		{
			if ((tmp >> j) & 1) ans++;
		}
		ans %= 998244353;
	}
	cout << ans << endl;
	return 0;
}
```

D問題は屈辱ながらLLMにほぼ解いてもらいました。
ビットを桁ごとに見ると周期性がある、とこまでは考えられたても、実装力が追いつきませんでした。。

```cpp
// こちらがD問題のACコードです
const long long MOD = 998244353;

int popcount(long long x) {
    return __builtin_popcountll(x);
}

int main() {
    long long N, M;
    cin >> N >> M;
    long long ans = 0;
    for (int bit = 0; bit < 60; bit++) {
        long long block_size = 1LL << bit;
        long long full_blocks = (N + 1) / block_size;
        long long remainder = (N + 1) % block_size;
        long long count_ones = (full_blocks / 2) * block_size;
        if (full_blocks % 2 == 1) count_ones += remainder;
        if (M & (1LL << bit)) ans = (ans + count_ones) % MOD;
    }
    cout << ans << endl;
    return 0;
}
```