7976번: 수열

https://www.acmicpc.net/problem/7976


$O(n)$

$a[i]+a[i+1]+...+a[i+k-1]\equiv a[i+1]+...+a[i+k] (mod 2)$
$a[i]\equiv a[i+k] (mod 2)$
따라서 k로 나눈 나머지가 같은 번째의 항들은 홀짝성이 같아야 한다.

이를 이용해 본 문제의 답을 구하자.
먼저, k로 나눈 나머지가 같은 번째의 항들마다 홀수 개수와 짝수 개수를 구하고 적은 쪽의 항들을 바꿔놓고 보자.
그러면 처음 k개의 수를 더했을 때 홀수가 될 수도 있는데 이런 경우에만 홀, 짝 개수 차가 적었던 항들의 홀짝성을 바꿔주면 된다.

#include<cstdio>
#include<algorithm>
using namespace std;
int c[1000000][2], n, k, r, b, mini = 1e6;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        c[i%k][x & 1]++;
    }
    for (int i = 0; i < k; i++) {
        r += min(c[i][0], c[i][1]);
        mini = min(mini, abs(c[i][0] - c[i][1]));
        b ^= c[i][0] < c[i][1];
    }
    printf("%d", r + mini*b);
    return 0;
}