Typical DP Contest : A - コンテスト、B - ゲーム、C - トーナメント

TDPCに参加。
Fまでは順調に解いてGもなんとか２時間ちょいで解いたけど、その後Iのバグが取れず若干違う問題もチャレンジしたけどGまでで打ち止め。
うーん、後で解いたところJやLは自力で解けたな…同じ配点ということで無理に前から解こうとしたのが失敗。
まだLまでしか解いてないけど徐々に復習開始。
http://tdpc.contest.atcoder.jp/tasks/tdpc_contest
http://tdpc.contest.atcoder.jp/tasks/tdpc_game
http://tdpc.contest.atcoder.jp/tasks/tdpc_tournament

A - コンテスト

N問の問題はそれぞれP[i]点である。
取りうる得点を答える問題。
N<=100、P[i]<=100なので、0～10000点まででとの得点の可能性の有無をDPするだけ。O(PN^2)。

int N,dp[10001];

void solve() {
	int f,r,i,j,k,l, x,y;
	
	dp[0]=1;
	N=GETi();
	FOR(i,N) {
		x=GETi();
		for(y=10000;y>=0;y--) if(dp[y]) dp[y+x]=1;
	}
	
	y=0;
	FOR(x,10001) if(dp[x]) y++;
	_P("%d\n",y);
	return;
}

B - ゲーム

２つの山それぞれ、i番目の物の価値をA[i]、B[i]とする。
２人交互にどちらかの山を選択し、最上位の物を取って行く。
先手・後手が最適戦略を取ったとき、先手の取れる価値を最大化せよ。

２つの山の残った物の数でDP。ここではメモ化再帰で処理。O(AB)。

int A,B;
int AA[1001],BB[1000];
int memo[2][1001][1001];
int dpdp1(int na,int nb) ;
int dpdp2(int na,int nb) {
	if(na==0 && nb==0) return 0;
	
	if(memo[1][na][nb]==-1) {
		if(na==0) memo[1][na][nb] = dpdp1(na,nb-1);
		else if(nb==0) memo[1][na][nb] = dpdp1(na-1,nb);	
		else memo[1][na][nb] = min(dpdp1(na-1,nb),dpdp1(na,nb-1));
	}
	return memo[1][na][nb];
	
}

int dpdp1(int na,int nb) {
	
	if(na==0 && nb==0) return 0;
	
	if(memo[0][na][nb]==-1) {
		if(na==0) memo[0][na][nb] = BB[B-nb] + dpdp2(na,nb-1);
		else if(nb==0) memo[0][na][nb] = AA[A-na] + dpdp2(na-1,nb);
		else memo[0][na][nb] = max(AA[A-na]+dpdp2(na-1,nb),BB[B-nb]+dpdp2(na,nb-1));
	}
	return memo[0][na][nb];
}

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>A>>B;
	FOR(i,A) AA[i]=GETi();
	FOR(i,B) BB[i]=GETi();
	MINUS(memo);
	
	_P("%d\n",dpdp1(A,B));
	return;
}

C - トーナメント

レートがPとQの人が戦うと、レートPの人はの確率で勝つ。
2^N人それぞれのレートR[i]が与えられるとき、それぞれが優勝する確率を答えよ。

i番目がM回戦にたどり着く確率をA[i]とすると、M+1回戦にたどり着く確率はM回戦で戦う人jについてとなる。
後は順に決勝戦まで処理していけばよい。O(N×(2^N)^2)程度なので結局O(N×2^N)か。

int K,N;
int R[2000];
double rate[2000][2000];
double RR[11][2000];

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>K;
	N=1<<K;
	FOR(i,N) R[i]=GETi();
	
	FOR(x,N) FOR(y,N) rate[x][y]=1.0/(1.0+pow(10,(R[y]-R[x])/400.0));

	FOR(i,N) RR[0][i]=1;
	FOR(i,K) {
		x = 1<<i;
		FOR(j,N) {
			FOR(y,x) {
				int tar = (j/(2*x))*(2*x);
				if(j%(2*x)<x) tar += x;
				tar += y;
				
				RR[i+1][j] += RR[i][tar]*rate[j][tar];
			}
			RR[i+1][j] *= RR[i][j];
		}
	}
	
	FOR(i,N) _P("%.12lf\n",RR[K][i]);
	return;
}

まとめ

思ったより難易度上昇が激しかった。
配点１点分位難易度が想定と違うな…。