TDPCに参加。
Fまでは順調に解いてGもなんとか2時間ちょいで解いたけど、その後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 - ゲーム
2つの山それぞれ、i番目の物の価値をA[i]、B[i]とする。
2人交互にどちらかの山を選択し、最上位の物を取って行く。
先手・後手が最適戦略を取ったとき、先手の取れる価値を最大化せよ。
2つの山の残った物の数で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; }
まとめ
思ったより難易度上昇が激しかった。
配点1点分位難易度が想定と違うな…。