Codeforces #945 : Div2 E. Cat, Fox and Swaps

あいにく解けず…。
https://codeforces.com/contest/1973/problem/E

問題

1～NのPermutation Pが与えられる。
以下を満たす整数対(L,R)は何通りか。

• 1≦L≦R≦2*N
• P中の2値x,yは、L≦x+y≦Rならswapできるとき、Pを昇順にソートできる。

解法

まずコーナーケースとして、Pがソート済みならL,Rは何でもよい。
次にL=Rのケースを考える。
この時各値に対し、swap可能な値は1個しかない。
i≠P[i]なら、L=i+P[i]とならなければならない。

よって、i≠P[i]なiに対するi+P[i]の集合が

• 0通りなら、L=R=1～2Nがすべて解になる
• 1通りなら、L=R=i+P[i]が解になる
• 2通り以上なら、L=Rとなるケースはない。

以後、L＜Rのケースを考える。

MLはML≠P[ML]となる最小値、MRはMR≠P[MR]とする。
MLとMRが別の値とswapできないといけないので、この時、1≦L≦ML+N、max(L,MR)+1≦Rでなければならない。
Lを総当たりしながら、条件を満たすRの下限を求めて行けばよい。

int T,N,P[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		set<int> S;
		int minL=N+1,maxR=0;
		for(i=1;i<=N;i++) {
			cin>>P[i];
			if(i!=P[i]) {
				S.insert(i+P[i]);
				maxR=max(maxR,i);
				minL=min(minL,i);
			}
		}
		if(maxR==0) {
			cout<<1LL*2*N*(2*N+1)/2<<endl;
			continue;
		}
		
		ll ret=0;
		if(S.size()==1) ret++;
		else if(S.empty()) ret+=2*N;
		for(int L=1;L<=minL+N;L++) {
			x=max(maxR+1,L+1);
			ret+=2*N+1-x;
		}
		
		
		cout<<ret<<endl;
	}
}

まとめ

終わってみればコードは単純だな…。