AtCoder-ABC209 C - Not Equal【Python解答例】

AtCoder Beginner Contest209のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 209 - AtCoder

AtCoder Beginner Contest209 C - Not Equal

C - Not Equal

問題文

長さ N の整数列 C が与えられます。以下の条件を全て満たす長さ N の整数列 A の個数を求めてください。

・1≤Ai≤Ci(1≤i≤N)
・Ai ≠ Aj ( 1 ≤ i < j ≤ N )
ただし、答えは非常に大きくなる可能性があるので、(109+7) で割った余りを出力してください。

制約

・1≤N≤2×10^5
・1≤Ci≤10^9
・入力は全て整数

解答例

n = int(input())

C = list(map(int, input().split()))

C.sort()

ans = C[0]

for i in range(1,n):
    ans *= (C[i] - i)
    ans %= int(1e9 + 7)

print(ans)

解説

求める数列の個数は組み合わせになるのでソートしてから数を掛け合わせて求めました。

整数列Cをソートすることで、次のループにおいてC[i-1]よりC[i]が等しいか大きくなります。

したがって1<= Ai <= C[i]を満足する値はC[i]個ありますが、i 個の値はすでに使用されるためC[i] - i 個が組み合わせとして考えられる数になります。
この値をansに掛け合わせて行きました。

10^9 +7で割った余りは乗算のたびに求めました。
過去に同じような問題があり、この問題でも最後に1度だけ行うと答えが異なりましたので、各ループごとに行っています。
（詳しい説明ができず申し訳ないです (^_^;)）

最後にansを出力することでACでした！

ABC209の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com