Educational DP Contest (EDPC) X ~ Z 問題 解説

#はじめに
適当に記事を分けていった結果、この記事で解説するのが 3 問だけになってしまいました。(計画性の無さがばれてしまう)

この記事は EDPC X ~ Z 問題の解説です。X ~ Z 問題を解いてみてから読まれることを推奨します。

• Educational DP Contest / DP まとめコンテスト - AtCoder

W 問題までを解いていない方はこれらの記事も読むといいかもしれません。

• Educational DP Contest (EDPC) A ~ E 問題 解説
• Educational DP Contest (EDPC) F ~ J 問題 解説
• Educational DP Contest (EDPC) K ~ O 問題 解説
• Educational DP Contest (EDPC) P ~ S 問題 解説
• Educational DP Contest (EDPC) T ~ W 問題 解説

##この記事の続き

今後もしかしたら TDPC の解説も書くかもしれません。(まだ一問も読んでいないので気が変わるかもです)

• Typical DP Contest - AtCoder

また、私が好きな DP の配列再利用についても書く可能性があります。

#X - Tower
##問題
$N$ 個のブロックの中からいくつかを選び、次の条件を満たす塔を作ります。

• 塔に含まれるブロック $i$ について、ブロック $i$ より上に積んであるブロックの重さの和は $s_i$ 以下である。

塔に含まれる価値の和の最大値を求めてください。

##制約

• $1\le N\le10^3$
• $1\le w_i,s_i\le10^4$

##解法

実は、ある二つのブロックを比べたときに「こっちの方が下になるように積むのが望ましい」というのが一意に決められます。

塔の一番下にブロックを追加していくことを考えます。
すでに積まれているブロックの重さの和を $W$ として、その下にブロック $a,b$ 二つを追加します。
$a$ を $b$ の上に配置するとき、$W\le s_a$ と $W+w_a\le s_b$ を満たす必要があります。つまり、$W\le\min(s_a,s_b-w_a)$ である必要があります。
$b$ を $a$ の上に配置するときは、同様に $W\le\min(s_b,s_a-w_b)$ である必要があります。
$W$ により大きい値を入れられる方がいいので、ここから比較関数を作ることができそうです。
二つの $\min$ 関数内の不等号で場合分けして考えます。

• $s_a \le s_b-w_a$、$s_b\le s_a-w_b$ はあり得ないので、考えなくていいです。
• $s_a > s_b-w_a$、$s_b\le s_a-w_b$ の場合、$s_b>s_b-w_a$ より、$a$ が下の方がいいです。
• $s_a\le s_b-w_a$、$s_b>s_a-w_b$ の場合、同様に $b$ が下の方がいいです。
• $s_a > s_b-w_a$、$s_b>s_a-w_b$ の場合、
  • $s_b-w_a<s_a-w_b$ なら $a$ が下の方がいいです。
  • そうでないなら $b$ が下の方がいいです。

これらを整理してみると、$s_a+w_a>s_b+w_b$ の時に限り $a$ が下の方がいいことがわかります。

ブロックはこれに従ってソートされているものとします。

ここまでくれば、あとは塔の一番下にブロックを追加する DP をするだけです。
DP 自体はナップサックと似ていて、簡単だと思います。

##実装例
計算量は $O(N\max{s_i})$ です。

#include <algorithm>
#include <iostream>
using namespace std;

struct block {
    int w, s, v;
};
// 比較関数
bool comp(block a, block b) { return a.w + a.s < b.w + b.s; }

int N;
block B[1009];
long long dp[1009][20009];

int main() {
    cin >> N;
    for(int i = 0; i < N; i++) {
        int w, s, v;
        cin >> w >> s >> v;
        B[i] = block{w, s, v};
    }

    sort(B, B + N, comp);

    for(int i = 0; i < N; i++) {
        for(int j = 0; j <= 20000; j++) {
            dp[i + 1][j] = dp[i][j];
           if(j >= 1) dp[i + 1][j] = max(dp[i + 1][j], dp[i + 1][j - 1]);
            if(j >= B[i].w && j - B[i].w <= B[i].s)
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - B[i].w] + B[i].v);
        }
    }

    cout << dp[N][20000] << endl;

    return 0;
}

#Y - Grid 2

##問題
$H\times W$ のグリッド上に $N$ 個の壁があります。
$(0,0)$ から右、下への移動のみで $(H-1,W-1)$ まで行く方法は何通りか$\mod 10^9+7$ で求めてください。

##制約

• $2 \leq H, W \leq 10^5$
• $1 \leq N \leq 3000$

##解法
壁マスも無視して突っ切れるものとします。

下に $x$ マス、右に $y$ マス移動する方法を $f(x,y)=\binom{x+y}{x}$ とします。

求めるべきは壁マスを一度も通らずに右下にたどり着く方法です。
これは、$($右下までたどり着く方法 $-$ 壁を一度以上通って右下までたどり着く方法$)$ と言い換えられます。
左側は $f(H-1,W-1)$ なので、右側を求められればいいです。

$dp_i=($スタートから壁 $i$ まで行く方法のうち、途中に壁を通らないもの$)$ とします。
壁 $N$ がゴール地点にあるとみなすと、最終的な答えは $dp_N$ です。
遷移はこのようになります。

dp_i=f(r_i,c_i)-\sum dp_j\times f(r_i-r_j,c_i-c_j)

なお、この DP をする上で、「壁 $i$ から壁 $j$ に到達可能」ならば「$i<j$」が成り立っていると嬉しいですが、これは予め壁の座標を辞書順でソートしておけばいいです。

##実装例

#include <algorithm>
#include <iostream>
using namespace std;

const int mod = 1000000007;

// mod 逆元
long long inverse(long long a) {
    long long b = mod;
    long long u = 1, v = 0;
    while(b > 0) {
        int t = a / b;
        swap(a -= t * b, b);
        swap(u -= t * v, v);
    }
    return (u % mod + mod) % mod;
}

const int MAX = 200000;
// 階乗, 階乗の逆元を前計算しておく
long long fact[MAX + 1], finv[MAX + 1];
void factinit() {
    fact[0] = 1;
    for(int i = 1; i <= MAX; i++)
        fact[i] = fact[i - 1] * i % mod;
    finv[MAX] = inverse(fact[MAX]);
    for(int i = MAX; i > 0; i--)
        finv[i - 1] = finv[i] * i % mod;
}
long long comb(int n, int k) {
    if(n < k || k < 0) return 0;
    return fact[n] * finv[k] % mod * finv[n - k] % mod;
}
long long f(int x, int y) { return comb(x + y, x); }

int H, W, N;
pair<int, int> wall[3009];

long long dp[3009];

int main() {
    factinit();

    cin >> H >> W >> N;
    for(int i = 0; i < N; i++) {
        int r, c;
        cin >> r >> c;
        r--;
        c--; // 0-indexed にする
        wall[i] = make_pair(r, c);
    }
    // ゴールにも壁があるとみなすと実装が楽
    wall[N] = make_pair(H - 1, W - 1);

    sort(wall, wall + N);

    for(int i = 0; i <= N; i++) {
        dp[i] = f(wall[i].first, wall[i].second);
        for(int j = 0; j < i; j++) {
            int dx = wall[i].first - wall[j].first;
            int dy = wall[i].second - wall[j].second;
            dp[i] = (dp[i] - dp[j] * f(dx, dy) % mod + mod) % mod;
        }
    }

    cout << dp[N] << endl;

    return 0;
}

#Z - Frog 3

##問題

$N$ 個の足場の上をカエルが移動します。
カエルは、現在地より番号が大きいの任意の足場にジャンプできます。
足場 $i$ から足場 $j$ にジャンプするには $(h_j-h_i)^2+C$ のコストがかかります。
カエルが足場 $0$ から $N-1$ まで移動するための最小コストを求めてください。

##制約

• $2\le N\le2\times10^5$
• $h_i<h_{i+1}$

##解法

従来の Frog シリーズと同様に、$dp_i=($足場 $i$ まで移動する最小コスト$)$ としてよさそうです。
遷移を書くと

\begin{align}
dp_i &=\min\left(dp_j+\left(h_i-h_j\right)^2\right)+C \\
&=\min\left(h_i^2-2h_jh_i+h_j^2+dp_j\right)+C \\
&=\min\left(-2h_jh_i+h_j^2+dp_j\right)+h_i^2+C
\end{align}

となり、$\min$ の中をよく見ると一次関数 $(-2h_j)x+h_j^2+dp_j$ の集合の $x=h_i$ における最小値なので、Convex-Hull Trick が使えそうです。

CHT を使うことでこの遷移はならし $O(1)$ でできるので、全体での計算量は $O(N)$ です。

##実装例

#include <deque>
#include <iostream>
using namespace std;

struct ConvexHullTrick {
    struct Line {
        long long a, b;
        long long get(long long x) { return a * x + b; }
    };
    deque<Line> que;
    bool check(Line a, Line b, Line c) {
        return (b.b - c.b) * (b.a - a.a) <= (a.b - b.b) * (c.a - b.a);
    }
    void add(long long a, long long b) {
        Line l{a, b};
        while(que.size() > 1 && check(que[que.size() - 2], que.back(), l))
            que.pop_back();
        que.push_back(l);
    }
    long long query(long long x) {
        if(que.empty()) return INT64_MAX;
        while(que.size() > 1 && que[0].get(x) >= que[1].get(x))
            que.pop_front();
        return que[0].get(x);
    }
};

int N;
long long C;
long long h[200009];

ConvexHullTrick cht;

long long dp[200009];

int main() {
    cin >> N >> C;
    for(int i = 0; i < N; i++)
        cin >> h[i];

    cht.add(-2 * h[0], h[0] * h[0]);
    for(int i = 1; i < N; i++) {
        dp[i] = cht.query(h[i]) + h[i] * h[i] + C;
        cht.add(-2 * h[i], dp[i] + h[i] * h[i]);
    }

    cout << dp[N - 1] << endl;

    return 0;
}

#続き