ARMERIA

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

第一回日本最強プログラマー学生選手権決勝 F - Count Permutations Many Times

お題箱より。

F - Count Permutations Many Times

難しめの(とはいえ上級者には比較的知名度が高い)テクニックを複数使いこなす必要がある問題です。公式解説では多項式の係数に対応させて解いていますが、そうではない方法で説明しようと思います。

解法

まずは1つのクエリだけを考える

まずはこの問題を、あるクエリ(区間 \lbrack L, R\rbrack 1つだけについて解くことを考えましょう。

 p_{j} \ne A_{j} である」よりも「 p_{j} = A_{j} である(違反状態である)」のほうが数えやすいので、包除原理を適用します。 N 個の整数の集合を  S = \lbrace 0, ..., N-1\rbrace として、その部分集合  s を考えます。 s に含まれる整数が全て違反状態である(含まれない整数はどちらでもよい)ような場合の数を  C(s) とすると、求めたい答えは包除原理から

 \displaystyle \sum_{s\subset S}(-1)^{|s|}C(s)

と計算することができます。ここで  |s| s の要素数を示します。

 C(s) の求め方を考えます。ある  s についてその要素を  x_{1}, ..., x_{|s|} と書きます。このときクエリで指定された区間  A_{L}, ..., A_{R} に含まれている整数  x の個数を  n(x) とすると、これは以下のように考えることができます。

  1. まず  x_{1}, ..., x_{|s|} を置く場所を順番に決めてしまう。このとき整数  x_{i} が違反する置き場所として取れるものは  n(x_{i}) 通りあり、これらの場所は異なる整数間で重複することはない。
  2. 先に上記の |s| 個を置き終わったら、残っている  N-|s| 個の整数を残っている  N-|s| 個の場所に自由に置く。

ということで、 C(s) は以下のようになります。

 \displaystyle C(s) = \prod_{x \in s}n(x) \times (N-|s|)!

これを全ての  s \subset S について個別に求めるのは当然できません。求めたい答えの計算において、サイズ  |s| が同じ部分集合には同じ係数  (-1)^{|s|}(N-|s|)! が掛かることに注目すると、残った  \prod_{x \in s}n(x) をサイズが同じ集合ごとに合計したものが分かれば良さそうです。

ということで以下のDPを組みます。

 dp\lbrack i \rbrack\lbrack j \rbrack = 整数  0, ..., i-1 までのうち  j 個を含むような集合全てについて、それぞれの集合を  s としたときの  \prod_{x \in s}n(x) の値を合計したもの。

これを最後まで計算したときの

 \displaystyle \sum_{j=0}^{N} \left( dp\lbrack N \rbrack\lbrack j \rbrack\times (-1)^{j}(N-j)!\right)

の値が答えになります。

このDPにおける  dp\lbrack i \rbrack\lbrack j \rbrack からの遷移は次の2通りです。

  • 整数  i を集合の要素として採用する。 n(i) を掛けて  dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack に足す。
  • 整数  i を集合の要素として採用しない。そのまま  dp\lbrack i+1 \rbrack\lbrack j \rbrack に足す。

これでクエリが1つの場合は  O(N^{2}) のDPで解くことができました。このようにシンプルな遷移であることが後々効いてきます。

複数クエリではどうするか?

クエリとして区間が与えられるので、まず考えるのはセグメント木等です。ただこの問題の場合、2つの区間に対する計算結果(DPテーブル)をマージするのが難しいです。遷移の係数となっている  n(0), ..., n(N-1) が全部変わる可能性があるため、DPを最初から全部やりなおすことになります。

区間クエリの処理方法としてもう1つ重要テクニックがあります。Mo's Algorithm です。使える条件/やり方/計算量についてはリンク先を参照して欲しいのですが、これは

  • オフラインクエリである(いわゆるクエリ先読みができる)
  • 区間を1要素分伸ばす/1要素分縮めて、答えを更新するという操作が妥当な計算時間でできる

という条件を満たす時に使えるテクニックです。

伸び縮みの計算量を  O(\alpha) として全体計算量は  O(\alpha(N+Q)\sqrt{N}) N, Q が大きいと  O(\alpha) として許せる計算量は  O(1) O(\log N) くらいなのですが、今回は制約が小さいので  O(N) くらいならOKそうです。

要素を増やす/減らす処理を上手くやるには?

ある区間  A_{L}, ..., A_{R} について、先ほどのDPの最終結果が求められているとします。そこから区間の要素を1つだけ増やす/減らすという処理を上手くやる方法はあるでしょうか?

このとき増えた/減った要素の値を  d とすると、DP遷移の係数となっている  n(0), ..., n(N-1) のうち変化するのは  n(d) だけです。そして先ほどのDPは、「戻すDP」というテクニックが適用できる形になっています。これは

  • 今回の  0, ..., N-1 の整数のように、DPの計算において見ていく順番が変わっても問題ない。
  • DPの遷移が単純で、 dp\lbrack N \rbrack\lbrack\cdot\rbrack から  dp\lbrack N-1\rbrack\lbrack\cdot\rbrack を逆算することができる。

という条件を満たすときに使えるテクニックです。

今回のように  N 段階の遷移のうち1つの段階だけで係数の変化などがある時には、その遷移を古い係数で戻してから新しい係数で計算し直す…という手順で  dp\lbrack N \rbrack\lbrack\cdot\rbrack を更新することができます。この計算は  O(N) でできます。

まとめ

以上で全ての材料が揃いました。

  1. まず包除原理を元に、1つのクエリ  \lbrack L, R\rbrack だけについてこの問題を解くDPを構成する。
  2. 与えられるクエリにMo's Algorithmを適用する。
  3. Mo's Algorithmの中で要求される区間の伸び縮みについては、先ほどのDPに「戻すDP」のテクニックを適用し、DPテーブルの値を更新する。
  4. 各クエリについて、その時のDPテーブルの値に係数を掛けて合計したものが答えとなる。

公式解説では多項式の係数と見なして解いていますが、多項式の掛け算がこの記事におけるDPを進める時の遷移に、割り算が戻す時の遷移にちょうど対応するので、本質的には同じ計算をしていることになります。

ACコード

Submission #7835655 - 第一回日本最強プログラマー学生選手権決勝(オープンコンテスト)