そういやここらへんはデータが吹っ飛んだ時か…。
http://codeforces.com/contest/392/problem/D
問題
3つの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)の組み合わせを考えると、2次元座標第1象限において原点を含む凸図形を除いた形状になる。
その凸図形における(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; }
まとめ
シンプルな問題設定だね。