백준 6231, Prefix Sum, Hashing
USACO March 2007 Contest Gold 1번 문제.
Hashing 을 이용하는 새로운 방법을 배운 문제다.
$psum[i][j]$ 를 $i$ 번째 소 까지 $j$ 번째 $feature$ 의 합을 나타낸다고 하자.
$psum[i][p] - psum[j][p] == psum[i][0] - psum[j][0]$ 을 만족하는 $i$ 와 $j$ 가 있다면
$i+1$ 부터 $j$ 까지가 조건을 만족하는 구간이라는 사실은 자명하다.
여기까지는 쉽게 생각할 수 있었지만, 이후에 식을 한 번 바꾸는걸 생각 못했다.
양변을 정리하면 $psum[i][p] - psum[i][0] == psum[j][p] - psum[j][0]$ 가 된다.
따라서 $0$ ~ $K-1$ 까지 $p$ 들에 대해서 $psum[i][p] - psum[i][0]$ 들만 비교하면 된다.
$psum[i]$ 를 크기 $K$ 인 vector 로 만들고, $map<vector
Source Code
//BOJ6231
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
int N, K, ans;
map<vi, int> mp;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K;
ans = 0;
vi featureID(K);
mp[featureID] = 0;
//featureID : 1~K 까지 p 에 대해 psum[i][p] - psum[i][0] 가 적용된 누적합
for (int i = 1; i <= N; ++i) {
int t, x;
cin >> t;
x = t;
for (int j = 0; j < K; ++j) {
featureID[j] += t % 2;
t /= 2;
//누적합을 더해준다.
}
if ( x%2 ) {
for (int j = 0; j < K; ++j) --featureID[j];
//psum[i][0] 를 빼준다.
}
/*
for (int j = 0; j < K; ++j) {
printf("%d ", featureID[j]);
}
printf("\n");
*/
if (mp.count(featureID)) {
//일치하는 누적합 상태가 있는지 확인. 있으면 현재 위치 - 누적합 위치가 구간 길이.
ans = max(ans, i - mp[featureID]);
}
else mp[featureID] = i;
//없으면 위치 표시.
}
printf("%d\n", ans);
return 0;
}