Codeforces #637 Div1 A. Nastya and Strange Generator

ここはCを落としてもったいなかった。
http://codeforces.com/contest/1340/problem/A

問題

1～Nの順列を以下の手順で作ることを考える。
初期状態で対象の数列は空とする。

• i番目のステップでは、iをどこに埋めるかを考える。
  • 各要素jについて、右方向で最寄りの未確定の要素番号R[j]を求める。
  • 各要素kについて、R[j]=kであるようなjの数をC[k]とする。
  • C[k]が最大となる要素にiを埋める。同着が複数あるなら、任意の場所を選べる。

今、順列が与えられたとき、上記手順でその順列を作れるか判定せよ。

解法

一端ある値をある要素に置くと、次の値はその右隣に置くことになる。
よってこの数列は、1～aの左に(a+1)～bが来て、その左に(b+1)～cが来て…というような並びになる。
そこで、入力がそのような形になっているか確認しよう。

int T;
int N;
int P[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		map<int,int> M;
		multiset<int> ma;
		FOR(i,N) {
			cin>>x;
			P[x-1]=i;
			M[i]=1;
			ma.insert(1);
		}
		
		FOR(i,N) {
			x=*ma.rbegin();
			if(M[P[i]]!=x) break;
			ma.erase(ma.find(x));
			M.erase(P[i]);
			auto it=M.lower_bound(P[i]);
			if(it!=M.end()) {
				ma.erase(ma.find(it->second));
				it->second+=x;
				ma.insert(it->second);
			}
		}
		if(i==N) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

まとめ

Aから問題文が長いとしんどい。