ABC468 C - Between P and 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)$。

入力例1での動作

入力を受け取る。

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

まず、$P=(1,3,2)$ より辞書順で小さい順列の個数を求める。

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

次に、$Q=(3,1,2)$ について同様に求める。

したがって、$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$ なので間に合う。