Problem
1부터 10억까지 좌표중에, N개의 값을 넣는다. 해당 값은 1~8사이 이다.
이 중 두가지 조건을 만족하는 가장 긴 길이의 범위는?
- 서로다른 K개의 이상의 값이 존재해야한다.
- 각 값들의 갯수는 같아야 한다.
논리 과정
T(b,p) 를 p보다 왼쪽에있는 b의 갯수라고 하자.
- T(b,R) = T(b,L) + c 만약 이 사이에 b 가 존재한다면.
- T(b,R) = T(b,L) 이다 만약 b가 존재하지 않는다면.
따라서 집합 A 와 기준점 p 가 주어지면 우리는 signature S(A,p) 를 만들 수 있다.
- T(b,p) - T(b0,p) 이 때 b0 는 A 안에 첫번쨰 원소이다.
- T(b,p) 는 존재하지 않는것에 대하여.
만약 S(A,L) = S(A,R) 이고 L<R이라면 L-R 은 유효하다.
S는 각 원소들의 차이값이다.
모든 S(A,L) 값을 전처리 한 후 A,R을 고정시키고, 그 와 매칭하는 가장 작은 L을 구해주면 된다.
이 과정에서 MAP 을 이용한다.
K개의 이상의 원소를 포함하는 조건을 만족시키기 위해서 인덱스를 추가한것.
따라서 차이값을 이용해서 map(vector, int) 로 문제를 해결한다. 벡터해쉬
'알고리즘' 카테고리의 다른 글
boj2319)사수아탕 (0) | 2018.08.15 |
---|---|
이항계수를 빠르게 구하는 알고리즘 (3) | 2018.07.05 |
[기하] 다각형의 내부 외부 판별 (0) | 2018.05.13 |
BOJ 6171) 땅따먹기 (0) | 2018.05.13 |
DP최적화 - Convex Hull Trick (0) | 2018.05.06 |