C - Not Equal（285）

問題

問題文

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

制約

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

考察

条件を満たす数列の数を求めます。まずは条件を言い換えます。

・Ai ≠ Aj ( 1 ≤ i < j ≤ N )

この条件は、数列のうち i 番目以降には i 番目と同じ数字が出現しない、ということを示しています。その条件が1 から N までの全ての i , j の組み合わせについて成り立ちますので、次のように言い換えることが可能です。

数列 A の全ての数字が相異なる

この条件のもとで考えていきます。次に、特殊なケースにおいて考えます。

例）5 5 5

１番目の数字としてあり得るのは「1,2,3,4,5」の５つです。２番目の際には「１〜５」のうち１つの数字が既に使われていますので、「1,2,3,4,5」のうち使われている一つを除いた4つです。同様に３番目の際には既に2つ使われていますので、候補となるのは３つです。考えられる組み合わせはこの３つの数字の掛け算で表されますので、

5 * 4 * 3 = 60 通り

となります。このように、各数字において候補となる数字を掛けていけば答えになります。次の例を考えます。

例）1 3 5

この場合も上の例と同様に考えられます。1番目は１通り、２番目は３通りから１を引いて2通り、３番目は5通りから2を引いて３通りとなります。これの掛け算で1*2*3 = 6通りです。

最後の例です。

例）4 2 8

１番目の候補は「1,2,3,4」の４通りです。しかし、2番目の候補は今まで通りにはいきません。一番目に「1,2」を選んだ際には1通りですが、「3,4」を選んだ際には2通り存在します。ということで、先ほどと同様に前から掛けていくだけでは答えが求まりません。

どうしてこうなるかといいますと、前の数字よりも小さな数字が出現するからです。

ですので、小さい数字から順番に処理していくとこにしましょう。まずは、2です。2つですね。次は4で4-1=3つです。最後に8で8-2=6つです。これらの数字の掛け算で答えが求まります。

このように小さい順に処理することにより簡単な掛け算で求めることができます。問題の条件は「数列 A の全ての数字が相異なる」ですので、順番を変えても答えに影響はありません。

実装する際には、元の数列Cをソートしておくことにより、小さい順に処理することができます。ソート済みのCの値を出現した数字の数を引きながら掛け合わせていきましょう。このとき、その値が0以下になりましたら、存在しないということですので、0をかけてあげます。

また、答えは(10^9+7)で割った値を出力するので、この値の余りを取りながら計算をしていきましょう。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

const int mod = 1e9 + 7;
int main()
{
   int n;
   cin >> n;
   ll ans = 1;
   vector<ll> c(n);
   rep(i, n) cin >> c[i];
   sort(c.begin(), c.end());
   rep(i,n)
   {
       ans *= max(0LL,c[i]-i);
       ans %= mod;
   }
   cout << ans << endl;

   return 0;
}

あとがき

小さい順に処理することが重要な問題でした。私はコンテスト中はなかなかこの性質に気づくことができずに、だいぶ苦戦しました。

「大きい数字が先に来ると困る」「順番を入れ替えても影響がない」

という２点からソートが有効であるということに気づけました。

結構、難しい問題だったと思います。この問題も灰色diffなのが信じられませんね。