問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_concatenation 解法 同じ文字列を複数選んでも良いので，何を使ったかを保存する必要はないです． 今作っている文字列の状態がどうか，がわかれば十分．そこで突然ですが，以下のような dp をします． dp[…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_graph 解法 どう考えても閉路は一つにまとめたいな～という気持ちになるので，とりあえずSCCしたあとのDAGの上で解くことを考えます． 一番端っこから引いていくのが当然良いので，トポロジカルソートして…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_eel 解法 木の上でのDPなので，やはり根を適当に決めたあとのDFS木上で，部分木の結果を統合していくのが鉄則となります．根として適当に頂点 0 を選んで，そのDFS木上で考えます． 以下のような dp を考…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_fibonacci 解法 今なら，通称きたまさ法とよばれている方法でやります． きたまさ法自体の説明は省略します．アイデアとしては，一般項を最初の K 項の線形結合で表そう，というものです． ソースコード #…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_grid 解法 まず，この問題を解くにあたって以下の記事を大いに参考にさせていただきました．ありがとうございます． algoogle.hadrori.jpH が小さいので，それぞれのマスの連結関係をもちながら，列を左か…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_house 解法 まず階段を使うまえに，各階で部屋i -> j の移動経路が何パターンあるかを計算します． これは普通に dp[S][i][j] := 今まで訪れた部屋の集合が S である，i -> j の移動パターン とすれば求め…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_target 解法 それぞれの円の左端と右端のpairである (x + r, x - r) を昇順ソートする． そのあと，-(x - r) についての最長増加部分列（ (x - r) のまま考えるなら，最長減少部分列．右から左の向き）を…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_lexicographical 解法 まず， next_pos[i][c] := i番目以降で，文字 c があらわれる一番前の位置 とします． ここで，dp[i] を dp[i] := i 番目の文字を「使った上で」，i 番目以降のユニークな文字列は何…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_string 解法 dp[i][j] := i 番目の文字まで見た時，同じ文字が連続している場所が j 箇所あるような場合の数 とする． 例えば，AABBBCDEE なら，連続している箇所は4箇所と数える．次に追加する文字が f[i…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_ball 解法 期待値を求める問題．bitDP か線形方程式を解くところだが，|S| = 1024 なので後者は厳しい．なので bitDP を疑う．ただし、このためには遷移をDAGにしないといけない。dp[S] := すでに倒れたも…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_tree 解法 まず，一番最初に書き始める辺を定めることを考える． そして，定めた辺を縮約したグラフ上で，以下の問題を解けば良い． 「縮約してできた頂点を根として，そこから辺を生やしていく方法は何通…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_knapsack 解法 まず，色でソートしておく． すると以下の dp が書ける． dp[i][w][j][k] := i 番目まで見たとき，j 種類の色を使っていて，最後に使った色が k であって，重さの総和が w となるときの最大…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_cat 解法 1 1つは今見ているのが何番目かに使うとして，もう1つを何にするかが問題．自分は，どの猫まで距離1以内に配置するか，と考えた．つまり dp[i][j] := i 番目の猫まで考えた時，i 番目の猫は"自分…

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi 解法 区間DP．dp[l][r] := [l, r) で最大何文字取り除けるか と定義する． まず，dp[l][r] = max(dp[l][i] + dp[i][r]) (i = l, ..., r) という遷移は，明らかだと思う． あとは，s[l...r) が完全に取…

問題文 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 - トーナメント - す…