CODE FESTIVAL 2014 決勝 : D - パスカルの三角形、E - 常ならずグラフ

一瞬考えるけど、落ち着くと簡単な問題。
http://code-festival-2014-final-open.contest.atcoder.jp/tasks/code_festival_final_d
http://code-festival-2014-final-open.contest.atcoder.jp/tasks/code_festival_final_e

D - パスカルの三角形

f(y,x)をパスカルの三角形で上からy段目、左からx個目の数値とする。
整数Aが与えられるので、f(y,x)=Aとなるy,xを答えよ。

なので、となる。

void solve() {
	int i,j,k,l,r,x,y; string s;
	ll A;
	cin>>A;
	_P("%lld %lld\n",A+1,2LL);
}

E - 常ならずグラフ

N要素の数列R[i]が与えられる。
Rの部分列R'[i]のうち、要素同士の大小関係がジグザグとなる最長の部分列の要素数を答えよ。

自分はdp[要素番号][直前は数値が上昇中か下降中か]を状態として要素数の最大値を保持してDPした。
Greedyにジグザグとなる要素だけを順次R'[i]に追加していく方法もあるようだ。

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

まとめ

ここらへんはまだまだいける。