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로 풀었다.

 

 

	#include <bits/stdc++.h>
	using namespace std;
	using ll = long long;
	int a[100005];
	int n, st, d;
	vector<int> cmp;
	struct Segtree{
	ll seg[262500];
	int cnt[262500];
	void init(){
	memset(seg, 0, sizeof(seg));
	memset(cnt, 0, sizeof(cnt));
	}
	void upd(int now, int s, int e, int i, int v){
	if(i < s || i > e) return;
	cnt[now] += v;
	seg[now] += v * cmp[i];
	if(s == e) return;
	int m = s + e >> 1;
	upd(now << 1, s, m, i, v);
	upd(now << 1 | 1, m+1, e, i, v);
	}
	ll sum_max_kth(int now, int s, int e, int k){
	if(!k) return 0;
	if(s == e) return ll(min(cnt[now], k)) * cmp[s];
	int m = s + e >> 1;
	if(cnt[now << 1 | 1] > k) return sum_max_kth(now<<1|1, m+1, e, k);
	else return sum_max_kth(now << 1, s, m, k - cnt[now<<1|1]) + seg[now<<1|1];
	}
	} S;
	map<int, int> M;
	bool chk[100005];
	void upd(int i, int v){
	if((v == 1) == chk[i]) return;
	chk[i] ^= 1;
	S.upd(1, 0, (int)cmp.size() - 1, a[i], v);
	}
	ll qry(int k){
	ll qv = S.sum_max_kth(1, 0, (int)cmp.size() - 1, k);
	return qv;
	}
	void init(){
	cin >> n >> st >> d;
	for(int i = 0; i < n; i++){
	cin >> a[i];
	cmp.push_back(a[i]);
	}
	sort(cmp.begin(), cmp.end());
	cmp.erase( unique(cmp.begin(),cmp.end()), cmp.end() );
	for(int i = 0; i < n; i++){
	a[i] = lower_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin();
	}
	}
	ll ans;
	void dnc(int s, int e, int kmin, int kmax){
	if(s > e) return;
	int m = s + e >> 1;
	for(int i = m; i <= e; i++) upd(i, 1);
	int klim = min(kmax, 2*m + d - st);
	ll lans = 0;
	int lansi = kmin;
	for(int i = kmin; i <= klim; i++){
	upd(i, 1);
	ll tmp = qry(d - (st-m) - (i-m));
	if(tmp > lans){
	lans = tmp;
	lansi = i;
	}
	}
	ans = max(ans, lans);
	for(int i = klim; i >= lansi; i--) upd(i, -1);
	if(m < e){
	int mm = (m+1+e) >> 1;
	for(int i = m; i <= mm; i++) upd(i, -1);
	dnc(m+1, e, lansi, kmax);
	}
	for(int i = kmax; i >= kmin; i--) upd(i, -1);
	if(s < m){
	int ss = (s+m-1) >> 1;
	for(int i = m; i < min(kmin, e+1); i++) upd(i, 1);
	dnc(s, m-1, kmin, lansi);
	for(int i = ss; i <= e; i++) upd(i, -1);
	}
	for(int i = m; i <= e; i++) upd(i, -1);
	for(int i = kmin; i <= lansi; i++) upd(i, -1);
	}
	void pro(){
	S.init();
	memset(chk,0,sizeof(chk));
	int l = max(0, st - d);
	dnc(l, st, st, n-1);
	}
	int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	init();
	pro();
	reverse(a, a+n); st = n-1-st;
	pro();
	cout << ans << '\n';
	}

view raw BOJ 10076.cpp hosted with ❤ by GitHub

$\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)$에 문제를 풀 수 있을 것이다. 솔직히 구현이 귀찮아서 해보진 않았다.