CODE FESTIVAL 2016 Qual A : E - LRU パズル / LRU Puzzle

コード量はDよりずっと少ない。
http://code-festival-2016-quala.contest.atcoder.jp/tasks/codefestival_2016_qualA_e

問題

初期状態でN個の整数列群があり、いずれも1～Mが順に並んでいる。
この整数列群に対し、Q個の処理を行う。

各処理は整数A[i]で示される。
N個の整数列群のうち１つの数列を選択し、整数列中のA[i]を先頭に持ってくる、という処理を繰り返す。

Q個の処理を行った後、全数列の並びが等しくなるようにできるか。

解法

全ての処理を１つの数列に行った場合を考える。
同じ数値を何度も先頭に持ってくることもあるが、得られる結果は以下のようになる。

• A[i]を逆順に見て、現れた数値が初登場ならその数値を答えの数列の前から順に並べる。
• Aを全部みても登場しない数値は、その後数列の末尾に順次追加していく。

N個の整数に処理を散らした場合、その結果は上記全処理を１つの数列に行った場合と等しくなければならない。
そこで、各数列が先頭何個目まで上記数列と一致するかを管理し、A[i]をやはり逆順に見て一致する数を１つずつ増やしていくとよい。

以下のコードでは、「全ての処理を１つの数列に行った場合」を求めた後、末尾の単調増加の部分を削除し、そこまでの数列をN個分作るようにしている。

int N,M,Q;
int A[101010];
int did[101010];
int ind[101010];
vector<int> V;
int num[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>Q;
	FOR(i,Q) cin>>A[i];
	for(i=Q-1;i>=0;i--) {
		did[A[i]]++;
		if(did[A[i]]==1) {
			ind[A[i]]=V.size();
			V.push_back(A[i]);
		}
	}
	FOR(i,M) if(did[i+1]==0) {
		ind[i+1]=V.size();
		V.push_back(i+1);
	}
	
	while(V.size()>=2 && V[V.size()-2]<V[V.size()-1]) V.pop_back();
	V.pop_back();
	
	num[0]=N;
	for(i=Q-1;i>=0;i--) if(num[ind[A[i]]]) {
		num[ind[A[i]]]--;
		num[ind[A[i]]+1]++;
	}
	
	FOR(i,V.size()) if(num[i]) return _P("No\n");
	_P("Yes\n");
}

まとめ

Dで時間使いすぎて本番は考察する時間もなかった。