Cまで三完。
E. Arena
ツイッターでDPの定義を見てAC。
・DP[i][j]=残りi人で、残った一人の最大値がjのとき一人だけが勝つ場合の数、とする。
答えは、DP[n][1...x]を全体から引いたもの。
遷移は、最大値がi-1だけ減るので、そのとき何人いなくなるかで場合分け。k人いなくなるなら、pow(i-1, k)*Combi(i, k)を掛ける。
計算量は三乗だと思うけど、定数倍が小さくなるのでOK。
DPを疑うのは自然だし、分かってしまえばDPの定義も自然に思えるけど、思いつけなかったね……。
0 件のコメント:
コメントを投稿