kmjp's blog

競技プログラミング参加記です

AtCoder ABC #262 (第三回日本最強プログラマー学生選手権-予選-) : G - LIS with Stack

どうにか通せた。
https://atcoder.jp/contests/abc262/tasks/abc262_g

問題

空の数列X、空のスタックSとN要素の数列Aが与えられる。
Aの要素aに対し、順に以下の処理を行う。

  • aを捨てる
  • aをSにpushする

また、途中任意のタイミングでSの内容をpopしてXに追加できる。

Xを単調増加列になるようにするとき、最大要素数を求めよ。

解法

f(L,R,min,max) := Aの部分列A[L...(R-1)]に対し、問題の手順で構成できるXのうち、最小値がmin以上、最大値がmax以下である最大要素数
とする。求めたいのは、f(0,N,min(A),max(A))である。

f(L,R,min,max)に対し以下の状態分岐が考えられる。

  • 先頭要素を捨て、f(L+1,R,min,max)を考える
  • 部分列を2つに分割し、f(L,M,min,mid)+f(M,R,mid,max)の最大値を考える。M,midは総当たりする。
  • 先頭要素を最初にXに入れ、1+f(L+1,R,A[L],max)を考える。
  • 先頭要素を最後にXに入れ、1+f(L+1,R,min,A[L])を考える。

fは状態としてO(N^4)、状態遷移はO(N^2)通りあり、愚直に行うとO(N^6)かかりちょっと時間が短い。
ただ、A[L..(R-1)]に対し、有効なmin,maxの値はA[L...(R-1)]に含まれるものだけなので、このことを利用して状態数を減らすとO(N^6)でも何とか通る。

int N,A[55];
int tma[55][55][55];
int tmi[55][55][55];
int memo[55][55][55][55];

int hoge(int L,int R,int mi,int ma) {
	if(L>=R) return 0;
	mi=tmi[L][R][mi];
	ma=tma[L][R][ma];
	if(mi>ma) return 0;
	if(memo[L][R][mi][ma]>=0) return memo[L][R][mi][ma];
	int ret=0;
	
	//削除
	ret=max(ret,hoge(L+1,R,mi,ma));
	//分割
	int M,m;
	for(m=mi;m<=ma;m++) for(M=L+1;M<R;M++) ret=max(ret,hoge(L,M,mi,m)+hoge(M,R,m,ma));
	//最初に取るか最後に取る
	if(A[L]>=mi&&A[L]<=ma) {
		ret=max(ret,1+hoge(L+1,R,A[L],ma));
		ret=max(ret,1+hoge(L+1,R,mi,A[L]));
	}
	
	return memo[L][R][mi][ma]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	FOR(x,N) {
		for(y=x+1;y<=N;y++) {
			for(i=1;i<=50;i++) {
				int t=-1;
				for(k=x;k<y;k++) if(A[k]<=i) t=max(t,A[k]);
				tma[x][y][i]=t;
				t=55;
				for(k=x;k<y;k++) if(A[k]>=i) t=min(t,A[k]);
				tmi[x][y][i]=t;
			}
		}
	}
	
	
	MINUS(memo);
	cout<<hoge(0,N,1,50)<<endl;
	
}

まとめ

O(N^6)で通ってびっくり。