落ち着いて整理して考えましょう。問題自体は「累積和」が使える良い問題ですね！

問題概要

$N$ 個の電球を一列に並べていて、オンオフ状態が $A_{1}, A_{2}, \dots, A_{N}$ であるような状態を作りたいとします。ただし $A_{i} = 1$ は $i$ 番目の電球をオンにしたいことを表し、 $A_{i} = 0$ は $i$ 番目の電球をオフにしたいことを表します。

初期状態では、すべての電球がオフの状態です。あなたはまず、左から連続する何個かの電球をオンにすることができます。すべてオフのままでもよいですし、すべてをオンにしてもよいです。

その後、1 つの電球のオンオフ操作 (オンの電球はオフにして、オフの電球はオンにする) を実行していきます。このオンオフ操作の回数として考えられる最小値を答えてください。

制約

$1 \le N \le 2 \times 10^{5}$

問題を整理する

まず、「最初に左から何個分の電球をオンにするか」を決めると、その後の操作回数が決まることに注意しましょう。たとえば

$A = (0, 1, 1, 0, 0, 1)$ に対して、
左から 4 個分の電球をあらかじめオンにする

としたとしましょう。このとき操作回数は $A = (0, 1, 1, 0, 0, 1)$ と $(1, 1, 1, 1, 0, 0)$ とを比較して、相異なる箇所の個数に一致します。この場合は 3 回です。

0　1　1　0　0　1
1　1　1　1　0　0

よってまず次のような解法が考えられるでしょう。

「最初にオンにする電球の個数」を全探索して、
それぞれについて「相異なる箇所の個数」を調べる

しかしこれは $O(N^{2})$ の計算量となり、満点は得られません。

前処理で高速化

このようなとき、前処理で高速化するのが有効です。今回は次のような配列を用意しましょう。

left[i] ← $A_{1}, A_{2}, \dots, A_{N}$ のうち、左から $i$ 個分の中の、オフである電球の個数
right[j] ← $A_{1}, A_{2}, \dots, A_{N}$ のうち、右から $j$ 個分の中の、オンである電球の個数

これらの配列自体は $O(N)$ の計算量で計算できます。そしてこれらの配列が求められていると、なんと先ほどの探索が簡単に実行できます。

「最初に左から連続でオンにする個数」を $i$ 個としたとき、その後の必要な操作回数は

left[i] + right[N-i]

と簡単に表せるのです！！　たとえば先ほどの例 ( $A = (0, 1, 1, 0, 0, 1)$ 、 $i = 4$ ) の場合、下図のようになります。

よって次の解法で答えが求められます。今度は「最初に左から連続でオンにする個数」を決めたときの操作回数が $O(1)$ で求められるので、計算量は $O(N)$ となります。

配列 left、right を求める
i = 0, 1, ..., N に対する left[i] + right[N-i] の最小値を求める

コード

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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    // 前処理
    vector<int> left(N+1, 0), right(N+1, 0);
    for (int i = 0; i < N; ++i) {
        left[i+1] = left[i] + (A[i] == 0);
        right[i+1] = right[i] + (A[N-i-1] == 1);
    }

    // 最適化
    int res = N;  // 理論上の上限値
    for (int i = 0; i <= N; ++i) {
        res = min(res, left[i] + right[N-i]);
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOIG 2021 C - イルミネーション 2 (AOJ 0703, 難易度 4)

問題概要

制約

問題を整理する

前処理で高速化

コード