https://codility.com/programmers/lessons/10
この問題のspace complexityがO(1)なので、Lesson 9で使われているようなfactorizationのアルゴリズムは使えないことになりますね。
で、下のような方針をとりました。
NとMという二つの数を素数で素因数分解します。そして、NとMの最大公約数をP1 * P2 * P3 * P4 * ... Pxと素因数分解の一部で表しましょう。さらにN / gcd(N,M)と M / gcd(N,M)も残りの素因数を使って、ぞれぞれN1 * N2 * N3 * ... Ny, and M1 * M2 * M3 * ... Mzとあらわすとすると、Nと Mは以下のようになりますね。
N = (P1 * P2 * P3 ... Px) * N1 * N2 * N3 * ... Ny
M = (P1 * P2 * P3 ... Px) * M1 * M2 * M3 * ... Mz
(P1 * P2 * P3 ... Px) は gcd(N,M)ですから, NとMの間で因数として共通にあらわれる素数は必ずこのどれかに含まれていることになります。
いいかえれば、もし'N/ gcd(N,M)' の素因数(N1, N2, N3 ... Ny )のどれかが(P1, P2, P3, ...Px)に表れないならば、それはMの素因数ではないですね。つまりNとMの素因数の集合は同じでないということです。同様に 'M / gcd(A,B)'の素因数のどれか (M1, M2, L3 ... Ly)が(P1, P2. P3, ... Px)に表れないなら、それはNの素因数でないということになります。つまり、この場合もNとMの素因数の集合は同じでないということです。
つまるところ、この問題は、N1-NyとM1-Mzのうち、P1-Pxに表れないような素数があるかチェックするという問題になります。
ここでこう考えましょう。まずX = N / gcd(N,M)となるようなXを考えます。
そうすると現状でこうなりますね。
gcd(N,M): P1 * P2 * P3 ... Px
X : N1 * N2 * N3 ... Ny
もしここで gcd(N,M) % X == 0となるならば、N1-Nyは全てgcd(N,M)に含まれていることになりますね。
そうでなければ、今度はgcd(gcd(N,M), X)を計算しましょう。もしこの値が１であれば、gcd(N,M)とXは互いに素であることになり、Xはgcd(N,M)に表れない素因数をもつことになります。つまり、上で述べたようにこの場合、NにはMに含まれない素因数があったということで、NとMの素因数の集合は同じでないということになります。
もし１以上のgcdがあれば、今度はXをそのgcd(gcd(N,M), X)で割ってしまいましょう。この値で次のラウンドのXを更新します。これはどういうことかというと、gcd(gcd(N,M), X)にあたるXの素因数を全部割って取っ払い、その取っ払った後の残りを新しいラウンドのXにするということですね。
この時点でgcd(N, M) % X == 0になったとすると、Xの素因数は全てgcd(N, M)に含まれたことになりますので、少なくともNにある素因数はMに全て含まれているということになります。
もうちょっと具体例で説明しましょう。NとMを以下の値にしてみましょう。
N:3 * 5 * 3 * 7
M:3 * 5 * 11 * 13
そうすると、X = N / gcd(N, M)なので、下記のようになりますね。
gcd(N, M): 3 * 5
X : 3 * 7
ここで 15 % 21 != 0ですから、次の段階に進みます。まず上の二つの値を見ると, gcd(gcd(N, M), X) = 3 ですね。
ですからX / gcd(gcd(N, M), X)は 3 * 7 / 3 = 7となります。この７が次のラウンドのXになりますね。
すると、下記のようになります。
gcd(N, M): 3 * 5
X : 7
ここでgcd(gcd(N, M), X) = 1となりましたので、NにはMに存在しない素因数があるということになります。もし、Mが7を素因数として持っていたら、当然、NとMの両方に含まれるので、gcd(N, M)の素因数に含まれていないとおかしくなり、仮定に反しますね。
これをMに対しても行うとNとMの互いの素因数の集合が同じものであるかわかります。
それでは、このアルゴリズムが、問題が求めるO(Z*log(max(A)+max(B))^2)の最悪の計算量の想定を満たすか調べましょう。とりあえず、今回はO(log(a+b))の計算量の最大公約数を求めるアルゴリズムを使います。
上にしめした手法では、この最大公約数を求めるアルゴリズムを１ラウンドに１回つかい、それをlog(a)より小さいの回数繰り返すことになりますね。
例えばgcd(N,M) = 2でN = 2 * 2 * 2 * 2 * 2という、一番小さい素数２のみをつかった場合を想定しましょう。
For instance, assume gcd(N,M) = 2 and N = 2 * 2 * 2 * 2 * 2, using the smallest possible prime divisor 2. N は5個の2で構成されていますので, `rest / gcd(gcd(N,M),X)' の部分はgcd(N,M) % rest == 0になるまで、４回繰り返されますね。
ですから、このアルゴリズムの計算量はO(log(N+M)*log(N))を超えないことがわかります。 同様にMに同じことをする場合、O(log(N+M)*log(M))を超えない計算量になりますね。
この二つをあわせた計算量はO(log(N+M)*log(N) + log(N+M)*log(M))ですが、ここで、log(N) < log(N+M)、 log(M) < log(N+M)であるので以下のことが言えます（あ、0 < N <= Mですよ、もちろん。問題がそう定義してますから）
log(N+M) * log(N) + log(N+M) * log(M) <= 2 * log(N+M) * log(N+M).
ですから、NとMの両方に対して上記のアルゴリズムを適用しても、計算量はO(2*log(N+M)*log(N+M))、定数は除けるので、O(log(N+M)^2)を超えません。
これをそれぞれのA, BにたいしてZ回繰り返すので、それぞれのA,Bの最悪実行時間はmax(A), max(B)の時ですから、全体としての計算量は、問題が要求する最悪実行時間、O(Z*log(max(A)+max(B)^2))を超えないことになります。
このアルゴリズムを実装すると１００％のスコアがもらえました。
//The O (log(a + b)) gcd algorithm,
int gcd(int a, int b)
{
if (a % b == 0){
return b;;
}
return gcd(b, a % b);
}
int check(int a, int gcd_ab)
{
//check if all the prime divisors of 'a' can be found
//in the prime divisors of gcd(a,b).
int rest = a / gcd_ab;
//if gcd(a, b) % rest == 0, that means all the prime divisors
//of 'rest' is included in the prime divisors of gcd(a,b).
while (gcd_ab % rest != 0){
int gcd_tmp = gcd(gcd_ab, rest);
//if gcd(a,b) has 1 as the gcd with rest,
//that means 'a / gcd(a,b)' contains some prime divisor that is not
//found in the prime divisors of gcd(a,b).
return 0;
}
rest /= gcd_tmp;
}
return 1;
}
int solution(int A[], int B[], int Z)
{
int cnt = 0;
int i;
for (i = 0; i < Z; i++){
int gcd_ab = gcd(A[i], B[i]);
if (check(A[i], gcd_ab) && check(B[i], gcd_ab)){
cnt++;
}
}
return cnt;
}
0 件のコメント:
コメントを投稿