Codeforces ECR #119 : F. Bipartite Array

FよりGの方が易しい。
https://codeforces.com/contest/1620/problem/F

問題

N要素の順列Pが与えられる。
ここで以下のグラフを考える。

• N点からなる。
• i＜jかつP[i]＞P[j]の場合、i番とj番の点に辺を張る。

各要素の符号を反転できるとき、二部グラフを構築可能か判定せよ。

解法

Pの3要素の部分列に、降下列があると長さ3の閉路ができるので二部グラフにならない。
dp(i,x,y) := i要素目まで決めたとき、最大値がx、長さ2の降下列の2要素目の最大値yとなる取り方があるかどうか

このままだとO(N^3)かかるので、何とか状態を減らす。
まずbool値で状態を持つのは無駄なので、xまたはyの最小値を値として取るようにする。
次に、P[i-1]または-P[i-1]のいずれかは必ずxかyに入る。
よって、P[i-1]の符号と、x,yどちらに入るかを持つようにすると、状態がO(N)通りで済むようになる。

int T;
int N;
int P[1010101];

pair<int,int> from[1010101][2][2];
int dp[1010101][2][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&N);
		FOR(i,N) scanf("%d",&P[i]);
		
		FOR(i,N) dp[i][0][0]=dp[i][0][1]=dp[i][1][0]=dp[i][1][1]=1LL<<30;
		dp[0][0][0]=dp[0][0][1]=-1LL<<30;
		
		int pos,sig,ns;
		FOR(i,N-1) FOR(pos,2) FOR(sig,2) if(dp[i][pos][sig]<1<<30) {
			if(pos==0) {
				x=(sig?-P[i]:P[i]);
				y=dp[i][pos][sig];
			}
			else {
				x=dp[i][pos][sig];
				y=(sig?-P[i]:P[i]);
			}
			FOR(ns,2) {
				int v=ns?-P[i+1]:P[i+1];
				
				if(v>x) {
					if(chmin(dp[i+1][0][ns],y)) from[i+1][0][ns]={pos,sig};
				}
				else if(v>y) {
					if(chmin(dp[i+1][1][ns],x)) from[i+1][1][ns]={pos,sig};
				}
			}
		}
		pos=sig=-1;
		FOR(x,2) FOR(y,2) if(dp[N-1][x][y]<1<<30) pos=x, sig=y;
		if(pos==-1) {
			cout<<"NO"<<endl;
		}
		else {
			for(i=N-1;i>=0;i--) {
				if(sig) P[i]=-P[i];
				auto p=from[i][pos][sig];
				pos=p.first;
				sig=p.second;
			}
			cout<<"YES"<<endl;
			FOR(i,N) cout<<P[i]<<" ";
			cout<<endl;
		}
		
	}
	
	
}

まとめ

言われてみるとそこまで難しいことしてないんだけど、本番さっと思いつくのが難しい。