ABC 467 C - Adjacent Sums (easy)

[river0525]

問題の感想や気づきを投稿・共有するスペースです

[Yuulis]

公式解説に実装例が載ってないので、考察含めて書いておきます。E問題の部分問題ですが、C問題のみを解く解法です。

---

$M = 2$ なので、 $A_i$ は $0$ か $1$ のいずれかであり、これはビット列とみなしてよい。
操作後のビット列を $x_i$ として、条件を満たすためには、

$$ x_i + x_{i+1} \equiv B_i \pmod{2} $$

が成り立つ必要がある。
これは、 XOR を使うと以下のように書き直せる。

$$ x_i \oplus x_{i+1} = B_i \iff x_{i+1} = x_i \oplus B_i $$

つまり、最初のビット $x_1$ を決めると、残りの $N-1$ 個のビットは一意に決まる。

元の $A_i$ が取り得る値は $0$ か $1$ なので、 $i$ 番目の要素に対する操作回数は、

• $A_i \neq x_i$ の場合は $1$ 回
• $A_i = x_i$ の場合は $0$ 回

である。
$2$ 回以上余分に加えると偶奇は同じまま操作回数だけ増えるので、各要素への操作は高々 $1$ 回としてよい。

したがって、最初のビット $x_1$ を $0$ とした場合と $1$ とした場合の両方を試して、操作回数の合計が少ない方を選べばよい。

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(N - 1);
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N - 1) cin >> B[i];

    auto calc = [&](int bit) -> int {
        int res = 0;
        int now = bit;
        rep(i, 0, N) {
            if (now != A[i]) {
                res++;
            }

            if (i < N - 1) {
                now ^= B[i];
            }
        }
        return res;
        };

    cout << min(calc(0), calc(1)) << endl;

    return 0;
}

https://atcoder.jp/contests/abc467/submissions/77592020

ブログにも書きました。
https://yuulisio.com/posts/review-abc467-c