Educational Codeforces Round 81 - E. Permutation Separation

https://codeforces.com/contest/1295/problem/E%EF%BB%BF

Problem - E - Codeforces

문제 리딩이 깔끔해서 좋았다.

 

퍼뮤테이션 배열과 비용 배열이 입력으로 들어온다.

적당한 칸막이를 설치하여 왼쪽에 1~k의 퍼뮤테이션 값을 가지는 원소를, 오른쪽에 k+1~N의 값을 가지는 원소를 배치시키는 것을 최종목표로 하며, 원래 위치에서 좌 혹은 우 칸막이로 이동하는데 걸리는 코스트가 입력의 비용 배열이다.

 

초기 칸막이 위치가 k번째 원소와 k+1번째 원소 사이에 있었다고 가정하고, 결과적으로 왼쪽에 퍼뮤테이션의 1~t 원소가, 오른쪽에 t+1~N 원소가 위치하게 된다고 하자. 이 때 필요한 최소 비용을 $D[k][t]$ 라고 하면,

$$ D[k][t] = \sum_{i \leq k, P[i] > t} A[i] + \sum_{i > k, P[i] \leq t} A[i] $$

이다. 즉, 문제는 모든 $k$, $t$ 값에 대한 $D[k][t]$의 최소값을 찾는 문제와 같다.

 

현실적으로 복잡도 $O(N^2)$ 코드는 통과할 수 없다. 하지만 이를 이용해 점화식을 세우면 결과가 재미있어진다.

$$ D[k][0] = \sum_{i=1}^k A[i] $$

$$ D[k][t] = D[k][t-1] + (P^{-1}[t] \leq k?\; -A[P^{-1}[t]] : A[P^{-1}[t]]) $$

$D[k][t-1]$와 $D[k][t]$의 최종 상태의 유일한 차이점은 $P[i] = t$를 만족하는 $i$번째 원소가 칸막이 오른쪽/왼쪽에 위치하느냐 이다.

$i \leq k$ 이라면 초기 칸막이를 기준으로 원래도 왼쪽에 있었기 때문에 굳이 옮길 필요가 없어서 비용이 $A[i]$ 만큼 감소한다.

$i > k$ 이라면 원래 오른쪽에 있는 원소를 왼쪽으로 옮기는 것이기 때문에 비용이 $A[i]$ 만큼 증가한다.

 

최종적으로 구해야하는 문제의 해답은

$$ \min_{1 \leq k < N,\; 0 \leq t \leq N} D[k][t] $$

이므로, 각각의 $k$값에 대해

$$ \min_{0 \leq t \leq N} D[k][t] $$

를 빠르게 구할 수 있다면 해결된다.

 

삼항연산자 부분을 새로운 배열으로 정의하자.

$$ B[k][t] \triangleq P^{-1}[t] \leq k?\; -A[P^{-1}[t]] : A[P^{-1}[t]] \\= t \leq P[k]?\; -A[P^{-1}[t]] : A[P^{-1}[t]] $$

$k$ 값이 고정되어 있다면

$$ \min_{0 \leq t \leq N} D[k][t] = \left( \sum_{i=1}^k A[i] \right) + \min_{0 \leq t \leq N} B[k][t]$$

이다. (물론 정의의 일반성을 유지하기 위해 $B[k][0] = 0$ 으로 두자.)

그러므로 $B[k][.]$ 배열의 맨 왼쪽 원소부터 시작하는 최소 연속합을 구하는 문제와 동치이다.

 

또한, $B[k-1][.]$ 배열과 $B[k][.]$ 배열 원소는 오직

$$ P^{-1}[t] = k \quad (t = P[k]) $$

를 만족하는 $t$ 번째 원소만 서로 다른 값을 가지고 나머지 원소는 모두 값이 같다!

즉, $B[k-1][.]$ 배열에서 $P[k]$ 번째 원소의 값을 $+A[k]$ 값에서 $-A[k]$ 값으로 갱신해주면 된다.

 

단일 원소의 값이 바뀌는 최소 연속합 쿼리는 세그먼트 트리나 인덱스 트리로 어렵지 않게 구현된다.

 

되게 마음에 들었던 문제다.

대회 때 못 풀어서 아쉬웠다 ㅠㅠ

 

너무 formalized thinking에 집중하다보니까 시간 싸움에서 지는 것 같다.

빠르고 정확하게 사고하는 훈련도 열심히 해야겠다.

 

 

코드

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll*INF*INF;
 
#define CPPIO ios::sync_with_stdio(0); cin.tie(0); cout << std::setprecision(10); cout << fixed
 
#define forn(x, n) for (int x=0; x<(n); x++)
#define for1(x, n) for (int x=1; x<=(n); x++)
#define ford(x, n) for (int x=(n)-1; x>=0; x--)
#define ford1(x, n) for (int x=(n); x>=1; x--)
#define forr(x, n, m) for (int x=(n); x<=(m); x++)
#define forrd(x, n, m) for (int x=(m); x>=(n); x--)

template<typename T> inline bool uin(T &a, T b) { return a>b? (a=b, 1) : 0; }
 

struct segment_tree_min_sum {
	typedef long long ll;
 
	int l, r;
	ll sum;
	ll lmnsum, rmnsum, mnsum;
	const ll SEG_MAX = 0x3f2f1f0f3f2f1f0f;
 
	segment_tree_min_sum *left, *right; //, *parent;
	segment_tree_min_sum() : left(0), right(0) {}
	segment_tree_min_sum(int L, int R) : l(L), r(R), left(0), right(0) { make(); }
 
	void make() {
		sum = 0; // ::fill:: identity sum 
		if (l < r) {
			int m = (l + r) / 2;
			left = new segment_tree_min_sum(l, m);
			right = new segment_tree_min_sum(m+1, r);
		}
	}
 
	void update(int p, ll v) {
		if (l <= p && p <= r) {
			if (left) {
				left->update(p, v);
				right->update(p, v);
				sum = left->sum + right->sum;
				rmnsum = min(right->rmnsum, left->rmnsum + right->sum);
				lmnsum = min(left->lmnsum, right->lmnsum + left->sum);
				mnsum = min(left->rmnsum + right->lmnsum,
							min(left->mnsum, right->mnsum));
			} else {
				sum = lmnsum = rmnsum = mnsum = v;
			}
		}
	}
 
	ll naive_sum(int li, int ri) {
		if (li <= l && r <= ri) return sum;
		else if (r < li || ri < l) return 0;
		else {
			return (left->naive_sum(li, ri) + right->naive_sum(li, ri));
		}
	}
 
	ll left_min_sum(int li, int ri) {
		if (li <= l && r <= ri) {
			return lmnsum;
		} else if (li > r || l > ri) {
			return SEG_MAX;
		} else {
			return min(left->left_min_sum(li, ri),
						left->naive_sum(li, ri) + right->left_min_sum(li, ri));
		}
	}
 
	ll right_min_sum(int li, int ri) {
		if (li <= l && r <= ri) {
			return lmnsum;
		} else if (li > r || l > ri) {
			return SEG_MAX;
		} else {
			return min(right->right_min_sum(li, ri),
						right->naive_sum(li, ri) + left->right_min_sum(li, ri));
		}
	}
 
	ll _rmn(int li) {
		if (li <= l) return rmnsum;
		else if (li > r) return SEG_MAX;
		else return min(left->_rmn(li) + right->sum, right->_rmn(li));
	}
 
	ll _lmn(int ri) {
		if (r <= ri) return lmnsum;
		else if (l > ri) return SEG_MAX;
		else return min(right->_lmn(ri) + left->sum, left->_lmn(ri));
	}
 
	ll min_sum(int li, int ri) {
		if (li <= l && r <= ri) return mnsum;
		else if (li > r || l > ri) return SEG_MAX;
		else {
			return min(min(left->min_sum(li, ri), right->min_sum(li, ri)),
					left->_rmn(li) + right->_lmn(ri));
		}
	}
};

 
const int MAX_N = 2e5 + 20;
 
int N;
int P[MAX_N], iP[MAX_N];
ll A[MAX_N];
 
segment_tree_min_sum seg(0, MAX_N);
 
 
int main() {
	CPPIO;
	
	cin >> N;
	
	for1(i, N) cin >> P[i];
	for1(i, N) cin >> A[i];
 
	for1(i, N) iP[P[i]] = i;
 
	for1(i, N) {
		seg.update(P[i], A[i]);
	}
 
	ll d0 = 0;
	ll ans = LINF;
 
	for (int k=1; k<N; k++) {
		seg.update(P[k], -A[k]);
 
		d0 += A[k];
 
		ll lmnsum = seg.left_min_sum(1, N);
		uin(lmnsum, 0ll);
 
		uin(ans, d0 + lmnsum);
	}
 
	cout << ans << endl; 
}