かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC199 E - Permutation

別解です.ほぼ一緒なので丁寧には書きません.

問題はこちら

問題概要

{(1,2,3,\cdots,N)}を並び替えてできる数列{A}で,以下の条件を満たすものの数を求めよ.

  • {1\leq i\leq N}を満たす全ての数列{i}について,{A_1,A_2,A_2,\cdots,A_{X_i}}の中に{Y_i}以下の数は{Z_i}個以下しか存在しない.

{2\leq N \leq 18\\
0 \leq M \leq 100\\
1\leq X_i < N\\
1\leq Y_i < N\\
0\leq Z_i < N\\}

解説

公式解説では数列を左端から決めて,使った数を状態として持つDPをしていましたが,小さい数から位置を決めていくことを考えます.DPでは数列中の既に決まった位置を持っておきます.すると遷移は

  • {dp[\emptyset]=1}
  • {dp[S]=0} (条件を満たさない時)
  • {\displaystyle dp[S]=\sum_{a\in S}dp[S\backslash \{a\}]} (条件を満たすとき)

となります.条件を満たすかを見るときは{|S|=Y_i}となる条件のみを見ればいいです.この方針だと任意の区間(位置)の条件でも解くことができるはず(たぶん).

提出プログラム

https://atcoder.jp/contests/abc199/submissions/22139163

感想

制約がbitDP