[IOI 2016] Detecting Molecules 풀이

2017. 8. 9. 08:47알고리즘 문풀/Others

문제 : 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 ) \)


'알고리즘 문풀 > Others' 카테고리의 다른 글

Codeforces Goodbye 2017 Contest  (0) 2017.12.30
Codechef 2017 November LunchTime  (0) 2017.11.26
CodeForces #447 (Div.2 Only)  (1) 2017.11.20
Codeforces Round 433 Div.2  (1) 2017.09.07
APIO 2015 Jakarta Skyscrapers 풀이  (0) 2017.07.13