AtCoder ARC #206 : B - Slime Swap

前半から割と手間取った…。
https://atcoder.jp/contests/arc206/tasks/arc206_b

問題

N体のスライムが並んでおり、それぞれのサイズと色が与えられる。
隣接するスライムは、色が異なればswap可能である。

初期状態で指定したスライムの色を変えられるとする。
全スライムをサイズ順に並べたい場合、最少何体のスライムの色を変えればよいか。

解法

元々色が異なるスライムは互いに任意にswap可能なので、それらの間の関係は無視してよい。
あとは、同じ色のスライムについて、いくつかのスライムの色を変えてサイズ順に並べ替えられるようにしたい。

このスライムのサイズからなる数列について、LISを求めれば、LISに該当しない要素に対応するスライムの色を変えればよいことになる。

int N;
int P[202020],C[202020];

vector<int> V[202020];

template<class CC> int LIS_num(vector<CC>& v) {
	int i,N=v.size();
	if(v.empty()) return 0;
	vector<CC> dp(N,(numeric_limits<CC>::max)()),id(N);
	FOR(i,v.size()) dp[id[i]=lower_bound(dp.begin(),dp.end(),v[i]) - dp.begin()] = v[i];
	// FOR(i,v.size()) dp[id[i]=lower_bound(dp.begin(),dp.end(),v[i]) - dp.begin()] = v[i]-1; 同じ数値の連続も許可する場合
	return *max_element(id.begin(),id.end())+1;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i];
	FOR(i,N) {
		cin>>C[i];
		V[C[i]].push_back(P[i]);
	}
	ll ret=0;
	FOR(i,N+1) ret+=1LL*i*(V[i].size()-LIS_num(V[i]));
	cout<<ret<<endl;
}

まとめ

意外と時間かかってしまった。