【AtCoder】ABC 467 C - Adjacent Sums (easy)

C - Adjacent Sums (easy)

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 608 / NoviSteps: 2Q / 配点: 300 点

問題概要

$0$ 以上 $M-1$ 以下の整数からなる整数列 $A=(A_1,A_2,\dots,A_N), \, B=(B_1,B_2,\dots,B_{N-1})$ が与えられる。

$A$ に対して以下の操作を好きな回数行う。

• $1$ 以上 $N$ 以下の整数 $i$ を $1$ つ選び、$A_i$ に $1$ を加える。

以下の条件を満たすようにするために必要な操作回数の最小値を求めよ。 なお、問題の制約下では、必ず条件を満たすようにできることが証明できる。

• $i=1,2,\dots,N-1$ について、$A_i+A_{i+1}$ を $M$ で割った余りは $B_i$ に等しい。

制約

• $2 \leq N \leq 2 \times 10^5$
• $M=2$
• $0 \leq A_i \leq M-1$
• $0 \leq B_i \leq M-1$
• 入力される値はすべて整数

考察

$M = 2$ なので、 $A_i$ は $0$ か $1$ のいずれかであり、これはビット列とみなしてよい。

操作後のビット列を $x_i$ として、条件を満たすためには、$x_i + x_{i+1} \equiv B_i \pmod{2}$ が成り立つ必要がある。

これは、 XOR を使うと以下のように書き直せる。

つまり、最初のビット $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$ とした場合の両方を試して、操作回数の合計が少ない方を選べばよい。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.// ======================================== //
7. 
8.int main()
9.{
10.    int N, M;
11.    cin >> N >> M;
12.    vector<int> A(N), B(N - 1);
13.    rep(i, 0, N) cin >> A[i];
14.    rep(i, 0, N - 1) cin >> B[i];
15. 
16.    auto calc = [&](int bit) -> int {
17.        int res = 0;
18.        int now = bit;
19.        rep(i, 0, N) {
20.            if (now != A[i]) {
21.                res++;
22.            }
23. 
24.            if (i < N - 1) {
25.                now ^= B[i];
26.            }
27.        }
28.        return res;
29.        };
30. 
31.    cout << min(calc(0), calc(1)) << endl;
32. 
33.    return 0;
34.}

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

atcoder.jp

実装時間: 10分

コメント

Twitter では動的計画法っぽく解いている人もいたが、これはE問題意識してるのか？