AtCoderログ：0016 - ABC 209 C

問題：ABC 209 C - Not Equal

問題文

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

制約

・$1 \le N \le 2 \times 10^5$
・$1 \le C_i \le 10^9$
・入力は全て整数

回答 (AC)

例えば $N=2, C_1=3, C_2=4$ の場合、条件に適する整数列は $(1,2)$, $(1,3)$, $(1,4)$, $(2,1)$, $(2,3)$, $(2,4)$, $(3,1)$, $(3,2)$, $(3,4)$ の $9$ 通りです。同様にして全ての場合を列挙するアプローチが考えられますが、列挙するには数列の各要素をループさせる必要があり、2つ目の制約条件 $1 \le C_i \le 10^9$ からこのアプローチは厳しいことがわかります。

そこで数式で計算することを考えます。さきほどの例の場合、$A_1$ の選び方は $1,2,3$ の $3$ 通り、$A_2$ の選び方は $1,2,3,4$ から $A_1$ として選んだ $1$ 通りを抜いた $3$ 通りとなるので、合計は $3 \times 3 =9$ 通りとなります。つまり $(C_1-0)\times(C_2-1)\times(C_3-0)\times \cdots$ を計算すれば良さそうに見えます。

ところがこの方法ではうまくいかないことがあります。例えば(先ほどとよく似た) $N=2, C_1=4, C_2=3$ の場合。数式による解法では $4 \times 2=8$ 通りとなるはずですが、実際に列挙してみると $(1,2)$, $(1,3)$, $(2,1)$, $(2,3)$, $(3,1)$, $(3,2)$, $(4,1)$, $(4,2)$, $(4,3)$ の $9$ 通りとなってしまい、どこかおかしいです。

詳しく調べると、例えば $A_1=1$ を選んだ場合には $A_2$ の選択肢は(期待通り) $2$ 通りですが、$A_1=4$ を選んでしまうと $A_2$ の選択肢は $1,2,3$ の $3$ 通りがあり、ここで違いが生じています。この違いは、前者で選んだ $A_1=1$ は $A_2$ の選択肢に含まれている数字であるのに対し、後者で選んだ $A_1=4$ は $A_2$ の選択肢に含まれていない数字であることです。上記の計算式では、$A_2$ の選択肢は $A_1$ で選ばれた数字取り除いて考えたため、後者のようなケースに対応できていないのです。

「$A_1$ で選んだ数字が $A_2$ の選択肢に必ず含まれている」ようにするには、$C_1 \le C_2$ である必要があります (上記の $N=2, C_4, C_2=3$ はこの条件を満たしていないため違いが生じました)。同様に「$A_1, A_2$ で選んだ数字が $A_3$ の選択肢に必ず含まれている」必要もあり、これは $C_1, C_2 \le
C_3$ という条件で表すことができます (まとめて $C_1 \le C_2 \le C_3$ となります)。さらに同様に考えることで、上記の計算式を使用するには $C_1 \le C_2 \le \dots \le C_N$ という条件が必要です。

コーディングにおいては、整数列を c() で受け取った後、c を昇順 (小さい順に) になるようにソートすれば上の条件を満たします。このとき求める場合の数は c.at(0) * (c.at(1)-1) * (c.at(2)-2) * ... * (c.at(n-1)-(n-1)) となります。なお、途中で c.at(i)<i となった場合、その桁の選択肢がないことを意味するので、最終的な答えは 0 になります。また、実際の計算では各項を掛けるごとに $\bmod{(10^7+9)}$ を計算することで、答えが膨大になることを避けることができます。

以上から、コードは以下のようになります。私の提出コードも同じ方針でした。

abc209c.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
 
  vector<int> c(n);
  for ( int i=0; i<n; i++ ) {
    cin >> c.at(i);
  }
  sort( c.begin(), c.end() );
  
  int64_t answer = 1, MOD = pow(10,9)+7;
  for ( int i=0; i<n; i++ ) {
    if ( c.at(i)<i ) {
      answer = 0;
      break;
    }
    answer = answer*(c.at(i)-i)%MOD;
  }
 
  cout << answer << endl;
}

調べたこと

AtCoder の解説 → 公式解説

回答と同じ方針でした。

AtCoder の解説 → ユーザ解説

回答と同じ方針でした。

リンク

• 前の記事 → AtCoderログ：0015 - ABC 209 B
• 次の記事 → AtCoderログ：0017 - ABC 069 B