C - Ringo's Favorite Numbers 2 解説 by physics0523
「\(A_i - A_j\) が \(200\) の倍数である」ということは、「\(A_i\) を \(200\) で割った余りと \(A_j\) を \(200\) で割った余りが一致する」と言い換えられます。
なので、求めるものは、 \(A_i\) を \(200\) で割った余りと \(A_j\) を \(200\) で割った余りが一致するような \((i,j)\) \((1 \le i < j \le N)\) の組の通り数(位置が異なる \(2\) つの要素の選び取り方の場合の数)と言い換えられます。
まず、数列 \(A_i\) に \(200\) で割った余りが \(k\) であるような要素がいくつ含まれるかを求めます。今回の問題では愚直にループを回して数えてもよいですが、バケットソートの要領で調べると高速です。
数列 \(A_i\) に \(200\) で割った余りが \(k\) であるような要素が \(X\) 個含まれるとします。このとき、この中から数列 \(A\) での位置が異なる \(2\) つの要素を選び取る場合の数は、\(\frac{X \times (X-1)}{2}\) 通りです。この式は \(X=0,1\) の場合でも適用できます。
これを \(0\) 以上 \(199\) 以下の全ての整数 \(k\) について足し合わせると、この問題を解くことができます。
最終的な計算量は \(O(N)\) です。
C言語による実装例:
#include<stdio.h>
int main(){
int n,a[200005];
long long b[200]={0};
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
b[a[i]%200]++;
}
long long res=0;
for(int k=0;k<200;k++){
res+=(b[k]*(b[k]-1))/2;
}
printf("%lld\n",res);
return 0;
}
補足1: 言い換えについて
「\(A_i - A_j\) が \(200\) の倍数である」ということは、「\(A_i\) を \(200\) で割った余りと \(A_j\) を \(200\) で割った余りが一致する」と言い換えられます。
この理由について説明します。
もし、ある \(2\) つの要素 \(A_i\) と \(A_j\) を \(200\) で割った余りが一致するならば、この \(2\) 要素間で生じうる差は \(200\) で割った商の部分だけです。そして、その差は必ず \(200\) の倍数となります。
逆に、ある \(2\) つの要素 \(A_i\) と \(A_j\) を \(200\) で割った余りが一致しないならば、 \(A_i-A_j\) は \(200\) の倍数とはなりません。この理由は、例えば \(A_j\) に \(200\) を何度か足したり引いたりしても \(200\) で割った余りは変わらないため、 \(A_i\) に一致させることができないということで説明できます。
補足2: 場合の数について
数列 \(A_i\) に \(200\) で割った余りが \(k\) であるような要素が \(X\) 個含まれるとします。このとき、この中から数列 \(A\) での位置が異なる \(2\) つの要素を選び取る場合の数は、\(\frac{X \times (X-1)}{2}\) 通りです。
この理由について説明します。
まず、 \(X\) 個の互いに区別可能な物体から \(2\) 個を選んで並べる場合の数を考えます。
最初に、 \(1\) 個目の物体を選びます。これは \(X\) 通りです。
ここで、どのような物体を選んだとしても、 \(2\) 個目の物体の選び方は \((X-1)\) 通り存在します。
結局、この場合の数は \(X \times (X-1)\) 通りとなります。
今回の問題では、単に \(2\) 個を選び取るだけなので、 \(2\) つの物体の並び順( \(2\) 通り存在します)は区別されません。なので、求める場合の数は \(\frac{X \times (X-1)}{2}\) となります。
投稿日時:
最終更新: