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][leq] := 下から i 桁目まで見た時,各桁の総和の余りが j であり,かつ N 以下である可能性がある (less equal) 場合の数
としておいて,遷移をする.
この時,最上位に 0 を許容する (leading zero) ことに注意.これは例えば N = 100 にたいして 099 == 99 をカウントすることを意味するためである.

最後に,1 以上 N 以下だから 0 を省く必要がある.

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
constexpr ll MOD = 1e9+7;
 
int main() {
    int D;
    string N;
    cin >> D >> N;
    reverse(N.begin(), N.end());
    vector<vector<vector<ll>>> dp(N.size()+1, vector<vector<ll>>(D, vector<ll>(2)));
    dp[0][0][1] = 1;
    for(int i=0; i<N.size(); ++i) {
        for(int j=0; j<D; ++j) {
            for(int k=0; k<2; ++k) {
                for(int d = 0; d<=9; ++d) {
                    bool leq = d < (N[i] - '0') || k == 1 && d == (N[i] - '0');
                    (dp[i+1][(j + d) % D][leq] += dp[i][j][k]) %= MOD;
                }
            }
        }
    }
    cout << (dp[N.size()][0][1] - 1 + MOD) % 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;
 
int main() {
    ll N, D;
    cin >> N >> D;
    int a[3] = {};
    int div[3] = {2, 3, 5};
    for(int i=0; i<3; ++i) {
        while(D % div[i] == 0) {
            a[i]++;
            D /= div[i];
        }
    }
    if(D > 1) {
        cout << 0 << endl;
        return 0;
    }
    vector<vector<vector<double>>> dp(a[0]+1, vector<vector<double>>(a[1]+1, vector<double>(a[2]+1)));
    dp[0][0][0] = 1;
    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};
    for(int i=0; i<N; ++i) {
        vector<vector<vector<double>>> next(a[0]+1, vector<vector<double>>(a[1]+1, vector<double>(a[2]+1)));
        for(int x=0; x<=a[0]; ++x) {
            for(int y=0; y<=a[1]; ++y) {
                for(int z=0; z<=a[2]; ++z) {
                    for(int l=0; l<6; ++l) {
                        int nx = min(a[0], x+dx[l]);
                        int ny = min(a[1], y+dy[l]);
                        int nz = min(a[2], z+dz[l]);
                        next[nx][ny][nz] += dp[x][y][z] / 6.0;
                    }
                }
            }
        }
        dp.swap(next);
    }
    cout << fixed << setprecision(10) << dp[a[0]][a[1]][a[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 win(int Rp, int Rq) {
    return 1.0 / (1 + pow(10, (double)(Rq - Rp)/400));
}
 
// [l, r]
vector<double> solve(int l, int r, vector<int> const& rating) {
    if(l == r) {
        return vector<double>(1, 1);
    }
 
    const int m = (l + r) / 2;
    auto left = solve(l, m, rating);
    auto right = solve(m+1, r, rating);
    auto res = vector<double>(left.size() * 2);
    for(int i=l; i<=m; ++i) {
        for(int j=m+1; j<=r; ++j) {
            res[i-l] += win(rating[i], rating[j]) * left[i-l] * right[j-(m+1)];
            res[j-l] += win(rating[j], rating[i]) * left[i-l] * right[j-(m+1)];
        }
    }
    return res;
}
 
int main() {
    int K;
    cin >> K;
    vector<int> rating(1 << K);
    for(int i=0; i<1<<K; ++i) {
        cin >> rating[i];
    }
    auto res = solve(0, (1 << K) - 1, rating);
    for(double x : res) {
        cout << fixed << setprecision(10) << x << endl;
    }
}

Typical DP Contest B - ゲーム

解法

漸化式的にも解けるが,メモ化再帰で書くほうがわかりやすいかもしれない.
この場合,minimax法でやる.
memo[l][r] := 左の一番上が l 枚目,右の一番上が r 番目の状態から始めた時の,(先手の得点) - (後手の得点) の最大値(手番が先手の時)または最小値(手番が後手の時)
としてメモ化再帰する.

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
constexpr int INF = 1e9;
 
int rec(int l, int r, int turn, vector<int> const& a, vector<int> const& b, vector<vector<int>>& memo) {
    const int A = a.size();
    const int B = b.size();
    if(l == A && r == B) {
        return memo[A][B] = 0;
    }
    int& res = memo[l][r];
    if(res != INF) {
        return memo[l][r];
    }
    res = (turn == 0 ? -INF : INF);
    if(l < A) {
        res = rec(l+1, r, turn^1, a, b, memo) + (turn == 0 ? a[l] : -a[l]);
    }
    if(r < B) {
        if(turn == 0) {
            res = max(res, rec(l, r+1, turn^1, a, b, memo) + b[r]);
        } else {
            res = min(res, rec(l, r+1, turn^1, a, b, memo) - b[r]);
        }
    }
    return res;
}
 
int main() {
    int A, B;
    cin >> A >> B;
    vector<int> a(A), b(B);
    int sum = 0;
    for(int i=0; i<A; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    for(int i=0; i<B; ++i) {
        cin >> b[i];
        sum += b[i];
    }
    vector<vector<int>> memo(A+1, vector<int>(B+1, INF));
    int t = rec(0, 0, 0, a, b, memo);
    cout << (sum + t) / 2 << endl;
}

Typical DP Contest A - コンテスト

解法

基本的なナップサック問題
p(i), N <= 100 なので,高々 10^6 のループで終わる.

ソースコード

#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;
    for(int i=0; i<N; ++i) {
        for(int j=10000-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 A - コンテスト - すいバカ日誌
Typical DP Contest B - ゲーム - すいバカ日誌
Typical DP Contest C - トーナメント - すいバカ日誌
Typical DP Contest D - サイコロ - すいバカ日誌
Typical DP Contest E - 数 - すいバカ日誌
Typical DP Contest F - 準急 - すいバカ日誌