APIO20 Paint

문제

oj.uz/problem/view/APIO20_paint

문제 보기 - 벽 칠하기 (APIO20_paint) :: oj.uz

길이 N의 배열을 각 칸을 $C_i$의 색으로 칠하려고 한다. 색의 종류는 K개, M명의 일꾼이 있으며, 각 일꾼마다 좋아하는 색의 목록이 있다. 색을 칠할 수 있는 방법은, 길이 M의 연속된 구간과 구간의 첫 시작점을 칠할 일꾼을 한 명 골라, i번째 칸은 (i+S) mod M번 일꾼이 칠하도록 하는 것이다. 이때 색칠해야 하는 칸의 색을 그 일꾼이 좋아해야 한다. 같은 칸은 여러번 칠할 수 있지만, 항상 해당 색으로 칠해야 한다. 이때 최소 연산 횟수를 이용하여 전체 칸을 색칠하자.

$N<=100000$

$M<=min(N, 50000)$

$K<=100000$

$f(k)$=색 k를 좋아하는 일꾼의 수 일 때 $\sum{f(k)^2}<=400000$

 

풀이

각 일꾼이 좋아하는 색 대신, 각 칸에 대해 그 칸을 칠할 수 있는 일꾼의 리스트를 저장해 놓았다고 생각하자. 이를 크기 $NM$의 테이블에 체크를 해 놓았다면 $O(NM)$에 dp를 통하여 색칠 가능한 구간의 목록을 모두 추출할 수 있다.

이후, 색칠 가능한 구간의 목록을 모두 추출하였다면, 슬라이딩 윈도우 DP를 이용하여 필요한 최소 연산의 개수를 구할 수 있다.

 

업데이트 과정에서 N개의 i에 대해 각 i에서 새로 전이될 수 있는 DP의 개수는 M이 아니라, 그 열에서 켜져 있는 칸들의 수와 같으므로, $O(\sum{f(C_i)})$의 시간 복잡도로 최적화할 수 있다.

 

Observation 1 : $\sum{f(C_i)} <= \sqrt{400000}N$

$\sum{f(k)^2} <= 400000$이니, $f(k)^2 <= 400000$, $f(k) <= \sqrt{400000}$이다.

 

따라서, 위 알고리즘은 $O(\sqrt{400000}N)$으로 통과한다.

 

시간 복잡도 : $O(\sqrt{400000}N)$

 

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int MAXM = 5e4;
const int MAXK = 1e5;

int N, M, K;
int C[MAXN+10];
vector<int> B[MAXK+10];

int dp[2][MAXM+10], chk[MAXN+10];
int dp2[MAXN+10];

int minimumInstructions(int _N, int _M, int _K, vector<int> _C, vector<int> _A, vector<vector<int>> _B)
{
	N=_N; M=_M; K=_K;
	for(int i=0; i<N; i++) C[i]=_C[i];
	for(int i=0; i<M; i++)
	{
		for(auto it : _B[i])
		{
			B[it].push_back(i);
		}
	}

	for(int i=0; i<N; i++)
	{
		if(i>=2)
		{
			for(auto it : B[C[i-2]])
			{
				dp[i&1][it]=0;
			}
		}
		for(auto it : B[C[i]])
		{
			dp[i&1][it]=1;
			if(i!=0 && dp[i-1&1][(it+M-1)%M])
			{
				dp[i&1][it]=dp[i-1&1][(it+M-1)%M]+1;
			}
			if(dp[i&1][it]>=M)
			{
				chk[i+1]=1;
			}
		}
	}

	deque<int> DQ;
	DQ.push_back(0);
	for(int i=1; i<=N; i++)
	{
		dp2[i]=987654321;
		if(!chk[i]) continue;
		while(!DQ.empty() && DQ.front()<i-M) DQ.pop_front();
		if(DQ.empty()) continue;
		dp2[i]=dp2[DQ.front()]+1;	
		while(!DQ.empty() && dp2[DQ.back()]>=dp2[i]) DQ.pop_back();
		DQ.push_back(i);
	}

	if(dp2[N]==987654321) return -1;
	return dp2[N];
}