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

hamayanhamayan's blog

Permutation [Educational DP Contest / DP まとめコンテスト T]

https://atcoder.jp/contests/dp/tasks/dp_t

解説

https://atcoder.jp/contests/dp/submissions/3980491

正直自分で以下のDPを思いついてないので、思いつく過程は分からない。
色々な要素が絡む難しい問題なので、TLEするDPをまずは説明して、そこからの最適化をしていく。
 
dp[i][lst][less][more] := 順列のi番目まで確定していて、最後の要素がlst、それより小さい要素がless個、大きい要素がmore個あるとする組み合わせ
dp[i][lst][less][more]からの遷移を考えると、

  • 次の要素との関係が'<'ならば、more通りの遷移先がある
  • 次の要素との関係が'>'ならば、less通りの遷移先がある

ここで、問題として遷移先のDPのlstをどうするかという問題があるが、遷移を見てみると、lstは特に使っていない。
つまり、最後の要素に対して小さい数、大きい数がどれだけ残っているかが重要になる。
そのため、lstを削ってみる。
 
dp[i][less][more] := 順列のi番目まで確定していて、最後の要素より小さい要素がless個、大きい要素がmore個あるとする組み合わせ
dp[i][less][more]からの遷移を考えると、

  • 次の要素との関係が'<'ならば、more通りの遷移先がある
  • 次の要素との関係が'>'ならば、less通りの遷移先がある

はしっかり行える。
次の要素との関係が'<'で、more通りの中で小さい方から2番目に遷移したとすると、遷移先はdp[i+1][less+1][more-2]のようにかける。
これで状態O(N^3)、遷移O(N)となり、O(N^4)を達成できる。
ここから、まずは、状態を削減できる。

dp[i][less] := 順列のi番目まで確定していて、最後の要素より小さい要素がless個である組み合わせ
moreを削ったのだが、i番目まで確定ということは未確定要素はN-i-1個となる。
(N-i-1の-1はiを0-indexedで考えているため)
よって、lessがわかれば、more=N-i-1-lessなので、状態として分けて保存しなくてもいい。
dp[i][less]からの遷移を考えると、

  • 次の要素との関係が'<'ならば、N-i-1-less通りの遷移先がある
  • 次の要素との関係が'>'ならば、less通りの遷移先がある

となり、変わらない。
これで状態O(N^2)、遷移O(N)
最後に遷移を最適化する。 
 
DPの最適化でよくあるテクだが、配るDPを貰うDPに変換する。
今までは遷移元から遷移先を考えていたが、逆に遷移先から遷移元を考える。
dp[i][less]への遷移元について考えてみると、

  • 前の要素との関係が'<'ならば、dp[i-1][0], dp[i-1][1], ..., dp[i-1][less]
  • 次の要素との関係が'>'ならば、dp[i-1][less+1], dp[i-1][less+2], ..., dp[i-1][N-1]

となる。
これは区間和になっているので、1つ前の桁のDPをBITにしておけば高速に取得できる。

nt N; string S;
mint dp[3010][3010];
BIT<mint> bit(3010);
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;

    rep(i, 0, N) dp[0][i] = 1;

    rep(i, 1, N) {
        bit.clear();
        rep(less, 0, N - i+1) bit.add(less, dp[i - 1][less]);
        rep(less, 0, N - i) {
            if (S[i - 1] == '<') dp[i][less] = bit.get(0, less + 1); // dp[i-1][0..less]
            else dp[i][less] = bit.get(less + 1, N); // dp[i-1][less+1..N-1]
        }
    }

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