CODE FESTIVAL 2014 決勝 - E : 常ならずグラフ

・概要
E: 常ならずグラフ - CODE FESTIVAL 2014 決勝 | AtCoder

数列が与えられるので、大小がジグザグになるように数列の要素をいくつか削る。その削って条件をみたすようになったグラフのうちで要素が最も多いものの要素の個数を求める。

・アイデア
数列の形としては、
x1 < x2 > x3 < x4 > ...
x1 > x2 < x3 > x4 < ...
のどちらか２通り。削るべき区間は、連続して大きくなっているところや、連続して小さくなっているということになる。その部分に関しては始点と終点を残して削る。このとき始点と終点を残す理由は、例えば上がっていく区間を見て、終点についた時、次は必ず終点より小さい値が来る。そのとき区間内の途中の値だと、大小関係が正しくならないおそれがあるからである。

ex.) 2 (<) 4 (<) 6 (<) 9 (>) 7 (>) 3 (<) 5
このようなときは、2,9,3,5と選ぶのがよい。

そして、上の２通りの両方をgreedyに試せば良い。時間計算量はO(N)。N<=3000なので余裕で間に合う。このサイズをみて、何らかのDPかなと思ってしまうが、これでできるから良い。
最後の要素に関する処理は次の要素がないので、完成する部分列の直前の要素と比べている点は注意。
vectorを使って数列を実際に作り上げなくても、要素の数え上げで行けるのだろうけど、直観的にやりやすいし、要素数も簡単に出せるので使ってみた。

・実装(C++)

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

int main(){
	int n, r[3000];
	
	cin >> n;
	for(int i=0; i<n; ++i) scanf(" %d", &r[i]);
	
	vector<int> r1,r2;
	//x1 < x2 > x3 < x4 > ...の形
	bool large=true;
	
	int revtmp=0;
	for(int i=0; i<n-1; ++i){
		if(large && r[i]<r[i+1]){
			large=false;
			r1.push_back(r[i]);
		}
		else if(!large && r[i]>r[i+1]){
			large=true;
			r1.push_back(r[i]);
		}		
	} 
	//printf("large ? %d\n", large);
	if(r1.size()!=0){
		if(!large && r1[r1.size()-1]<r[n-1]) r1.push_back(r[n-1]);
		else if(large && r1[r1.size()-1]>r[n-1]) r1.push_back(r[n-1]);
	}
	
	//x1 > x2 < x3 > x4 < ...の形
	large=false;
	for(int i=0; i<n-1; ++i){
		if(large && r[i]<r[i+1]){
			large=false;
			r2.push_back(r[i]);
		}
		else if(!large && r[i]>r[i+1]){
			large=true;
			r2.push_back(r[i]);
		}
	} 
	if(r2.size()!=0){
		if(!large && r2[r2.size()-1]<r[n-1]) r2.push_back(r[n-1]);
		else if(large && r2[r2.size()-1]>r[n-1]) r2.push_back(r[n-1]);
	}
	/*
	for(int i=0; i<r1.size(); ++i){
		printf(" %d: %d\n", i, r1[i]);	
	}
	printf("\n");	
	for(int i=0; i<r2.size(); ++i){
		printf(" %d: %d\n", i, r2[i]);	
	}
	printf("\n");
	*/
	
	int ans=max(r1.size(),r2.size());
	if(ans<3) ans=0;
	printf("%d\n",ans);
}

・感想
CODE FESTIVAL 決勝参加が決定したので、去年の問題を解いてみようと思いやってみた。5問は解けないと人権がなさそうな感じのstatsだったのでとりあえずここまで出来て安心した。ちなみに、D問題がとてもおもしろかった(D: パスカルの三角形 - CODE FESTIVAL 2014 決勝 | AtCoder)。これは典型的なDPだと思いきや、そんなことをやっていたら時間がかかりすぎて間に合いませんよっていうひっかけだった。
Combinationは "nC1 = n" なので、これを使えばO(1)で答えが出せるっていう(Submission #551324 - CODE FESTIVAL 2014 決勝 | AtCoder)。当日が来るまでちょっとでもスキル上げて人並みにはできるように頑張りたい...