Codeforces #230 Div1. D. Three Arrays

そういやここらへんはデータが吹っ飛んだ時か…。
http://codeforces.com/contest/392/problem/D

問題

３つのN要素の数列A,B,Cが与えられる。
A,B,Cの先頭u,v,w要素を合わせてできる集合が、A,B,Cに登場する全要素を含むようにしたい。
u+v+wの最小値を求めよ。

解法

まず整数を座標圧縮しよう。
その際、A,B,Cの順に見て早く登場した数値ほど小さい数値にする。
また、各整数が各数列で最小何番目に登場するかを求めておこう。

座標圧縮後、ユニークな整数がM個になったとする。
先頭i個の整数をAから確保するとすると、残った(i+1)番目～M番目を含むようにB,Cのprefixを取りたい。

(i+1)～M番目をカバーするような(v,w)の組み合わせを考えると、２次元座標第１象限において原点を含む凸図形を除いた形状になる。
その凸図形における(v+w)の最小値が、iに対応する最小の(v+w)となる。

上記考察をもとに、以下のように処理する。
iを大きい順に総当たりする。「各整数が各数列で最小何番目に登場するか」を先に求めてあるので、uが求まる。
あとは(v,w)の凸包を段々小さくしていこう。
既存の凸包のうち、B[v]=iなら(v,w)→(v-1,w)、C[w]=iなら(v,w)→(v,w-1)と凸包を構成する頂点を原点に近づけて移動できる。

int N;
int V[3][101000];
map<int,int> M;
int mi[3][303000];
set<pair<int,int> > P;
multiset<int> R;

void add(int bx,int cy) {
	int y;
	set<pair<int,int> >::iterator it=P.lower_bound(make_pair(bx,cy));
	if(it->second>=cy) return;
	y=it->second;
	R.insert(bx+y);
	it--;
	while(it->second<=cy) R.erase(R.lower_bound(it->first+y)),y=it->second, P.erase(it--);
	assert(R.count(it->first+y)>0);
	R.erase(R.lower_bound(it->first+y));
	
	P.insert(make_pair(bx,cy));
	R.insert(it->first+cy);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	int debug=0;
	FOR(i,3) {
		FOR(j,3*N+5) mi[i][j]=4*N;
		FOR(j,N) {
			cin>>x;
			if(M.count(x)==0) M[x]=M.size()-1;
			mi[i][M[x]]=min(mi[i][M[x]], j+1);
		}
	}
	
	int ans=mi[0][M.size()-1];
	P.insert(make_pair(0,9*N+1));
	P.insert(make_pair(9*N+1,0));
	R.insert(0);
	for(i=M.size()-1;i>=0;i--) {
		ans=min(ans,mi[0][i]+*R.begin());
		add(mi[1][i],mi[2][i]);
	}
	ans=min(ans,*R.begin());
	cout<<ans<<endl;
}

まとめ

シンプルな問題設定だね。