AtCoder

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 番目の状態から始めた時の,(先手…

Typical DP Contest A - コンテスト

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_contest 解法 基本的なナップサック問題. p(i), N ソースコード #include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<int> p(N); for(int i=0; i<N; ++i) { cin >> p[i]; } vector<bool> dp(10001); dp[0] = true;</bool></n;></int></bits/stdc++.h>…

Typical DP Contest まとめ

Typical DP Contest の全ての問題の解法を書いていきたい.Typical DP Contest A - コンテスト - すいバカ日誌 Typical DP Contest B - ゲーム - すいバカ日誌 Typical DP Contest C - トーナメント - すいバカ日誌 Typical DP Contest D - サイコロ - すい…

ARC070 D - No Need

arc070.contest.atcoder.jp 解法(証明?) を降順にソートする. 今, が不必要かどうかを判定したいとする.この時, とおく. また, から までの和で表現できる 未満の数がわかっているとする.(dpで保存) その中の任意の数 について, であるならば,…