問題文 http://agc004.contest.atcoder.jp/tasks/agc004_d 解法 首都が自己辺でなければならないのは，すぐ分かる．（ぱっとわからなくても実験すればわかるようになってる．） あとは制約から，与えられたグラフが首都を根とする木になっていることがわかる…

問題文 http://arc006.contest.atcoder.jp/tasks/arc006_3 解法 貪欲解で解くひとが多いと思うので，それ以外の解法を． この問題は，よく考えると「与えられたDAGの最小パス被覆を求めよ」と言い換えられる． 実際，x が y の上に積める，を y -> x という…

問題文 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] でよい． 停車する…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_number 解法 いわゆる桁DPというやつ． dp[i][j][lt] := 上から i 桁目まで見た時，各桁の総和の余りが j であり，かつ N 未満かどうかが lt (less than) のときの場合の数この dp だと 0 が常に条件を満…

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

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

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

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_contest 解法 基本的なナップサック問題． p(i), N ソースコード #include <bits/stdc++.h> using namespace std; constexpr int max_p = 10000; int main() { int n; cin >> n; vector<int> p(n); for(auto& x : p) cin >> x;</int></bits/stdc++.h>…

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

arc070.contest.atcoder.jp 解法（証明？） a[i] を降順にソートする． 今，a[i] が不必要かどうかを判定したいとする．この時，Si := a[1] + a[2] + ... + a_[i] とおく． また，a[n] から a[i + 1] までの和で表現できる K 未満の数がわかっているとする．…