人権なし

競プロで解いた問題や開発の進捗などの記録です

CPSCO2019 Session3:F - Flexible Permutation

問題

atcoder.jp

解法

dp(i, a, b) := 1 ~ i までの全ての順列のうち,P_k > k となるような k の個数が a,P_k < k となるような k の個数が b である通り数

を考える.1 ~ i - 1 までの順列に新しく i を追加するとき,1 ~ i - 1 までの順列の末尾に i を追加し,追加した i をそのままにするか,任意の箇所と swap することで,1 ~ i の任意の順列を作ることが出来る.

ここで,swap する相手の箇所 k が P_k > k であるのか,P_k < k であるのか,P_k == k であるのかを場合分けして考える.swap する場合,P_k < i かつ P_i > k であるので,P_k > k であるとき,swap すると b が 1 増える.P_k < k であるとき,swap すると a が 1 増える.P_k == k であるとき,swap すると a と b がともに 1 増える.swap しない場合はともに変化しない.これらを DP の遷移とすると,

dp(i, a, b) = dp(i - 1, a, b - 1) * a + dp(i - 1, a - 1, b) * b + dp(i - 1, a - 1, b - 1) * (i - 1 - (a - 1) - (b - 1)) + dp(i - 1, a, b)

となる.O(N^3).P_k == k となるような k を組み合わせ計算で決め打ちしておき,N == A + B とすることで O(N^2) に落とすこともできる.

解答

atcoder.jp

f:id:babcs2035:20190505223143p:plain