ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

CPSCO2019 Session3 F - Flexible Permutation O(N^2)解法

お題箱より。 O(N^{2}) 解法が知りたいというリクエストだったので考えてみました。

F - Flexible Permutation

解法

後に扱うDPの都合上、個人的にはインデックスよりも値に注目したほうが理解しやすいので、条件を値中心の言葉に言い換えます。 P_{i} \gt i であるような値  P_{i} を「左に動いた」、 P_{i} \lt i であるような値  P_{i} を「右に動いた」、 P_{i} = i であるような値  P_{i} を「動かない」と呼ぶことにします。

まず、動かない値  N-A-B 個を固定します。この選び方は  _{N}C_{N-A-B} 通りあり、これらの値を除くと残りは  A+B 個の必ず動く値だけを考えれば良いことになります。

公式解説の  O(N^{3}) 解法と同様に、値を順番に足していきながら以前の値とswapしていくDPを考えます。ただしそのまま適用した場合、DPの途中では相変わらず「左に動いている」「右に動いている」「(一時的に)動いていない」値がいくつあるかという情報を管理する必要があり、状態数が落ちません。

そこで以下のようなものを数える包除原理を考えます。

  • 予め指定したある  k 個の要素の集合について、値が動かない(違反状態である)。
  •  A 個の要素について、値が左に動く。
  • 残りの  B-k 個の要素について、値が動かないか、または右に動く。

つまり「ちょうど  A 個の値が左に動く」という条件は絶対に満たすとして、 B 個の要素について包除原理を適用する、ということです。こうすると先に  k 個の値を除いておけば、値の扱いで区別するべきものは「左に動いている」「それ以外」の2種類になり、状態数が  O(N^{2}) に落ちます。

  •  dp\lbrack i \rbrack\lbrack a\rbrack = 既に  i 個の値を置いていて、そのうち左に動いている値が  a 個あり、それ以外の値が  i-a 個あるような並べ方の数

遷移は次に置く値を「そのまま右端に置いた」「左に動いている値とswapした」「それ以外の値とswapした」ときにそれぞれ  a がどのように変化するかを考えれば良いです。具体的には「それ以外の値とswapした」ときだけ  a 1 つ増えることになります。

包除原理に基づいて結果を集計します。違反状態として指定した要素の個数が  k である場合、その  k 個の選び方が  _{A+B}C_{k} 通り、残りの場所の置き方が  dp\lbrack A+B-k\rbrack\lbrack A\rbrack 通りあるので、これらの積に  (-1)^{k} を掛けて全て合計すれば良いです。最後に  _{N}C_{N-A-B} を掛けると答えになります。

ACコード

Submission #15585152 - CPSCO2019 Session3