ABC468 C - Between P and Q

PとQの間

考え方

$N$ 個の数の順列は、$N!$ 通りある。
$P$ と $Q$ それぞれより辞書順で前にある順列の個数を求めてしまえば、それらの差 $-1$ で答えとなる。

さて、ある順列が何番目になるかは、高校数学の典型問題。
前から順に「その桁より前は同じで、その桁が $P$ より小さくなる個数を足していく」をやればよい。
その値は、その桁に使える数の個数 $\times$ 残り個数の階乗で求められる。

そういう関数を作り、「$Q$ の前にある個数」$-$「$P$ の前にある個数」$-1$ を計算すればよい。
$-1$ は、$P$ そのものの分である。

ただし、$P$ が $Q$ より後ろにある場合などは計算結果が誤って負の数になってしまう。
計算結果と $0$ との大きい方を答えとして出力する。

計算量は、その桁に使える数の個数の管理方法次第。
ここを愚直にやれば $O(N^2)$、Fenwick木（E問題級）で高速化すれば $O(N \log N)$。

入力を受け取る。

n: 3
p: {1, 3, 2}
q: {3, 1, 2}

$P$ が何番目の順列かを計算する。

先頭の $1$ より小さい未使用の数はない。

次の $3$ より小さい未使用の数は $2$ の $1$ 個である。
残り $1$ 個の並べ方は $1!=1$ 通りなので、$1$ を加える。

最後の $2$ より小さい未使用の数はない。

よって、$P$ より辞書順で小さい順列は $1$ 個である。

calc(p): 1

$Q$ が何番目の順列かを計算する。

先頭の $3$ より小さい未使用の数は $1,2$ の $2$ 個である。
残り $2$ 個の並べ方は $2!=2$ 通りなので、$2\times2=4$ を加える。

次の $1$ より小さい未使用の数はない。

最後の $2$ より小さい未使用の数もない。

よって、$Q$ より辞書順で小さい順列は $4$ 個である。

calc(q): 4

したがって、$P$ と $Q$ の間にある順列の個数は $4-1-1=2$ である。

特になし。

順列全探索で解くこともできる。
スタートを昇順ではなく $P$ そのものに設定し、毎回カウンタを $1$ 増やしていく。
$P$ と $Q$ が一致したら、break で脱出。

間を数えるので、do while よりも、普通の while で最初に $1$ 回順列を進める方が正しく答えやすい。

また、最初から $P \geq Q$ の場合にちゃんと $0$ と答えられるように注意する必要がある。

計算量は $O(N \times N!)$ だが、 $N \leq 10$ なので間に合う。