Typical DP Contest P - うなぎ

競プロ TDPC AtCoder

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_eel

解法

木の上でのDPなので，やはり根を適当に決めたあとのDFS木上で，部分木の結果を統合していくのが鉄則となります．

根として適当に頂点 0 を選んで，そのDFS木上で考えます．
以下のような dp を考えます．
dp[v][i][j] := 根が v となるような部分木で，i 個の disjoint なパスを書き，かつ v の次数が j であるような書き方

パスは disjoint であるという条件から，k はたかだか 2 になります．
dp の更新にさらに別のDPを行う必要があります．
dp2[i][j][k] := v の子のうち i 個目まで見た時，j 個の disjoint なパスを書き，かつ v の次数が k であるような書き方
dp2 の更新には，子の dp の値も使います．

dp2 の遷移は，基本的に子 i と v に辺を書くかどうかで決まります．
以下の4パターンがあります．

  • そもそも書かない場合 -> 積を単純に加えるだけでよい．
  • 書く場合
    • v の次数が 0 で，i の次数が 0 -> v と i だけからなるパスが新たに1つ増える
    • v の次数が 0 で，i の次数が 1 -> もともとあるパスが延長される
    • v の次数が 1 で，i の次数が 0 -> もともとあるパスが延長される
    • v の次数が 1 で，i の次数が 1 -> もともと disjoint だったパス同士がくっつくので，トータルで disjoint なパスが1つ減る

これを丁寧に書くと良いです．
ちょっと説明が雑なので，コードを読んだほうがわかるかもしれません．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using graph = vector<vector<int>>;

constexpr ll M = 1e9 + 7;

void dfs(graph const& g, int v, int par, vector<vector<vector<ll>>>& dp) {
    vector<int> child;
    for(auto to : g[v]) {
        if(to == par) {
            continue;
        }
        child.push_back(to);
        dfs(g, to, v, dp);
    }
    int const sz = child.size();
    int const N = dp.size();
    int const K = dp[0].size() - 1;

    vector<vector<vector<ll>>> dp2(sz + 1, vector<vector<ll>>(K + 1, vector<ll>(3)));
    dp2[0][0][0] = 1;
    // i: 今見ている子の idx
    // j: 頂点 v の部分木のパスの数
    // k: 頂点 v の次数
    // l: 今見ている子の部分木でのパスの数
    // m: 今見ている子の部分木での子の次数
    for(int i = 0; i < sz; ++i) {
        for(int j = 0; j < K + 1; ++j) {
            for(int k = 0; k < 3; ++k) {
                for(int l = 0; l < K + 1; ++l) {
                    for(int m = 0; m < 3; ++m) {
                        // パスが一個減るかもしれないので K + 1 までは許容
                        if(j + l > K + 1) {
                            continue;
                        }

                        ll t = (dp2[i][j][k] * dp[child[i]][l][m]) % M;
                        // v と child[i] を結ばない
                        if(j + l <= K) {
                            (dp2[i + 1][j + l][k] += t) %= M;
                        }

                        // v と child[i] を結ぶ
                        if(k == 0) {
                            if(m == 0 && j + l + 1 <= K) {
                                // v と child[i] を結ぶことで v - child[i] のみの新たなパスが増える
                                (dp2[i + 1][j + l + 1][1] += t) %= M;
                            } else if(m == 1 && j + l <= K) {
                                (dp2[i + 1][j + l][1] += t) %= M;
                            }
                        } else if(k == 1) {
                            if(m == 0 && j + l <= K) {
                                (dp2[i + 1][j + l][2] += t) %= M;
                            } else if(m == 1 && 0 <= j + l - 1) {
                                // 2つのパスがくっつくので 1 つ減る
                                (dp2[i + 1][j + l - 1][2] += t) %= M;
                            }
                        }
                    }
                }
            }
        }
    }
    dp[v] = move(dp2[sz]);
}

int main() {
    int N, K;
    cin >> N >> K;
    graph g(N);
    for(int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(K + 1, vector<ll>(3)));
    dfs(g, 0, -1, dp);

    ll res = 0;
    for(int i = 0; i < 3; ++i) {
        (res += dp[0][K][i]) %= M;
    }

    cout << res << endl;
}

感想

一日中考えてなんとかわかったけど，本番で出たら絶対書けないと思いますね…．
DPは脳死でコードが書けないのでとてもつらいです．

AOJ 0636 フェーン現象(Foehn Phenomena)

競プロ AOJ

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0636&lang=jp

解法

B[i] = A[i] - A[i + 1] という数列 B[i] を考えるのが良いです．
すると，A[l] から A[r] の変化が x だとすると，B[l - 1] と B[r] にしか影響を及ぼさないことがわかります．その他の場所は影響が相殺されるからです．
あとは変化によって B[l - 1]，B[r] の値が正になるのか負になるのかを見てやると，あとは総和を求めるだけになるので，BITなどで管理すると頭を使わなくて楽です．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
constexpr ll M = 1e9 + 7;

// 0-indexed
template <typename T>
class fenwick_tree {
public:
    fenwick_tree(int n) : n(n), dat(n, 0) {}

    void add(int i, T value) {
        for(; i<n; i |= i + 1) {
            dat[i] += value;
        }
    }

    // [0, i)
    T sum(int i) const {
        T res = 0;
        for(; i>=0; i = (i & (i+1)) - 1) {
            res += dat[i];
        }
        return res;
    }
    // [l, r)
    T sum(int l, int r) const {
        return sum(r-1) - sum(l-1);
    }

    T get(int i) const {
        return sum(i) - sum(i - 1);
    }

private:
    const int n;
    std::vector<T> dat;
};


int main() {
    ll N, Q, S, T;
    cin >> N >> Q >> S >> T;
    vector<ll> A(N + 1);
    for(int i = 0; i <= N; ++i) {
        cin >> A[i];
    }

    fenwick_tree<ll> bit(N);
    for(int i = 0; i < N; ++i) {
        if(A[i] < A[i + 1]) {
            bit.add(i, (A[i] - A[i + 1]) * S);
        } else {
            bit.add(i, (A[i] - A[i + 1]) * T);
        }
    }

    while(Q--) {
        int l, r, x;
        cin >> l >> r >> x;
        ll L = bit.get(l - 1), R = bit.get(r);
        ll new_L = L / (L < 0 ? S : T) - x;
        ll new_R = R / (R < 0 ? S : T) + x;
        bit.add(l - 1, -L + new_L * (new_L < 0 ? S : T));
        bit.add(r, -R + new_R * (new_R < 0 ? S : T));
        cout << bit.sum(0, N) << endl;
    }
}

感想

差をもった数列を扱う問題を最近解いたのですぐわかった．
こういう処理は典型らしい．
べつにBITは使わなくていいです．総和を持っておいて逐一変えるだけでOK．

TopCoder SRM 720 Div1 Easy SumProduct

競プロ TopCoder

問題文

リンクがまだない

問題概要

あなたは 0 から 9 までの数字をそれぞれ a[i] 個使えるとします．
これらの数字から，A 桁の数字 X と B 桁の数字 Y の2つの数字を作るとします．
このとき，考えられる (X, Y) について，X * Y の総和を求めなさい．
ただし，0-leadingな数字も許可するとし，また (a, b) と (b, a) (a != b) は区別して扱います．

例．
1を2個，2を1個，3が1個使えて，A = 2, B = 2の時，考えられるすべてのペアは
(11, 23), (11, 32), (12, 13), (12, 31), (13, 12), (13, 21), (21, 13), (21, 31), (31, 12), (31, 21), (32, 11) の12個で，総和は4114です．

・制約
0 <= a[i] <= 100
1 <= A <= 100
1 <= B <= 100
A + B <= a[0] + a[1] + ... + a[10]

解法

まず，0-leadingな数字が許される（例えば 0001 は 1 として扱う）ので，ある1つの桁に注目すると，その桁が x であるような組み合わせの数は，その桁以外でも全く同じになることがわかります．
（例えば，X の10の位が x である場合の数と，X の1000の位が x である場合の数は等しい．）
これから，以下のような解法が考えられます．

X の i 桁目が x，Y の j 桁目が y であるような組み合わせを C とおくと，ans += x * 10^i * y * 10^j * C をすべての i, x, j, y について行う．

各桁だけ抽出してやっていくということです．
先程も行ったとおり，何桁目だろうが同じことなので，X で x を1桁目に使い，Y で y を1桁目に使う場合の数を求めるだけで十分です．
これは
dp[i + 1][j] := 数字 i まで見た時，すでに j 桁使っている場合の数
として求めることができます．数字は結局 A + B 桁選ぶことになり，x と y は1つ使うのが固定なので，dp[10][A + B - 2] 通りが求める場合の数になります．a[x] と a[y] から最初に1を引いておくことに注意は必要です．
このDPの遷移は，今できている数列に，今見ている数字をいくつ挿入するか決め，そのあと配置をを定める，ということを考えるとかけます．
もしすでに j 桁できていて，k 個数字を挿入するなら，残りの A + B - 2 - j 箇所から k 箇所選んで配置するということです．

あとは，tmp += dp[10][A + B - 2] * x * y としていくと，最終的に tmp はある桁に注目したときの，その桁のみの掛け算の総和となります（10 のべき乗部分を含めていません）

最後は，i 桁と j 桁を全部試して足せばいいです．
これは tmp * 10^i + tmp * 10^j を，0 <= i < A, 0 <= j < B についてループを回すだけです．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
constexpr ll M = 1e9 + 7;

ll modpow(ll x, ll n) {
    ll res = 1;
    while(n > 0) {
        if(n & 1) {
            res = (res * x) % M;
        }
        x = (x * x) % M;
        n >>= 1;
    }
    return res;
}

class SumProduct {
public:
    int findSum(vector<int> amount, int blank1, int blank2) {
        vector<vector<ll>> comb(201, vector<ll>(201));
        for(int i = 0; i < 201; ++i) {
            for(int j = 0; j <= i; ++j) {
                if(j == i || j == 0) {
                    comb[i][j] = 1;
                } else {
                    comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % M;
                }
            }
        }

        ll t = 0;
        for(int n = 0; n <= 9; ++n) {
            if(amount[n] - 1 < 0) {
                continue;
            }
            amount[n]--;
            for(int m = 0; m <= 9; ++m) {
                if(amount[m] - 1 < 0) {
                    continue;
                }
                amount[m]--;
                vector<vector<ll>> dp(11, vector<ll>(201));
                dp[0][0] = 1;
                for(int i = 0; i < 10; ++i) {
                    for(int j = 0; j <= blank1 + blank2 - 2; ++j) {
                        for(int k = 0; k <= amount[i] && j + k <= blank1 + blank2 - 2; ++k) {
                            (dp[i + 1][j + k] += comb[blank1 + blank2 - 2 - j][k] * dp[i][j]) %= M;
                        }
                    }
                }
                t = (t + n * m * dp[10][blank1 + blank2 - 2]) % M;
                amount[m]++;
            }
            amount[n]++;
        }
        ll res = 0;
        for(int i = 0; i < blank1; ++i) {
            for(int j = 0; j < blank2; ++j) {
                res = (res + (t * modpow(10, i) % M) * modpow(10, j)) % M;
            }
        }
        return res;
    }
};

感想

本番で通せませんでした．DP部分ができない～となっていましたが，本番終了後に既知のDPであることに気が付きました．
過去の自分をぶんなぐってやりたい．

Typical DP Contest T - フィボナッチ

競プロ AtCoder TDPC

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_fibonacci

解法

今なら，通称きたまさ法とよばれている方法でやります．
きたまさ法自体の説明は省略します．

アイデアとしては，一般項を最初の K 項の線形結合で表そう，というものです．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
constexpr int M = 1e9 + 7;
 
 
class kitamasa {
public:
    // d: coefficient
    kitamasa(std::vector<long long> const& d_, long long const m = 1e9+7)
        : k(d_.size()),
          d(d_),
          M(m)
    {}
 
    void inc(std::vector<long long>& v) {
        std::rotate(v.begin(), v.begin() + (k - 1), v.begin() + k);
        long long l = v[0];
        v[0] = 0;
        for(int i = 0; i < k; ++i) {
            (v[i] += d[i] * l) %= M;
        }
    }
    void dbl(std::vector<long long>& v) { 
        auto buf = v;
        std::vector<long long> res(k);
        for(int i = 0; i < k; ++i) {
            for(int j = 0; j < k; ++j) {
                (res[j] += buf[j] * v[i]) %= M;
            }
            inc(buf);
        }
        v = std::move(res);
    }
 
    // calc a_n
    long long calc(long long n) {
        std::vector<long long> res(k);
        res[0] = 1;
        int j = 63;
        while(!(n & (1 << j))) {
            --j;
        }
        for(int i = j + 1; i >= 0; --i) {
            dbl(res);
            if(n & (1LL << i)) {
                inc(res);
            }
        }
 
        long long ans = 0;
        for(int i = 0; i < k; ++i) {
            (ans += res[i] * d[i]) %= M;
        }
        return ans;
    }
 
private:
    int k;
    std::vector<long long> d;
    long long const M;
};
 
using ll = long long;
 
int main() {
    int K, N;
    cin >> K >> N;
    vector<ll> d(K, 1);
    kitamasa kit(d);
    cout << kit.calc(N - 1) << endl;
}

感想

（線形）代数にある程度理解があるなら，アイデアはすぐわかると思います．

Typical DP Contest S - マス目

競プロ AtCoder TDPC

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_grid

解法

まず，この問題を解くにあたって以下の記事を大いに参考にさせていただきました．ありがとうございます．
algoogle.hadrori.jp

H が小さいので，それぞれのマスの連結関係をもちながら，列を左から右に見ていくDPをします．
具体的には
dp[i][S] := i 列目まで見た時，i 列目の各マスの連結関係が S であるような塗り方
とします．
ただし，S は7進数のように考えます．S の j 桁目が，j 行目に対応し，その値を以下のように分類します．

  • 0 -> 白色
  • 1 -> 黒で，かつ (0, 0) と連結である
  • 2 ～ 6 -> 黒で，かつ (0, 0) と連結でない．同じ番号が振られていれば，それらのマスは連結であると考える．

現状態を 0 から 7^H まで見て，次の状態を計算していきます．
この時，連結関係を見るのに union find 木を使うと便利です．
具体的な計算はコードにコメントで残しておきました．

ソースコード

#include <bits/stdc++.h>
using namespace std;

constexpr int M = 1e9 + 7;

class union_find {
public:
    union_find(int n)
        : par_(n, -1)
    {}

    int root(int x) {
        return par_[x] < 0 ? x : par_[x] = root(par_[x]);
    }

    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if(x == y) {
            return false;
        } else {
            if(par_[x] < par_[y]) {
                par_[x] += par_[y];
                par_[y] = x;
            } else {
                par_[y] += par_[x];
                par_[x] = y;
            }
            return true;
        }
    }

private:
    std::vector<int> par_;
};


int main() {
    int h, w;
    cin >> h >> w;

    vector<int> pw(8);
    pw[0] = 1;
    for(int i = 1; i < 8; ++i) {
        pw[i] = pw[i - 1] * 7;
    }

    vector<int> cur(pw[h]);
    // 1 列目の計算
    for(int i = 0; i < (1 << h); ++i) {
        if(i % 2 == 0) {
            continue;
        }
        int s = 1; // 状態．最初 (0, 0) は必ず黒で塗られている．
        int label = 1; // 連結関係のラベル
        for(int j = 1; j < h; ++j) { // 0 行目は黒確定なので 1 から
            if(i >> j & 1) {
                s += label * pw[j]; // 7 進数 j 桁目が label という意味
            } else if(i >> (j - 1) & 1) { // 隙間が空いているので
                label++;                      // 連結関係をわける
            }
        }
        cur[s] = 1;
    }

    for(int i = 0; i < w - 1; ++i) {
        vector<int> nxt(pw[h]);
        for(int j = 0; j < pw[h]; ++j) { // 現状態．7 進数だと思えばよい．
            if(cur[j] == 0) {
                continue;
            }
            for(int k = 0; k < (1 << h); ++k) { // 次の状態（黒く塗られているかだけ）
                union_find uf(h); // 次の連結関係を求めるための union find 木
                vector<int> p(h); // 次状態の各行の連結関係を保存
                for(int l = 0; l < h; ++l) {
                    if(k >> l & 1) {             // 次状態の l 行目が黒
                        if(j / pw[l] % 7 == 1) { // 現状態で l 行目が (0, 0) と連結なら
                            p[l] = 1;            // 次状態でも l 行目は (0, 0) と連結
                        }

                        for(int m = l + 1; m < h; ++m) { // 連結関係を uf 木でまとめていく
                            if(k >> m & 1) {
                                if(m == l + 1) {    // l 行目と l + 1 行目がともに黒
                                    uf.unite(l, m); // 隣あってるので，l 行目と m 行目は連結
                                } else {
                                    int u = j / pw[l] % 7, // 現状態の l 行目，m 行目の連結関係
                                        v = j / pw[m] % 7;
                                    if(u > 0 && u == v) {  // どちらも現状態で同じ連結関係なら
                                        uf.unite(l, m);    // 次状態でも同じ連結関係
                                    }
                                }
                            }
                        }
                    }
                }

                for(int l = 0; l < h; ++l) {
                    if(p[l] == 1) {
                        p[uf.root(l)] = 1; // 次状態で (0, 0) と連結なものをまとめる
                    }
                }
                int nj = 0;     // 連結関係も含めた最終的な次状態
                int label = 2;  // 連結関係のラベル
                for(int l = 0; l < h; ++l) {
                    if(k >> l & 1) {        // 次状態で l 行目が黒である
                        int u = uf.root(l); // l 行目が連結関係にある集合
                        if(p[u] == 0) {     // その集合が (0, 0) に連結でなく，新しい連結関係であるなら
                            p[u] = label++; // どの連結関係かのラベルを割り当てる
                        }
                        nj += pw[l] * p[u];
                    }
                }
                nxt[nj] = (nxt[nj] + cur[j]) % M;
            }
        }
        cur.swap(nxt);
    }

    int res = 0;
    for(int i = 0; i < pw[h]; ++i) {
        if(i / pw[h - 1] % 7 == 1) {
            res = (res + cur[i]) % M;
        }
    }
    cout << res << endl;
}

感想

自力では解けませんでした．解法を理解してもバグりました．
時間を開けて，次は何も参考にせずに解きたい．

Typical DP Contest M - 家

競プロ AtCoder TDPC

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_house

解法

まず階段を使うまえに，各階で部屋i -> j の移動経路が何パターンあるかを計算します．
これは普通に
dp[S][i][j] := 今まで訪れた部屋の集合が S である，i -> j の移動パターン
とすれば求めることができます．

i -> ｊの移動パターンの総数を A[j][i] で表すことにします．（添字注意）
h 階で部屋 i に至る経路の総数を b_h[i] という列ベクトルで表すと，h - 1 階で部屋 i に至る経路の総数 b_{h-1}[i] は b_{h-1} = A * b_h という式で表せることがわかります．

H回部屋をウロウロできるので，答えは A^H * b_H となります．b_H は最初の要素が1でほかが0の列ベクトルです．

計算量は O(2^H * R^3 + R^3logH) です．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
constexpr ll M = 1e9 + 7;

// matrix は略

ll dp[1 << 16][16][16];

int main() {
    int H, R;
    cin >> H >> R;
    vector<vector<int>> g(R, vector<int>(R));
    for(int i = 0; i < R; ++i) {
        for(int j = 0; j < R; ++j) {
            cin >> g[i][j];
        }
    }

    for(int i = 0; i < R; ++i) {
        dp[1 << i][i][i] = 1;
    }
    auto A = make_matrix<ll>(R, R);
    for(int S = 0; S < (1 << R); ++S) {
        for(int start = 0; start < R; ++start) {
            for(int now = 0; now < R; ++now) {
                for(int next = 0; next < R; ++next) {
                    if((S >> next) & 1 || g[now][next] == 0) {
                        continue;
                    }
                    (dp[S | 1 << next][start][next] += dp[S][start][now]) %= M;
                }
                (A[now][start] += dp[S][start][now]) %= M;
            }
        }
    }

    A = modpow(A, H, M);
    vector<ll> b(R);
    b[0] = 1;
    cout << modmul(A, b, M)[0] << endl;
}

感想

これは簡単だった．
2^R * R^3 でちょっと焦りましたが…（よくあるのは 2^R * R^2 ですよね．通るもんですね）

Codeforces Round #238 (Div. 1) D. Hill Climbing

競プロ Codeforces

問題文

http://codeforces.com/problemset/problem/406/D

問題概要

山が一直線上に n 山ならんでいる．それぞれの山の座標は x[i]，高さは y[i] である．
山と山にはスロープがかかっている．スロープは以下のようにかかっている．
各山 a は，a の頂上から右（x の正方向）を見たときに見える山で一番右にある山 b とスロープでつながっている．

この山々に対してクエリが m 個投げられる．各クエリは山 a と b を指定してくるので，a と b から右の山にスロープで移動していって，合流する山を答えよ．

・制約
1 <= n <= 10^5
1 <= m <= 10^5
1 <= x[i] <= 10^7
1 <= y[i] <= 10^11
x[i] は相異なる．

解法

スロープを辺と見ると，これは山 n を根とした木になっていることがわかる．
合流する山とは，この根付き木での LCA を求めるということである．

あとはスロープをつなげるだけだが，これは山 n から見ていって，凸包を作るような感じで結んでいけば良い．
候補の山を vector で持っておき，今見ている山の頂上と候補の中で直近の山の頂上を結んだときの傾きで判定すれば良い．
この傾きが増加し続ける限り，その要素を pop_back しながら右の山を見ていく．
増加しなくなったタイミングで打ち切り，その山とスロープをつなげる．
pop_backした山は，後にスロープがかかることは無いのでそれっきりでOK．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

constexpr int INF = 1e9 + 1;

struct edge {
    int from, to;
};

using edges = std::vector<edge>;
using graph = std::vector<edges>;

int main() {
    int n;
    scanf("%d", &n);
    vector<double> x(n), y(n);
    for(int i = 0; i < n; ++i) {
        scanf("%lf %lf", &x[i], &y[i]);
    }

    vector<int> v = {n - 1};
    graph g(n);
    for(int i = n - 2; i >= 0; --i) {
        int j = v.size() - 1;
        double a = (y[v[j]] - y[i]) / (x[v[j]] - x[i]);
        for(int k = j - 1; k >= 0; --k) {
            if(a < (y[v[k]] - y[i]) / (x[v[k]] - x[i])) {
                j = k;
                a = (y[v[k]] - y[i]) / (x[v[k]] - x[i]);
                v.pop_back();
            } else {
                break;
            }
        }
        add_edge(g, i, v[j]);
        v.push_back(i);
    }

    // n - 1 を根にする
    lca L(g, n - 1);
    int m;
    scanf("%d", &m);
    for(int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        if(i != 0) {
            printf(" ");
        }
        printf("%d", L.query(a, b) + 1);
    }
    printf("\n");
}

感想

英文読解に失敗して LCA だと思ってなかった．
辺をはるところが難しい．なんとかバグらせずに通せた．