NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ,自然言語処理 (ブログではまだ)。数式の書き方を一気に KaTeX に変えようとして記事を全削除してインポートし直すなどしたので,過去にブックマークされた記事は URL が変わってしまっている可能性があります…….

yukicoder No.1001 注文の多い順列

問題: No.1001 注文の多い順列 - yukicoder

writer 解説: yukicoder

問題概要

$1$ 以上 $N$ 以下の整数の順列 $p_1, p_2, ... p_N$ であって,以下の条件を満たすものの数を $10^9+7$ で割った余りを求めよ。

  • すべての $i (1 \leq i \leq N)$ について以下を満たす。
    • $t_i = 1$ ならば $p_i \geq X_i$
    • $t_i = 0$ ならば $p_i \leq X_i$

解法概要

仮に条件が $t_i = 0$ のもののみであった場合,以下のようにして解ける。

  1. 条件を $X_i$ の昇順にソートする。ソート後のインデックスを $i' (1 \leq i' \leq N)$ とする。
  2. すべての $i'$ について,$\max(0, (X_i' - (i'-1)))$ の積をとる。 ($i'-1$ はこれまでに置いた要素の数にあたる)

例えば, $X_1 = 2, X_2 = 3, X_3 = 3$ ですべての $i$ について $t_i = 0$ であれば,$X_1 = 2$ については 1 か 2 を置くことができるので選択肢は2個,$X_2 = 3$ については 3 以下の整数が置けるが 1 か 2 はすでに使ってしまったので選択肢は $3-1=2$ 個,$X_3 = 3$ については 3 以下の整数が置けるが 2以下の整数 1 個と3以下の整数1個の計2個は使ってしまったので選択肢は $3-2=1$個,よって条件を満たす順列の数は $2 \times 2 \times 1 = 4$ 個,と求められる。

しかし今回は,$t_i = 0$ の条件と $t_i = 1$ の条件の両方が存在する。ただし,$t_i = 1$ の条件は反転させると $p_i \leq X_i-1$ と,$t_i = 0$ の条件と同じ形にすることができる。$t_i = 1$ の条件を反転させたものを利用すると,

($t_i = 0$ の条件をすべて満たし,かつ$t_i = 1$ の条件を反転させたものを1つも満たさない順列の数)

= ($t_i = 0$ の条件をすべて満たす順列の数) - ($t_i = 0$ の条件をすべて満たし,かつ$t_i = 1$ の条件を反転させたものを1つでも満たす順列の数)

のようにして数えることができる。条件がすべて $\leq$ の形をしていれば最初に述べたような方法で数えることができるので,$t_i = 0$ の条件そのものおよび $t_i = 1$ の条件を反転させたものを昇順にソートした後,DP で数える。

$ \mathit{dp}_{i, j} = i$ 個目の条件まで考慮済みで,そのうち $j$ 個の条件を満たす場合の配置の仕方の数

と定義し配る DP を考えると,条件を満たす場合の遷移は,

$\mathit{dp}_{i+1, j+1} = \mathit{dp}_{i+1, j+1} + \mathit{dp}_{i, j} \times \max(0, X_i -j)$ ($j$ 個配置済みなので)

となり,条件を満たさない場合の遷移は

$\mathit{dp}_{i+1, j} = \mathit{dp}_{i+1, j} + \mathit{dp}_{i, j}$

となる。ただし,$ t_i = 0$ の条件については条件を満たすものしか考えないので条件を満たさない場合の遷移は行わない。

すべての遷移の後に,$\mathit{dp}_{n, j}$ に対して $(n-j)!$ をかけた数が数えたい順列の数になる。

包除原理を使って

($t_i = 0$ の条件をすべて満たす順列の数)

$-$ ($t_i = 0$ の条件をすべて満たし,かつ$t_i = 1$ の条件を反転させたものを1つ満たす順列の数)

$+$ ($t_i = 0$ の条件をすべて満たし,かつ$t_i = 1$ の条件を反転させたものを2つ満たす順列の数)

$-$ ($t_i = 0$ の条件をすべて満たし,かつ$t_i = 1$ の条件を反転させたものを3つ満たす順列の数)

$\dots$

のように足し合わせたものが答え。

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

using ll =  long long;
using Pii = pair<int, int>;

constexpr ll MOD = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<Pii> p(n);
    int min_cnt = 0;
    for(int i=0;i<n;++i) {
        cin >> p[i].second >> p[i].first;
        if(p[i].second == 1) {
            --p[i].first;
        } else {
            ++min_cnt;
        }
    }
    sort(p.begin(), p.end());

    vector<vector<ll>> dp(n+1, vector<ll>(n+1, 0));
    dp[0][0] = 1;
    for(int i=0;i<n;++i) {
        for(int j=0;j<=i;++j) {
            if(p[i].second == 1) {
                dp[i+1][j] += dp[i][j];
                dp[i+1][j] %= MOD;
            }
            dp[i+1][j+1] += dp[i][j] * max(0, p[i].first-j) % MOD;
            dp[i+1][j+1] %= MOD;
        }
    }

    ll fact[n+1];
    fact[0] = 1;
    for(int i=1;i<=n;++i) fact[i] = (fact[i-1] * i) % MOD;

    ll ans = 0LL;
    for(int i=min_cnt;i<=n;++i) {
        if((i-min_cnt) % 2) {
            ans += MOD - dp[n][i] * fact[n-i] % MOD;
        } else {
            ans += dp[n][i] * fact[n-i] % MOD;
        }
        ans %= MOD;
    }
    
    cout << ans << endl;
}

所感

包除原理を使うための材料を DP で揃える問題を通したのは初めてかもしれない?

汎用性たかそう。