AGC005 D ~K Perm Counting 別解(箱根駅伝DP)

AGC005D ~K Perm Counting を解きました。初めて箱根駅伝DPを使いました。

問題

AtCoder Grand Contest 005 D ~K Perm Counting
問題リンク:https://atcoder.jp/contests/agc005/tasks/agc005_d

解説

利用する典型テクニック

  • 箱根駅伝DP[1]

数列の順番を変える

条件がすべて $|a_i-i| \ne 1$ の形になるように帰着する。

 数列 $a$ の添字を次のように置き換えます。数列の値も同じように置き換えます。

  • $1,K+1,2K+1, \cdots ,2,K+2,2K+2, \cdots ,3,K+3,2K+3 \cdots $ を $1,2,3, \cdots $ に置き換える。

このようにすると、もともと添字の差が $K$ だった要素の組が隣り合うようになります。

 問題は次のように変化します。(これを新しい問題とします。)


 数列 $S$ が与えられます。下の条件を満たす長さ $N$ の順列 $a_1,a_2, \cdots a_N$ を数え上げてください。

  • 任意の $S$ の要素 $s$ について、 $|a_s-s| \ne 1$

箱根駅伝DPへ

箱根駅伝DPのテーブルを $4$ 倍した DP で解ける。

 「箱根駅伝DP」は、 $(1,2, \cdots ,N)$ と $(1,2, \cdots ,N)$ のマッチングを数え上げるときに用いて、

  • dp[i][k] = $(1,2, \cdots ,i)$ と $(1,2, \cdots ,i)$ について、 $k$ 個マッチングしている場合の数

というテーブルを持つDPを指します。(参考[1])

 新しい問題の、条件が関わる部分の遷移に注目します。

 通常の箱根駅伝 DP に加えて、「直前の要素 ( $2$ 個あります ) それぞれがマッチングに使われたか」という情報を添字に持ちます。使われていない場合、次の遷移でこの要素とのマッチングはできないので、遷移のときの倍率が $1$ 小さくなります。

 条件が関わらない部分は、通常の箱根駅伝DPと同様に遷移すればよいです。

提出コード

提出コードのリンク:https://atcoder.jp/contests/agc005/submissions/22554966

遷移の倍率をわかりやすくするため、 DP の添字の $k$ は「マッチングしていないペアが$k$ 個の場合」を表します。

参考

[1] けんちょんの競プロ精進記録(https://drken1215.hatenablog.com/entry/2019/10/05/173700)

タイトルとURLをコピーしました