Codeforces #915 : Div2 F. Field Should Not Be Empty

コード量は短い。
https://codeforces.com/contest/1905/problem/F

問題

1～NのPermutation Pが与えられる。
添え字xがGoodであるというのは、y＜xならP[y]＜P[x]、y＞xならP[y]＞P[x]であることをいう。

2要素のswapをちょうど1回だけ行うとき、Goodな添え字の最大値を求めよ。

解法

GoodであるP[x]=xで
Goodな添え字の増えるswapは以下の高々2N通り。

• P[i]とP[P[i]]をswapすると、旧P[i]がGoodになる可能性がある。
• iに対し、P[0]...P[i-1]の最小値をP[k]、P[i+1]...P[N-1]の最大値をP[j]とすると、iがGoodになる可能性がある。

これらを愚直に試そう。

int T,N,P[202020];
int Rmi[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		int ok=0;
		map<pair<int,int>,int> M;
		for(i=1;i<=N;i++) cin>>P[i];
		Rmi[N+1]=N+1;
		for(i=N;i>=1;i--) Rmi[i]=min(Rmi[i+1],P[i]);
		
		int ma1=0,ma2=0;
		for(i=1;i<=N;i++) {
			if(P[i]>ma1) ma2=ma1, ma1=P[i];
			else ma2=max(ma2,P[i]);
			
			if(ma1==P[i]&&P[i]==i) ok++;
			//iの左側の最大値を右側の最小値をswapして1cost増
			if(P[i]==i&&ma1>i&&ma2==i) M[{Rmi[i+1],ma1}]++;
			//左にiがあるので持ってくる
			if(P[i]<i&&ma1==i) M[{P[i],i}]++;
			//P[i]がiより大きく、左側はi未満なので、iを持ってくる
			if(P[i]>i&&ma2<i) M[{i,P[i]}]++;
			
			
		}
		int ret=-2;
		FORR2(a,b,M) ret=max(ret,b);
		
		cout<<ok+ret<<endl;
		
		
		
	}
}

まとめ

考察が済めばコードは短め。