https://atcoder.jp/contests/arc207/tasks/arc207_a
長さ $N$ の数列 $A_i$ (0-indexed) と整数 $X$ が与えられる。
以下の条件を満たす $(0,1,\dots,N-1)$ の順列 $p$ を数え上げよ。 ${\rm mod}$ $998244353$
- $\displaystyle \sum_{i=0}^{N-1} \max(0,A_{p_i}-i)$ が $X$ 以下である。
$1 \le N \le 100$
$0 \le A_i,X \le 10^9$
解説 AC ではあるんだけど解説を見てもあんまりよくわからず、 GPT 君に手伝ってもらってもよくわからず、結局だいぶ自力で細かいところを詰めた。
まず、 $A_i \ge N$ なる要素があったら $X$ を $A_i-(N-1)$ だけ減算して $A_i = N-1$ としてよい。
この際 $X<0$ なら答えは $0$ だし、 $X>N^2$ なら $X=N^2$ としてしまってよい。これを忘れると RE なり TLE なりするので注意。解法理解した後にこれで 2 ペナ出しました。
例えば位置 $6$ に $2$ を置くと、本来 $6$ の割引が利いて $-4$ であるものが $0$ になってしまう。このときの $4$ のようなものを loss と呼ぶ。
この loss に対して捉え方を変える。
先頭から要素を置いていく際に、位置 $k$ まで決めた時点で使っていない $k$ 以下の要素が $l$ 個あれば、位置 $k+1$ に移行する瞬間に loss が $l$ だけ増加する。
「 $k$ 以下」という属性があるため、「位置 $k$ を決めた直後に丁度 $k$ である要素たちに色を塗る。それまでは、 $k$ 以上である要素たちは一旦区別しないでおく。」という手続きを考える。今後は位置 $k$ を決めた以降の時点において、まだ使われず残っている $k$ を remain 0 と呼ぶことにする。
また、「場合の数」ではなく「確率」で考えて最後に「場合の数」に戻した方が楽なので、そうする。
以下の DP を行う。
$dp[$ loss の総和 $][$ remain 0 の個数 $]=\{$ そうなる確率 $\}$
- $dp[0][0]=1$ から始める。
- $pt=0,1,\dots,N-1$ について以下を繰り返す。
- まず、位置 $pt$ に置く要素を決める。
- $dp[i][j]$ について、 $\frac{j}{N-pt}$ の確率で remain 0 が $1$ 個減る。
- 次に、 $pt$ と等しい要素に色を付ける。つまり、既に使われている $pt$ には何も起こさず、まだ使われていない $pt$ は remain 0 となる。
- 以下を $pt$ の個数分繰り返す。
- まだ色付けしていない要素の総数を $tot$ とする。
- 一方、色付けしていない要素であってまだ置かれていないものの個数は $dp[i][j]$ に対して $rem=(N-pt-1)-j$ で求められる。
- $\frac{rem}{tot}$ の確率で、 remain 0 が $1$ 個増える。
- この結果、色付けしていない要素が $1$ 個減る。
- 以下を $pt$ の個数分繰り返す。
- 最後に、 $pt$ から $pt+1$ に移行する。
- この際、 remain 0 と同じだけ loss が増加する。
- まず、位置 $pt$ に置く要素を決める。
結局、 $dp[i]$ の総和を $i$ が $0$ から許される loss の最大値まで足し合わせて行けば確率が求まり、 $N!$ を掛けて答えが求まる。
https://atcoder.jp/contests/arc207/submissions/69932667
この手の数え上げ一生ハメてて一生死んでる。今回は挿入DPしようとして死んでました。
いい加減解けるようになるべき。
