ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

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

問題
提出コード

解法

i番目までの順列が完成しているときに、i+1番目の数字を加えて条件を満たす数列を作成することを考えます。
dp[i][j] = 長さiの数列で、一番後ろにjを選ぶときの並べ方の通り数
とします。
dp[i+1][j]を求めるために、i番目の数字とi+1番目の数字の関係をもとに場合分けしていきます。

  • p_{i} \lt p_{i+1}のとき
    p_{i} \lt jとなっている、i番目まで完成している任意の順列を1つ選びます。そして、この順列を少し組み換え、j以上の数字に+1をしてあげると、これはjを除き、[1,i+1]からなる数列になっていて、なおかつこの数列は問題の条件を満たしています。
    ということで、今作成した数列の最後尾にjを付け加えると、これは長さi+1の順列で、かつ問題の条件を満たしています。
    これ以外で作成できる、長さi+1で問題の条件を満たす順列は存在しません。上の操作と逆のことをすると元の順列を作成することができますが、逆操作を行う対象の順列が異なれば、逆操作後の順列も必ず異なるものになります。ので、長さi以下の順列を数え終えていることに反します。
    とういことで、p_{i+1} = jのとき、p_{i}j未満になればよいので、
    \displaystyle dp[i+1][j] = \sum_{k=1}^{j-1} dp[i][k]
    となります。

  • p_{i} \gt p_{i+1}のとき
    こちらも上と同様の手順を踏むことで、問題の条件を満たす順列が作成できます。これ以外に作成する方法がないので、結局はp_{i}j以上になっていればよいです(上の操作では、j以上の数に+1という操作を行っているので、p_{i}jになっていても、条件を満たすことができることに注意します)。
    ということで、
    \displaystyle dp[i+1][j] = \sum_{k=j}^{i} dp[i][k]
    となります。

    さて、あとはこのDPを行えばいいのですが、このままだと総和を取る操作で計算するのに時間がかかってしまいます。そこで、
    \displaystyle sum[i][j] = \sum_{k=1}^{j}dp[i][k]
    とすると、
    上の2つの遷移はそれぞれ、
    \displaystyle dp[i+1][j] = sum[i][j-1]
    \displaystyle dp[i+1][j] = sum[i][i]-sum[i][j-1]
    となります。
    ということで、このDPを行うと、答えは
    dp[n+1][n+1]を参照すればよいです。

    感想

    証明まできっちり行ってから通すことができたので良かったのではないかなと思っています。
    式変形も素直にできたのでよかったです。
    思考の過程としては、割と上の解法をそのままたどるような形で、まずはある時点での数列を完成していた場合に、1つ長さを増やした数列を作成するにはどのようにすればいいだろうか、という部分から解法を思いつきました。