[IOI 2016] Detecting Molecules 풀이

문제 : http://oj.uz/problem/view/IOI16_molecules

---

바로 100점 풀이.

바로 100점으로 넘어가는 이유는 rkm0959의 풀이를 컨닝했기 때문. 

일단 주어진 배열의 값들을 정렬한 값의 인덱스를 \(i_1, i_2, \cdots , i_n\)으로 정의한다. 이제  수학이다.

\(Pro(k)\)를 다음과 같은 알고리즘으로 정의하자:

\(P(k) := w_{i_1} + \cdots + w_{i_k}, \ S(k) := w_{i_n} + \cdots w_{i_{n-k+1}} \)

case 1) \(P(k) > u \) : terminate (답이 없다)

case 2) \(P(k) or S(k) \in [l,u] \) : terminate (둘 중 [l,u]에 들어 있는 놈이 답이다)

case 3) \(P(k)<l \wedge S(k)>u \)

투 포인터를 잡자. front = 1, rear = k로.

이제 front랑 rear를 1칸씩 뒤로 시프트하면서 \(\sum_{j=\text{front}}^{\text{rear}} w_{i_j} \in [l,u]\)이면 걔가 답이다.

일단 3)이 돌아가는 순간 답을 찾을 수 있는데,

1칸씩 shift할 때 구간 합의 변화폭은 \(w_{i_{rear+1}}-w_{front}\)인데, 이 값은 \(u-l\)이하이다. 따라서 \(l\)미만에서 \(u\)초과로 갈 때 최대 \(u-l\)씩 변화하므로, \([l,u]\)에서 한 번은 걸리게 된다.

case 4) \(Pro(k+1)\)로 넘어간다.

Pro를 1부터 \(n\)까지 돌리면 끝.

Time Complexity : \(O(sort(n) +n ) = O(n \text{lg} n ) \)