Educational DP Contest / DP まとめコンテスト: T - Permutation

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

問題概要

整数Nと長さN-1の文字列Sが与えられる。Sは'>'と'<'のみからなり、長さNの数列における隣り合う値の大小関係を表す。(1, 2, ..., N)のすべての順列のうちSの表す大小関係に従うものは何通りあるか。

N <= 3000

解法

値を左から確定させていくことを考えると、単純なDPは以下のようになる。

dp(i, j, T): i番目まで決めていて、最後に置いた値がjであり、残っている未使用の値の集合がTであるような場合の数

このとき遷移は、対応する文字が'>'であればTの中からjより小さい値を選び、'<'であればjより大きい値を選ぶ、という形になる。このことを踏まえると、ひとつ前に選んだ数字とこれから選ぶ数字の大小関係が本質的な情報である。よって状態を以下のようにまとめてしまうことができる。

dp(i, j): i番目まで決めていて、最後に置いた値が「残っている未使用の値のうちj番目に小さい値」であるような場合の数

もし直前に「残っている中で2番目に小さい値」を置いており、次の記号が'<'であるとする。すると今回置けるのは「残っている中で2番目以上の値」である（以下の画像参照）。

このようにすると前回取った値と大小記号だけで次に取れる値が決まるのでdpを埋めていくことができる。上の例でいくと、i回目に2を置いて記号が'<'のとき、遷移は dp[i][2] を dp[i+1][2～4] に一律に足す操作となる。これは区間への加算になるが、いもす法とかでうまいことやれば i -> i+1 の遷移全体をO(N)で計算できるので、結局O(N²)で最終的な答えが出せる。

上の説明は配る視点で書いたが自分の実装ではもらうDPでやっているのでそちら視点でも一応書いておく。たとえば今回のjが3で記号が<であれば、前回のjは0〜3のどれか。よって dp[i][j] += sum(dp[i-1][0〜j]) というような遷移になる。累積和等を使えば区間sumをとる部分がO(1)で処理できるようになるのでこちらも最終的にはO(N²)でできる。

感想

このまとめ方は思いつかなかった 下手に挿入DPを知っていたせいかとにかく値を入れる順番を固定しようとする方向にしか頭が行かず

（追記）コード書いたときはもらうDPで考えてたけど記事書いてたら自然と配る視点になったので配る方の説明も入れた

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string;

immutable long MOD = 10^^9 + 7;

void main() {
    auto N = readln.chomp.to!int;
    auto S = readln.chomp;

    auto dp = new long[][](N, N);
    dp[0][] = 1;

    foreach (i; 1..N) {
        if (S[i-1] == '>') {
            long s = dp[i-1][N-i];
            foreach_reverse (j; 0..N-i) {
                (dp[i][j] += s) %= MOD;
                (s += dp[i-1][j]) %= MOD;
            }
        } else {
            long s = dp[i-1][0];
            foreach (j; 0..N-i) {
                (dp[i][j] += s) %= MOD;
                (s += dp[i-1][j+1]) %= MOD;
            }
        }
    }

    long ans = 0;
    foreach (j; 0..N)
        (ans += dp[N-1][j]) %= MOD;
    ans.writeln;
}