問題 Twenty Questions | Aizu Online JudgeN 個の物体で構成された世界がある。これらすべては, M 種類の Yes/No で答えられる特徴で区別することができる。 あなたは, 今目の前にあるものがなんの物体であるかを調べたいのだが, 最悪の場合でもなるべく少…

問題 No.399 動的な領主 - yukicoder 解法 各頂点を通った回数が数えられれば, その頂点で合計かかった金額は, (cnt+1)*cnt/2 と求められます。よって, 各頂点の通った回数を求めることを目標にします。これは tree 上で imos 法をすると解けます。この発想…

問題 No.398 ハーフパイプ(2) - yukicoder 解法 dp します。dp[i][mini][maxi][sum] = (i 番目までで最小値が mini, 最大値が maxi, 合計が sum になっているような場合の数)とします。この dp は状態が O(6*W*W*6*W) で, 遷移に O(W) かかり, 結構計算量が…