Typical DP Contest F - 準急
解法
dp[i][j] := i 番目の電車まで考えた時,右端が j である (j=0: 停車, j=1: 通過) 場合の数
として更新していく.
右端で停車しない場合は単純に dp[i-1][0] + dp[i-1][1] でよい.
停車する場合は,直前の K-1 回で停車し,かつ駅 1 から駅 i-1 までだけを考えれば条件を満たす場合の数を引く必要がある.
これは dp[i-K][1] で求まる.(直前 K-1 回が停車駅なら,駅 i-K では通過していなければならない)
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr ll MOD = 1e9+7; int main() { int N, K; cin >> N >> K; vector<vector<ll>> dp(N+1, vector<ll>(2)); dp[0][0] = dp[0][1] = 1; for(int i=1; i<=N; ++i) { if(i == 1) { dp[1][0] = 1; dp[1][1] = 0; continue; } dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % MOD; dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % MOD; if(i - K >= 0) { dp[i][0] = (dp[i][0] - dp[i-K][1] + MOD) % MOD; } } cout << dp[N][0] << endl; }
Typical DP Contest E - 数
解法
いわゆる桁DPというやつ.
dp[i][j][lt] := 上から i 桁目まで見た時,各桁の総和の余りが j であり,かつ N 未満かどうかが lt (less than) のときの場合の数
この dp だと 0 が常に条件を満たすので,最後に 1 を引く.
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr int mod = 1e9 + 7; int main() { int d; cin >> d; string n; cin >> n; vector<vector<ll>> dp(d, vector<ll>(2)); dp[0][0] = 1; for(int i = 0; i < (int)n.size(); ++i) { vector<vector<ll>> nxt(d, vector<ll>(2)); const int cur = n[i] - '0'; for(int s = 0; s < d; ++s) { for(int lt = 0; lt < 2; ++lt) { const int lim = lt ? 9 : cur; for(int v = 0; v <= lim; ++v) { const int ns = (s + v) % d; const int nlt = lt | (v < cur); (nxt[ns][nlt] += dp[s][lt]) %= mod; } } } dp = move(nxt); } cout << (dp[0][0] + dp[0][1] + mod - 1) % mod << endl; }
Typical DP Contest D - サイコロ
解法
サイコロの出た目の積の素因数には 2, 3, 5 しかない.
つまり,D にそれ以外の素因数があればダメ.
そうでなければ,D = 2^a * 3^b * 5^c と一意的に表すことができる.
dp[x][y][z] := 今現在,2の素因数が x 個,3 の素因数が y 個,5 の素因数が z 個となる確率
というDPテーブルを考えれば,そこからもう一つサイコロを投げた時の遷移が簡単に書ける.
計算量は O(Nabc) となる.
N <= 100 だが,a, b, c はもっと小さいので余裕で間に合う.(2 ^ 64 で 10^18 を超えてしまう)
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template<typename T> std::vector<T> table(int n, T v) { return std::vector<T>(n, v); } template <class... Args> auto table(int n, Args... args) { auto val = table(args...); return std::vector<decltype(val)>(n, std::move(val)); } constexpr int dx[6] = {0, 1, 0, 2, 0, 1}; constexpr int dy[6] = {0, 0, 1, 0, 0, 1}; constexpr int dz[6] = {0, 0, 0, 0, 1, 0}; int main() { cout << fixed << setprecision(10); ll n, d; cin >> n >> d; vector<int> cnt; for(auto const v : {2, 3, 5}) { int c = 0; while(d % v == 0) { d /= v; ++c; } cnt.push_back(c); } if(d != 1) { cout << 0 << endl; return 0; } auto dp = table(cnt[0] + 1, cnt[1] + 1, cnt[2] + 1, 0.0); dp[0][0][0] = 1; for(int lp = 0; lp < n; ++lp) { auto nxt = table(cnt[0] + 1, cnt[1] + 1, cnt[2] + 1, 0.0); for(int x = 0; x <= cnt[0]; ++x) { for(int y = 0; y <= cnt[1]; ++y) { for(int z = 0; z <= cnt[2]; ++z) { for(int i = 0; i < 6; ++i) { const int nx = min(cnt[0], x + dx[i]); const int ny = min(cnt[1], y + dy[i]); const int nz = min(cnt[2], z + dz[i]); nxt[nx][ny][nz] += dp[x][y][z] / 6; } } } } dp = move(nxt); } cout << dp[cnt[0]][cnt[1]][cnt[2]] << endl; }
Typical DP Contest C - トーナメント
解法
まず各山について考える.たとえば,8人いるなら [0, 7], [0, 3], [4, 7], [0, 1], … などが各山にあたる.
ある山 X に属する個人が,X の中で優勝する確率と,次に X が対戦することになる山 Y の同様の確率が求まるとする.
すると,山 X と Y を統合した山 Z について,Z の中で X および Y に属する個人が勝利する確率を求めることができる.
これをループあるいは再帰で実装すればよい.
計算量は O(K * 2^(2K)).
ソースコード
#include <bits/stdc++.h> using namespace std; double calc_prob(double r1, double r2) { return 1.0 / (1 + pow(10, (r2 - r1) / 400)); } int main() { cout << fixed << setprecision(10); int k; cin >> k; vector<int> R(1 << k); for(auto& x : R) cin >> x; function<vector<double>(int, int)> solve = [&] (int l, int r) { if(r - l == 1) { return vector<double>{1.0}; } vector<double> res(r - l); const int sz = (r - l) / 2; auto l_res = solve(l, l + sz), r_res = solve(l + sz, r); for(int i = 0; i < sz; ++i) { for(int j = 0; j < sz; ++j) { res[i] += calc_prob(R[l + i], R[l + j + sz]) * l_res[i] * r_res[j]; res[j + sz] += calc_prob(R[l + j + sz], R[l + i]) * l_res[i] * r_res[j]; } } return res; }; for(auto&& ans : solve(0, 1 << k)) { cout << ans << endl; } }
Typical DP Contest B - ゲーム
解法
漸化式的にも解けるが,メモ化再帰で書くほうがわかりやすいかもしれない.
この場合,minimax法でやる.
dp[l][r] := 左の一番上が l 枚目,右の一番上が r 番目の状態から始めた時の,(その瞬間の)先手の得点 - 後手の得点の最大値
としてメモ化再帰する.
答えは sum を全カードの総和として (sum + dp[0][0]) / 2 で求まる.
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int inf = 1e9; int main() { int A, B; cin >> A >> B; vector<int> a(A), b(B); for(auto& x : a) cin >> x; for(auto& x : b) cin >> x; const int sum = accumulate(a.begin(), a.end(), 0) + accumulate(b.begin(), b.end(), 0); vector<vector<int>> dp(A + 1, vector<int>(B + 1, -inf)); function<int(int, int)> rec = [&] (int l, int r) { if(dp[l][r] != -inf) return dp[l][r]; if(l == A && r == B) return dp[l][r] = 0; int& res = dp[l][r]; if(l != A) res = a[l] - rec(l + 1, r); if(r != B) res = max(res, b[r] - rec(l, r + 1)); return res; }; cout << (sum + rec(0, 0)) / 2 << endl; }
Typical DP Contest A - コンテスト
解法
基本的なナップサック問題.
p(i), N <= 100 なので,高々 10^6 のループで終わる.
ソースコード
#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; vector<bool> dp(max_p + 1); dp[0] = true; for(int i = 0; i < n; ++i) { for(int j = max_p - p[i]; j >= 0; --j) { dp[j + p[i]] = dp[j + p[i]] | dp[j]; } } cout << count(dp.begin(), dp.end(), true) << endl; }
Typical DP Contest まとめ
Typical DP Contest - Typical DP Contest | AtCoder
Typical DP Contest の全ての問題の解法を書いていきたい.
Typical DP Contest A - コンテスト - すいバカ日誌
Typical DP Contest B - ゲーム - すいバカ日誌
Typical DP Contest C - トーナメント - すいバカ日誌
Typical DP Contest D - サイコロ - すいバカ日誌
Typical DP Contest E - 数 - すいバカ日誌
Typical DP Contest F - 準急 - すいバカ日誌
Typical DP Contest G - 辞書順 - すいバカ日誌
Typical DP Contest H - ナップザック - すいバカ日誌
Typical DP Contest I - イウィ - すいバカ日誌
Typical DP Contest J - ボール - すいバカ日誌
Typical DP Contest K - ターゲット - すいバカ日誌
Typical DP Contest L - 猫 - すいバカ日誌
Typical DP Contest M - 家 - すいバカ日誌
Typical DP Contest N - 木 - すいバカ日誌
Typical DP Contest O - 文字列 - すいバカ日誌
Typical DP Contest P - うなぎ - すいバカ日誌
Typical DP Contest Q - 連結 - すいバカ日誌
Typical DP Contest R - グラフ - すいバカ日誌
Typical DP Contest S - マス目 - すいバカ日誌
Typical DP Contest T - フィボナッチ - すいバカ日誌
・2017/08/27
無事全部解き切りました.一部の問題は自力で解けなかったけど.