6231번: Gold Balanced Lineup

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


$O(kn\lg n)$

sum(a[0][i...j]) = sum(a[1][i...j]) = ... = sum(a[k-1][i...j])인 최대 j-i+1을 구하는 문제

s[i][j]=sum(s[i][1...j])라고 하면
s[0][j]-s[0][i-1] = s[1][j]-s[1][i-1] = ... = s[k-1][j]-s[i-1][i-1]
이와 동치인 연립등식은 다음과 같다.
s[0][j]-s[k-1][j] = s[0][i-1]-s[k-1][i-1]
s[1][j]-s[k-1][j] = s[1][i-1]-s[k-1][i-1]
...
s[k-2][j]-s[k-1][j] = s[k-2][i-1]-s[k-1][i-1]

이제 (s[0...k-2][i]-s[k-1][i])가 key인 해쉬를 이용하면 매 i마다 같은 key값의 최소 인덱스를 빠르게 구할 수 있다.

#include<cstdio>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
int n, k, r;
map<vector<int>, int> mp;
int main() {
    scanf("%d%d", &n, &k);
    vector<int> s(k);
    mp[s] = 0;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        for (int j = k; j--; x /= 2) s[j] += x & 1;
        for (auto &it : s) it -= s[k - 1];
        auto it = mp.find(s);
        if (it != mp.end()) r = max(r, i - it->second);
        else mp[s] = i;
    }
    printf("%d", r);
    return 0;
}