IOI 2014 Holiday

문제 링크

10076번: 휴가

PS-hell 스터디에서 가장 먼저 해결한 문제다.

문제 내용

길이 \(n\)의 선형 배열 \(a[0\ldots n-1]\)가 있다.

\(s\)번째 entry에서 시작해서 한 턴에 다음의 동작들을 할 수 있다.

초기 점수가 0점이고 현재 위치가 \(i\)번 이라고 할 때,

• Stay : 현재 점수에 \(a[i]\)를 더한다. 단, 한 번 Stay한 곳의 배열 값을 중복해서 더할 수 없다.
• goLeft, goRight : 각각 \(i-1\)번, \(i+1\)번 entry로 이동한다.

총 \(d\)턴 동안 점수를 최대화하는 문제이다.

 

---

스포방지선

 

 

 

 

 

 

 

 

 

 

 

---

기본 관찰

Stay를 제외하면, 이동을 LL....LRR...R 또는 RR...RLL...L 형태로 하는 것이 최적임을 알 수 있다.

RR...RLL...L 형태는 배열을 뒤집어서 동일한 과정을 반복하는 것으로 고려할 수 있다.

 

따라서 탐색할 구간 \([l, r]\)을 고정하면 이동에 소모하는 턴(날짜) 수는 \(s - l + r - l\)턴이므로 총 \(g(l, r) = \min(r-l+1, d+2l-r-s)\)턴 동안 Stay를 할 수 있다.

 

따라서 \([l, r]\)에서 최대의 \(g(l, r)\)개 원소를 뽑아주면 된다. \(l\)을 고정하고 \(r\)을 늘려가면서 std::set 등으로 관리하면 \(O(N^2 \lg N)\)에 문제를 해결할 수 있다. \(l \le s \le r\)이 성립해야 한다.

 

DnC approach

시간복잡도를 줄이기 위해서는 모든 \([l, r]\)을 다 보면 안된다. 한 가지 중요한 관찰은 고정된 \(l\)에 대해서 답을 최대로 하는 \(r\)값을 \(f(l)\)이라고 하면, \(f(l)\)이 \(l\)에 따라 단조증가한다는 것이다.

 

따라서 다음의 pseudo-code가 잘 작동한다:

 

def solve(s, e, d, u): #[s, e] : candidates for l, [d, u] : candidates for r; i.e. f(m)
	if(s > e): return
    m = (s + e) // 2
    
    opt = f(m, d, u) #gets f(m) with an appropriate O(e-s + u-d) procedure
    
    solve(s, m-1, d, opt)
    solve(m+1, e, opt, u)

가능한 후보를 Segment Tree나 set 등의 자료구조로 잘 manage하면 \(f(l)\)을 \(\mathcal{O}(N\lg N)\)에 구할 수 있고, 전체 복잡도는 \(\mathcal{O}(N\lg^{2} N)\). 단, 분할 정복 과정에서 update가 \(\mathcal{O}(e-s + u-d)\)번 정도만 수행되도록 잘 유지해야 한다. 구현 자유도는 굉장히 높은 것 같다. 메모리가 64MiB라서 Persistent Segment Tree를 쓰려면 주의해야 하는...줄 알았지만 PST로 만점을 받은 사람도 많이 있는 것 같다.

 

나는 가장 큰 \(k\)개의 합이 지원되는 Segment Tree로 풀었다.

 

 

\(\mathcal{O}(N\lg N)\) sketch

\(f(l, r)\)을 \([l, r]\)에서 가장 큰 \(g(l, r)\)개 수의 합이라고 하자.

그렇다면 \(l_{1} < l_{2} \le r_{1} < r_{2}\)에 대해 \(f(l_{1}, r_{1}) < f(l_{1}, r_{2}) \implies f(l_{2}, r_{1}) < f(l_{2}, r_{2})\)가 성립한다. 이를 total monotonicity라고 한다.

 

\(R \times C\) Totally monotone matrix \(f[l, r]\)에 대해, row minima를 구하는 \(\mathcal{O}(R + C)\) 알고리즘이 알려져 있다. \(f(l, r)\)을 amortized \(O(\lg N)\) 정도에 구할 수 있으니, 아마 \(\mathcal{O}(N \lg N)\)에 문제를 풀 수 있을 것이다. 솔직히 구현이 귀찮아서 해보진 않았다.