貪欲からの帰着

DPの応用問題で難しい問題の中には、普通にDPを書くと重複してしまうタイプの問題があります。何らかの形でユニークなパラメータを基準に数える必要があるのですが、その判定問題がO(1)個のパラメータを持ちながら前から順番に見る貪欲で解けるならそのパラメータをDPのパラメータにすれば解けます。抽象的すぎて分かりませんね。具体例を見てみましょう。

問題

1, 2, ..., Nの順列であって、条件に合う様な各要素へのラベル付けが存在するものの数を答えよ。(N<=2000) 条件) 各要素AまたはBのラベルを付ける。Aの要素、Bの要素共に前から見ると単調増加になっている。

注意点として、1, 2, 3, ..., Nの様な列はラベルの付け方は多数あるが1通りとして数えられる。

そのままだと難しいので、ある列に対するラベル付けの判定問題にすり替えます。可能かどうかどう判定しますか？

前から順番に、可能ならAに詰め込みもし不可能ならBに詰め込む。それも不可能なら不可能という貪欲をすれば良さそうです。(これでいける簡単な説明を考えましょう。任意の地点で重要なのはA, B最後の要素のみです。もしこれよりいいやり方があるならBの最後の値はAの列のどっかに入る必要があります。Bの最後の値を入れる瞬間、もしこれをAに入れる事が可能ならば、その地点でAに入っていた値がBに入っている事になり、これは現状より悪いからです)

info

ここで順列のDPなので挿入DPしたくなるのですが、こらえて下さい。僕はこれで2時間迷走していました。何故挿入DPをしてはいけないのか、一般的な根拠があるのかよく分かりません。 {{< /alert >}}

前から順番に決めて行きます。例えば3 4 1 9 2で次にBが入るなら5しか入りようがありません。そもそもBになるためには9未満の整数である必要があり、6以上の数を入れると5の入る場所が無くなるからです。10以上の値はAとして自由に入り得ります。

つまり、 $dp_{i, j} := $前からi番目まで決めた時、Aの最大値がjである、とすると最後にBが入る様な決め方は(存在するなら)必ず各1通り決まります。i\<jならば決める事ができます。最後にAが入る時、$ dp_{i+1, j+1} $, $dp_{i+1, j+2}$ , ... , $dp_{i+1, n}$ に遷移します。

$dp_{i+1, j} = \sum_{k=i}^{j} dp_{i, k}$ 、 $dp_{1, *} = 1$ となります。

#include<cstdio>
using namespace std;

int n, dp[2002][2002];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) dp[1][i] = 1;
  for (int i = 1; i < n; i++) {
    for (int j = i; j <= n; j++) dp[i+1][j] = dp[i+1][j-1] + dp[i][j];
  }
  printf("%d\n", dp[n][n]);
}

ついでにtest用

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

int n, d[20], ans;

bool check() {
  int a = 0, b = 0;
  for (int i = 0; i < n; i++) {
    if (a < d[i]) a = d[i];
    else if (b < d[i]) b = d[i];
    else return false;
  }
  return true;
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) d[i] = i+1;
  do {
    if (check()) ans++;
  } while (next_permutation(d, d+n));
  printf("%d\n", ans);
}

少なくともn=12までは一致しました。関係ないですが、サクッと愚直コード書いてデバッグする事も大切だと思います。

warning

参考にしたページではBの末尾の要素が前i要素の中で大きい方からj番目として漸化式を立てているため方針が違う様です。そちらの方針、理解できませんでした。 {{< /alert >}}

疲れたので終わりです。