はまやんはまやんはまやん

hamayanhamayan's blog

Deforestation [AtCoder Beginner Contest 209 F]

競技プログラミング

競プロのコード例について補足 競技プログラミング練習問題集 Twitter 競技セキュリティまとめのまとめ

https://atcoder.jp/contests/abc209/tasks/abc209_f

前提知識

解説

https://atcoder.jp/contests/abc209/submissions/24159889

mod109+7で制約をみてみると、dp[N][N]的な感じかなとまずよぎる。
色々整理していこう。

最適動作について

今回はコストの最小化と、最小になるときの組み合わせを計算する必要がある。
2つのことを一度に行うのは難しく、まずはコストの最小化を考えよう。

とある木を伐採する場合、そのコストに影響を与えるのは左右に隣接する木だけである。
よって、最適動作については隣接する木についてどちらを先に伐採するかで決まることになる。
仮にH[i]とH[i+1]を2通りの順番で伐採することを想定しよう。
H[i-1]とH[i+2]は一旦無視する。

H[i] -> H[i+1]で伐採すると、H[i]+2H[i+1]
H[i+1] -> H[i]で伐採すると、2H[i]+H[i+1]

となる。H[i]+H[i+1]はどちらもかかるので、差分で見ると、あとに伐採される方の高さが余分にかかってしまう。
なので、先に高さが高い方を伐採する方が効率がいい。
よって、H[i]＜H[i+1]ならi+1番目を先に伐採する必要があるし、H[i]＞H[i+1]ならi番目を先に伐採する必要があるし、同じならどっちでもいい。

この辺は何となく理解できると思う。
ここで重要なのが、この関係というのは「隣接する要素についてのみ考える必要があり、
2つ以上離れている要素について大小関係は考慮しなくていい」という部分である。これをうまく使うことでDPに落とし込める。

挿入DP

まず、挿入DPに慣れていない場合は一次元の普通の挿入DPを先に実施すると解説が分かりやすいかもしれない。
数列に対する一般的なDPでは要素を決定させるときに末尾に数などを追加していくようなイメージで遷移をしていく。
一方、挿入DPでは要素を決定させるときに既に確定している数列の任意の箇所に要素を挿入していくようなイメージになる。
一般に挿入DPは順列を構築する場合に使用する。
今回は木を伐採する順番を表す順列を作っていくことに相当する。

さて、DPテーブルを決めよう。

dp[i][pos] := i番目までの木の伐採順番が決まっていて、最後の木（i番目の木）がpos番目で伐採されているような組合せ

よくわからないかもしれない。
例えば、dp[4][2]というのは4番目までの木の伐採順番が決まっているので、1234の順列の組合せを想定している。
その中で4番目の木が2番目で伐採されているようなものなので、

1 4 2 3
1 4 3 2
2 4 1 3
2 4 3 1
3 4 1 2
3 4 2 1

みたいな順列の組み合わせが入っていることになる。
（実際はそれまでの遷移で最適動作になるような順列しか遷移されてこないので、もうちょっと絞られるはず）

dp[i][pos]のiは分かるだろうが、posが要素にある必要性について説明をする。
例えばdp[4][2]であれば、次に追加するのは5である。
5番目の木の伐採順番を考えようとしたときに、最適動作になるように気を付けるべきは4番目の木との位置関係だけである。
「だけ」というのが重要で、一手前の要素の場所だけ分かっていれば他は抽象化して問題ないということである。

H[4]とH[5]について H[4]＜H[5]であれば、5は4以前に置けばいいので、1 4 2 3であれば

 1 4 2 3  
^ ^

この2通りの挿入組合せがあることになり、遷移としては、
dp[4][2] -> dp[5][1]とdp[5][2]
のような遷移となる。
dp[i][pos]に対してi+1をどこに置くかを最適動作に注意しながら遷移させていけば、DPを更新していくことができる。
これを愚直に実装すると以下のような実装になる。

dp[1][1] = 1; // 1番目の木は単に置くだけ  
rep(i, 1, N) {  
    if (H[i - 1] <= H[i]) {  
        rep(pos, 1, i + 1) {  
            rep(pos2, pos + 1, i + 2) dp[i + 1][pos2] += dp[i][pos];  
        }  
    }  
    if (H[i - 1] >= H[i]) {  
        rep(pos, 1, i + 1) {  
            rep(pos2, 1, pos + 1) dp[i + 1][pos2] += dp[i][pos];  
        }  
    }  
}

ここまでがしっかり理解できていれば、これ以降の改善はそれほど難しくない。

貰うDPへの変換と累積和

この実装だとO(N3)なので間に合わない。
よって、DPを最適化することでACを取ろう。

まずは上の実装では配るDP（遷移元から遷移先を列挙）になっているので貰うDP（遷移先から遷移元を列挙）に変換しよう。
これも境界について注意しながら変換していく。

dp[1][1] = 1;  
rep(i, 1, N) {  
    if (H[i - 1] <= H[i]) {  
        tot[i] = dp[i][i];  
        rrep(pos, i - 1, 1) tot[pos] = tot[pos + 1] + dp[i][pos];  
  
        rep(pos2, 1, i + 1) {  
            rep(pos, pos2, i + 1) dp[i + 1][pos2] += dp[i][pos];  
        }  
    }  
    if (H[i - 1] >= H[i]) {  
        tot[1] = dp[i][1];  
        rep(pos, 2, i + 2) tot[pos] = tot[pos - 1] + dp[i][pos];  
  
        rep(pos2, 2, i + 2) {  
            rep(pos, 1, pos2) dp[i + 1][pos2] += dp[i][pos];  
        }  
    }  
}

本当にループを反転しただけ。
これを眺めてみると、遷移元は区間和の形を取っていることになる。
よって、dp[i+1]を計算するときにdp[i]について累積和を取っておくことで更新を高速化していく。
この部分についてはここまで話がついていけている人なら、それほど難しくないだろう。
累積和に変換すれば計算量も間に合うのでAC

int N, H[4010];
mint dp[4010][4010];
mint tot[4010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> H[i];

    dp[1][1] = 1;
    rep(i, 1, N) {
        if (H[i - 1] <= H[i]) {
            tot[i] = dp[i][i];
            rrep(pos, i - 1, 1) tot[pos] = tot[pos + 1] + dp[i][pos];

            rep(pos2, 1, i + 1) {
                //rep(pos, pos2, i + 1) dp[i + 1][pos2] += dp[i][pos];
                dp[i + 1][pos2] += tot[pos2];
            }
        }
        if (H[i - 1] >= H[i]) {
            tot[1] = dp[i][1];
            rep(pos, 2, i + 2) tot[pos] = tot[pos - 1] + dp[i][pos];

            rep(pos2, 2, i + 2) {
                //rep(pos, 1, pos2) dp[i + 1][pos2] += dp[i][pos];
                dp[i + 1][pos2] += tot[pos2 - 1];
            }
        }
    }

    mint ans = 0;
    rep(pos, 1, N + 1) ans += dp[N][pos];
    cout << ans << endl;
}