indexを $0 ≤ L ≤ R ≤ N-1$ になおして考える。
$L$ を $L=0$ から順番に試す。
辞書順なので兎にも角にも先頭に“1”を持ってくるのが一番小さくて、 その方法は(最初から $A_0$ が“1”だった場合を除き)$L=0$、$R=(A_i=1 であるような i)$ とする1通りである。
4 3 1 6 2 5 L R [1 3 4]6 2 5
また、“2”にするのも(最初から $A_0$ が“2”だった場合を除き)1通りで、これが2番目に小さい順列となる。
4 3 1 6 2 5 L R [2 6 1 3 4]5
同様に考えると、先頭が $A_0$ 以外になる順列はそれぞれ1通りしか作れず、順位が確定する。
4 3 1 6 2 5 → f(L,R)は21通り 辞書順 1 (先頭が1) 確定 2 (先頭が2) 確定 3 (先頭が3) 確定 4 (先頭が4) 5 (先頭が4) : 19 (先頭が4) 20 (先頭が5) 確定 21 (先頭が6) 確定
先頭が“4”になるのは、$L \ge 1$ か、または $L=R=0$ であり実質 $A$ から変わらない順列のいずれかとなる。
ともかく、順位 1~3, 20~21 が確定し、4~19 が未確定となった。
これを $L=1,2,3,...$ で再帰的におこなえば、徐々に未確定順位が絞られていく。
処理の途中で $K$ 番目が確定すればよし、確定しなければ次に進むことを繰り返す。
$L=N-1$ まで処理すると、最終的に未確定順位が $N$ 個分残る。
これは $L=R$ とした時のものであり、$K$ が未確定順位内にある場合は $A$ のままが答えとなる。
DP。割と素直な考え方で解けるが、計算量をちゃんと評価する部分に若干の難しさがある。
(とはいえ、「何となく大丈夫そう」で通ってしまうことも多いけど)
$x$ 2個が $x+1$ 1個になることを、「$x+1$ に1個繰り上がる」と表現することにする。
以下のDPで解ける。
例えば初期状態で“1”が7個あったら、$0~3$ 個まで“2”に繰り上げることができるので、
0 1 2 3 DP[2] = [1, 1, 1, 1]
となる。次、加えて“2”が例えば5個あったら、$DP[2]$ の $j=0~3$ につき、$DP[3]$ の $0~\lfloor \frac{j+5}{2} \rfloor$ に遷移できる。
Aの初期状態に"2"が5個: DP[2][0] → DP[3][0~2] のそれぞれに加算 DP[2][1] → DP[3][0~3] のそれぞれに加算 DP[2][2] → DP[3][0~3] のそれぞれに加算 DP[2][3] → DP[3][0~4] のそれぞれに加算 結果 0 1 2 3 4 DP[3] = [4, 4, 4, 3, 1]
加算部分は累積和で高速化できる。
これを、$i$ が $\max(A)$ を超えた上で、$|DP[i]|=1$ になるまで繰り返せば、$DP[i][0]$ が答え。
なので単純に掛け合わせると $O(N(A_{\max}+\log{N}))$ となり、TLEとなる。
しかし、それはあり得ない $(i,j)$ ペアまで含めてしまっているからで、有効なものだけを考えると、状態はぐっと減る。
ざっくり見積もりとして、以下が利用できる。
初期状態に $i$ があるとそこで長さが追加されるが、その場合も以下のように考えると、
細かな誤差とかは無視して、 「繰り上がってきた分」と「Aの初期状態にあった追加分」の DP上での行く末を分けて考える (本来は±1の端数のため、明確に分けられるものでもないが、ざっくり) 0 1 2 3 4 5 DP[2] [ o o o o o o ] ↓ ,-----' DP[3] [ o o o|o o o o o o ] ↓ ,-' ,-------' DP[4] [ o o|o o o|o o o ] ~~~ 2から追加された ~~~~~ 3から追加された ~~~~~ 4から追加された
結局、それぞれの区間の長さは約半分ずつになっていくのは変わらない。
ある長さ $n$ の区間が半分ずつになっていって、なくなるまでの長さの合計は約 $2n$ である。
DPに追加される長さの総計が $O(N)$ なので、それが一括であろうと分割されていようと、 全ての区間が無くなるまでの $DP[i]$ の長さの合計は $O(N)$ で収まることになる。
ただ、$N=2,A=\{1,200000\}$ のようなケースなど、繰り上がりが発生しなくても上限までの $DP[i][0]$ は遷移させ続けないといけないので、 計算量は $O(N + A_{\max})$ となる。
制約付き重複組み合わせ。計算量を減らす発想も必要。
まず、どちらの操作にしても総和が $K$ ずつ少なくなるので、$M \mod{K} \equiv 0$ 以外の場合は不可能。
可能な場合、$d=\frac{M}{K}$ として、$d$ 回、いずれかの操作をすることになる。
操作を「縦」「横」で表現することにする。
縦操作のパターンは、$i=1~N$ のそれぞれに対して、そこに何回操作をおこなえるかで決まる。
横操作のパターンは、$i=1~N-K+1$ のそれぞれに対して、そこを左端とする横操作を何回おこなえるかで決まる。
横操作の回数を $y$、縦操作を $d-y$ として、 それぞれの重複組み合わせ ${}_NH_{d-y} \times {}_{N-K+1}H_{y}$ とかで計算できそう。。。
しかし、これでは以下の2パターンが同じになり、重複して数えてしまう。
重複を防ぐため、「横操作は、1箇所に対して $K-1$ 回までしかおこなえない」とする。 (「縦操作は連続する $K$ 箇所に行えない」としてもよいが、まぁ、横操作の方が考えやすそう)
以下、1箇所の上限が $K-1$ までと決まっている重複組み合わせを、${}_nH'_{r}$ で表す。
横操作の回数を固定し、その場合の横操作と縦操作のパターン数の積を計算したい。
横操作の回数の上限は、$N-K+1$ 箇所に上限 $K-1$ を配置するため、$(N-K+1)(K-1)$ となる。
数え上げる式は立てられたが、これでは計算量が多すぎる。個数上限のある重複組み合わせの求め方と、$y$ に対するループの部分がネック。
個数上限付き重複組み合わせは、例えば以下の2通りの求め方がある。
DPなら、${}_nH'_r$ は以下のサイトのように $O((nの範囲) \times (rの範囲))$ で出せるが、
今回の場合、$n$ の上限は $N+K-1$、$r$ は横操作の回数上限 $(N-K+1)(K-1)$ なので、$O(N^3)$ となりDPでは無理そう。
包除原理は、個数上限が一定であるときに特に使いやすくて、 $n$ 個のうちいくつが(明示的に)制約違反しているかを求めることで、1回当たり $O(N)$ で求められる。
包除原理で、上限付き重複組み合わせを $O(N)$ で計算できるとはいっても、
ために、全体でまだ $O(N^4)$ かかってしまう。
実は、縦操作と横操作の回数は、場合分けする必要が無い。
回数の和が $d$ と決まっている2つの重複組み合わせなので、
「縦操作 $N$ と横操作 $N-K+1$、計 $2N-K+1$ から $d$ 個を重複を許して選ぶ」とすると、まとめて一括で考えられる。
この場合でも、「その中で横操作に対応する $N-K+1$ 個だけは、$K$ 個を超えて選べない」という個数上限は、 包除原理で問題なく計算できる。
これで、全体で $O(N^2)$ に収まる。