2017-07-03から1日間の記事一覧

Typical DP Contest F - 準急

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_semiexp 解法 dp[i][j] := i 番目の電車まで考えた時,右端が j である (j=0: 停車, j=1: 通過) 場合の数 として更新していく. 右端で停車しない場合は単純に dp[i-1][0] + dp[i-1][1] でよい. 停車する…

Typical DP Contest E - 数

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_number 解法 いわゆる桁DPというやつ. dp[i][j][leq] := 下から i 桁目まで見た時,各桁の総和の余りが j であり,かつ N 以下である可能性がある (less equal) 場合の数 としておいて,遷移をする. こ…

Typical DP Contest D - サイコロ

問題文 D: サイコロ - Typical DP Contest | AtCoder 解法 サイコロの出た目の積の素因数には 2, 3, 5 しかない. つまり,D にそれ以外の素因数があればダメ. そうでなければ,D = 2^a * 3^b * 5^c と一意的に表すことができる. dp[x][y][z] := 今現在,2…

Typical DP Contest C - トーナメント

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_tournament 解法 まず各山について考える.たとえば,8人いるなら [0, 7], [0, 3], [4, 7], [0, 1], … などが各山にあたる. ある山 X に属する個人が,X の中で優勝する確率と,次に X が対戦することに…

Typical DP Contest B - ゲーム

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_game 解法 漸化式的にも解けるが,メモ化再帰で書くほうがわかりやすいかもしれない. この場合,minimax法でやる. memo[l][r] := 左の一番上が l 枚目,右の一番上が r 番目の状態から始めた時の,(先手…