본문 바로가기
알고리즘

Usaco Gold) Fair Photography

by 박정률 2018. 6. 3.

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