ABC209 C問題 Not Equalを解く - 競技プログラミング悪戦苦闘日記

ABC209 C問題の解説とふりかえりをします。

問題

長さ $N$ の整数列 $C$ が与えられます。以下の条件を全て満たす長さ $N$ の整数列 $A$ の個数を求めてください。
$1 \leq A_i \leq C_i (1 \leq i \leq N)$
$A_i \neq A_j ( 1 \leq i \lt j \leq N)$
ただし、答えは非常に大きくなる可能性があるので、 $(10^9 + 7)$ で割った余りを出力してください。

難しいポイント

おそらく問題を理解するのが難しいのではないかと思います。

解き方

問題文を読みながら具体的な数字を考えていきます。
2つ目のサンプルは $3, 3, 4, 4$ となっています。
愚直に $A_i$ の条件を書き出します。
$1 \leq A_1 \leq 3$ なので選べる数字としては $1, 2, 3$ の3個
$1 \leq A_2 \leq 3$ なので選べる数字としては $1, 2, 3$ の3個
$1 \leq A_3 \leq 4$ なので選べる数字としては $1, 2, 3, 4$ の4個
$1 \leq A_4 \leq 4$ なので選べる数字としては $1, 2, 3, 4$ の4個

ただ同じ数字を選べないという条件があるので、 $1, 2, 3$ から1つ選んだら、
次の $A_2$ は、 $1, 2, 3$ の3個から1つ少ない2個から選べます。
すでに2つの数字を選んでいるので、次の $A_3$ は、 $1, 2, 3, 4$ の4個から2個を引いた2個から選べます。
すでに3つの数字を選んでいるので次の $A_4$ は、 $1, 2, 3, 4$ の4個から3個を引いた1個から選べます。

ということで、整数列のパターンは、 $3 \times 2 \times 2 \times 1 = 12$ となります。

もう少し一般化して表現すると、1から $C_i$ までで選べる個数は $C_i$ 個だけど、それまでに $i - 1$ 個は数を選んでいるので、Nまで $C_i - (i - 1)$ をかけ続けると答えが求められます。

扱う数字が大きくなるとオーバーフローするので、掛け算をするたびに $10^9 + 7$ の余りを求めます。

実装

解き方の方針の通りに実装します。
Cの配列は処理の前にソートしてあげないと、不正解になります。
配列のインデックス $i$ は0から始まるので、見た目は少し異なります。

N = int(input())
c_arr = list(map(int, input().split()))
c_arr.sort()
ans = 1
R = 10**9 + 7
for i in range(N):
    ans = ans * (c_arr[i] - i) % R
print(ans % R)

反省

ans *= (c_arr[i] - i) % R

にするとタイムアウトしました。。。
累積演算子は計算量が思ったよりもかかるんですね。。。勉強になりました。