Codeforces #699 Div2 : E. Sorting Books

ようやく600番台が終わる…。
https://codeforces.com/contest/1481/problem/E

問題

N要素の整数列Aが与えられる。
任意の順で、選択した要素を末尾に移動することを繰り返し、同じ値の要素が連続するようにしたい。
最小何個の要素を末尾に移動すればよいか。

解法

dp(i) := 先頭i個目までを考えたとき、条件を満たすよう末尾に移動する要素数の最小値

状態遷移は以下の2つ。

• (i+1)個目を末尾に移動すると決めたとき、dp(i+1)=dp(i)+1
• A[i+1]が、A中で初出の場合、A[i+1]と同じ要素を残すことを考える。
  • この時、A[i+1]と同じ値を持つ最大の添え字をjとすると、A[i+1]....A[j]のうち、A[i+1]と異なる値は全部末尾に移動しなければいけないので、dp(j)が計算できる。

int N;
int A[505050];
vector<int> P[505050];
int dp[505050];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		dp[i+1]=1<<20;
		cin>>A[i];
		A[i]--;
		P[A[i]].push_back(i);
	}
	int ret=N;
	FOR(i,N) {
		//not take
		dp[i+1]=min(dp[i+1],dp[i]+1);
		//take
		r=A[i];
		x=lower_bound(ALL(P[r]),i)-P[r].begin();
		if(x==0) {
			dp[P[r].back()+1]=min(dp[P[r].back()+1],dp[i]+(P[r].back()-i)-((int)P[r].size()-x-1));
		}
		else {
			ret=min(ret,dp[i]+(N-1-i)-((int)P[r].size()-x-1));
		}
		ret=min(ret,dp[i+1]+N-1-i);
	}
	cout<<ret<<endl;
}

まとめ

Div2Eの割にはコードが短め。