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
無事全部解き切りました.一部の問題は自力で解けなかったけど.