Codeforces #1082 : Div1 A2. Lost Civilization (Hard Version)

ちょっと微妙な出来だった回。
https://codeforces.com/contest/2201/problem/A2

問題

整数列Xに対し、以下の処理を行うことができるとする。

• Xの１要素X[i]を選び、X[i]+1を末尾に追加する。

f(Y)を、上記処理を繰り返してYを作れる最小の配列長とする。

整数列Aが与えられる。
Aの全部分列A'におけるf(A')の総和を求めよ。

解法

A[x]が、他の要素から生成できるかどうかを考える。
手前にA[y]=A[x]-1があり、またA[x+1]以降がすべて多要素からら生成できるなら、A[x]はA[y]から生成できるため、初期状態で不要となる。

int T,N,A[303030];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		vector<int> V;
		ll ret=0;
		FOR(i,N) {
			cin>>x;
			V.push_back(x);
			ret+=1LL*(i+1)*(N-i);
		}
		deque<pair<int,int>> D;
		FOR(i,N-1) {
			D.push_front({V.back(),N-1-i});
			x=N-2-i;
			V.pop_back();
			while(D.size()&&V.back()+1==D[0].first) {
				y=D[0].second;
				ret-=1LL*(x+1)*(N-y);
				D.pop_front();
			}
		}
		cout<<ret<<endl;
	}
}

まとめ

本番意外にさっくり解いてる。