kmjp's blog

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

yukicoder : No.127 門松もどき

yukicoder

難しく考えすぎて遠回り。
http://yukicoder.me/problems/293

問題

N個の竹が一列に並んでおり、それぞれの高さはA[i]である。
竹番号を1～Nとして、その番号の部分列 i_1, i_2, ..., i_Mが門松列を成すとは、 A_{i_1} \gt A_{i_M} \gt A_{i_2} \gt A_{i_{M-1}} \gt ...もしくは A_{i_M} \gt A_{i_1} \gt A_{i_{M-1}} \gt A_{i_2} \gt ... のいずれかを成すものを指す。

A[i]に対し門松列の最大長を求めよ。

解法

連続した部分列A[x..(x+l)]において、以下の２値を更新していく。

  • A[x...(x+l)]のうち左端であるx=i_1かつA[x]が門松列中最小値となるような門松列の最大長L[x][x+l]
  • A[x...(x+l)]のうち右端であるx+l=i_MかつA[x+l]が門松列中最小値となるような門松列の最大長R[x][x+l]

以下の事実より、幅lを一つずつ広げながらDPしていけば良い。

  • L[x][x+l]=max(L[x][x+m]) (m < l)
    • A[x] < A[x+l]のとき、L[x][x+l]=R[x+1][x+l]+1 で最大値更新
  • R[x][x+l]=max(L[x+m][x+l]) (m < l)
    • A[x] > A[x+l]のとき、R[x][x+l]=L[x][x+l-1]+1 で最大値更新
int N;
int A[10101];
int dp[2][3030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	int ma=1;
	
	cin>>N;
	FOR(i,N) cin>>A[i], dp[0][i][i]=dp[1][i][i]=1;
	
	for(i=1;i<=N;i++) for(x=0;x+i<N;x++) {
		dp[1][x][x+i] = max(dp[1][x][x+i],dp[1][x][x+i-1]);
		dp[0][x][x+i] = max(dp[0][x][x+i],dp[0][x+1][x+i]);
		if(A[x]<A[x+i]) dp[1][x][x+i] = max(dp[1][x][x+i],dp[0][x+1][x+i]+1);
		if(A[x]>A[x+i]) dp[0][x][x+i] = max(dp[0][x][x+i],dp[1][x][x+i-1]+1);
		ma=max(ma,dp[1][x][x+i]);
		ma=max(ma,dp[0][x][x+i]);
	}
	cout<<ma<<endl;
	
}

まとめ

O(N^3)はすぐ思いついて、そこから探索量を減らそうと頑張ってしまったな…。
そのままでもO(N^2*logN)位で解けそうだけど、無駄に頑張りすぎた。