Yuki's Tech Blog

仕事で得た知見や勉強した技術を書きます。

問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本で知ったことをざっくりまとめてみた (part 2)

目次

ユークリッドの互除法とは

ユークリッドの互除法とは、自然数Aと自然数Bの最大公約数を高速に求めるためのアルゴリズムです。計算量はO(log(A+B))です。自然数Aと自然数Bの中で小さい方の数をNとすると、AとBの最大公約数はN以下であることは明らかです。1からN以下の数でAとBをそれぞれ割り、余りが0になるような最大の数が最大公約数です。しかし、この方法では計算量がO(N)です。ユークリッドの互除法の方がより少ない計算回数で自然数Aと自然数Bの最大公約数を求めることができます。

ユークリッドの互除法の計算ステップ

  1. 大きい方の数を小さい方の数で割る。
  2. 大きい方の数に小さい方の数を代入。余りを小さい方の数に代入。
  3. 余りが0になるまでこの操作を繰り返すと、大きい数と小さい数の最大公約数を求めることができる。

なぜ計算量がO(log(A+B))になるのか?

自然数Aと自然数Bの和をA + Bとすると、計算をするたびに、A+Bの和が2/3倍されるという事実があります。A + Bは絶対1より小さくならないので、(A + B) * (2 / 3)n >= 1 (nは計算回数)が成立します。この式を式変形すると、n <= log1.5(A + B) になります。したがって、計算量はO(log(A+B))です。

最大公約数を求めるアルゴリズム

#include <bits/stdc++.h>
using namespace std;

int main() {
  int gcd, a, b, r;
  vector<int> vec(2);
  cin >> vec.at(0) >> vec.at(1);
  
  if(vec.at(0) < vec.at(1)) {
    a = vec.at(0);
    b = vec.at(1);
  } else {
    a = vec.at(1);
    b = vec.at(0);
  }
  
  r = b % a;
  b = a;
  a = r;
    
  while (r != 0) {
    r = b % a;
    b = a;
    a = r;
  }
  
  gcd = b;
  cout << gcd << endl;
}

N個の自然数の最大公約数を求める

#include <bits/stdc++.h>
using namespace std;
 
long long getGcd(long long a, long long b) {
  long long gcd, r, tmp;
  
  if (a > b) {
    tmp = a;
    a = b;
    b = tmp;
  }
  
  r = b % a;
  b = a;
  a = r;
    
  while (r != 0) {
    r = b % a;
    b = a;
    a = r;
  }
  
  gcd = b;
  return gcd;
};
 
int main() {
  long long n, gcd, j = 2;
  cin >> n;
  vector<long long> vec(n);
  for (int i = 0; i < n; i++) {
    cin >> vec.at(i);
  }
  
  gcd = getGcd(vec.at(0), vec.at(1));
  
  while (j < n) {
    gcd = getGcd(gcd, vec.at(j));
    j++;
  }
  
  cout << gcd << endl;
}

N個の数の最小公倍数を求めるプログラム

2つの数の最小公倍数を導出した後、その最小公倍数と別の数の最小公倍数を求めます。その操作を繰り返すと、N個の数の最小公倍数を求めることができます。

#include <bits/stdc++.h>
using namespace std;

long long getGcd(long long a, long long b) {
  long long gcd, r, tmp;
  
  if (a > b) {
    tmp = a;
    a = b;
    b = tmp;
  }
  
  r = b % a;
  b = a;
  a = r;
    
  while (r != 0) {
    r = b % a;
    b = a;
    a = r;
  }
  
  gcd = b;
  return gcd;
}

long long getLcm(long long a, long long b) {
  long long lcm;
  lcm = (a / getGcd(a, b)) * b;
  return lcm;
}

int main() {
  long long n, j = 2, lcm;
  cin >> n;
  vector<long long> vec(n);
  for (long long i = 0; i < n; i++) {
    cin >> vec.at(i);
  }
  
  lcm = getLcm(vec.at(0), vec.at(1));
  
  while (j < n) {
    lcm = getLcm(lcm, vec.at(j));
    j++;
  }

  cout << lcm << endl;  
}

注) getLcm関数の中で、aとbの掛け算の結果を最大公約数で割るのではなく、aを最大公約数で割った後にbをかけています。このようにする理由は、aとbがとても大きな数の場合、オーバーフローを起こしてエラーになってしまうからです。先に割り算をすることで、数を小さくすることができます。

n個の物から2個選んで500円になるような選び方を求める

品物の値段が100, 200, 300, 400のいずれかの場合、500円になるようなパターンは2パターンしかありません。n個の物の中でそれらの個数を求めて、積の法則でそれらを掛け算すれば、n個の物から2個選んで500円になるような選び方を求めることができます。この時の計算量はO(n)です。 普通に計算しようとすると、1個固定して、500円になるような組み合わせをn個の中から探す必要があるので、計算量がO(n2)です。成立パターンのパターン数が決まっているなら、N個を構成している数の個数を数えて、積の法則(またはコンビネーション)で計算したほうが、計算量が少なくて良いです

#include <bits/stdc++.h>
using namespace std;

int main() {
  // 500円になるパターンは2パターンしかないので、ある金額の品物の個数をa, b, c, dとする
  long long n, a = 0, b = 0, c = 0, d = 0, result = 0;
  cin >> n;
  vector<long long> vec(n);
  for (long long i = 0; i < n; i++) {
    cin >> vec.at(i);
  }
  
  for (long long i = 0; i < vec.size(); i++) {
    switch (vec.at(i)) {
      case 100:
        a++;
        break;
      case 200:
        b++;
        break;
      case 300:
        c++;
        break;
      case 400:
        d++;
        break;
      default:
        a++;
        break;
    }
  }
  
  result = a * d + b * c;
  
  cout << result << endl;
}

赤、青、黄色の中から2つ選んで同色カードになる選び方の問題も、パターンが3パターンしかないので、N個の数の中から、赤、青、黄の個数を数えて、コンビネーションを使えば良いです。普通に計算しようすると計算量がO(n2)なので、処理効率が悪いです。

#include <bits/stdc++.h>
using namespace std;

long long getComb(long long n) {
  return (n / 2.0) * (n - 1);
}

int main() {
  long long n, a = 0, b = 0, c = 0, result = 0;
  cin >> n;
  vector<long long> vec(n);
  for (long long i = 0; i < n; i++) {
    cin >> vec.at(i);
  }
  
  for (long long i = 0; i < vec.size(); i++) {
    switch (vec.at(i)) {
      case 1:
        a++;
        break;
      case 2:
        b++;
        break;
      case 3:
        c++;
        break;
      default:
        a++;
        break;
    }
  }
 
  result = getComb(a) + getComb(b) + getComb(c);
  
  cout << result << endl;
}

AtCorderの実行制限時間

AtCorderの実行制限時間は、2秒くらいが多いです。 AtCorderでは1秒あたり108回くらい計算できます。

コンビネーションなどの場合の数の公式

コンビネーションなどの場合の数の公式を使うことで、計算回数の見積もりをすることができます。例えば、100個の中から5枚のカードを選ぶ場合、100C5を計算すれば、75287520なので、計算回数が109より小さいことがわかります。なので、実行時間が2秒未満であることがわかります。

コンビネーションを求めるプログラム

#include <bits/stdc++.h>
using namespace std;

int main() {
  long long n, r, fac = 1, comb = 0, result = 0;
  cin >> n >> r;
  
  for(int i = 1; i <= r; i++) {
    fac *= i;
  }
 
  result = n;
  for(long long j = 1; j < r; j++) {
    result = result * (n - 1);
    n -= 1;
  }
  
  comb =  result / fac;
  
  

  cout << comb << endl;
}

N枚のカードに整数A(1 <= A <= 99999)が書かれているとき、2枚のカードの和が100000になるような2枚のカードの選び方を求める

2枚しかカードを選ばなくて出る数も分かっている場合、和が100000になるような2枚のカードの選び方(パターン)は限定される。そのため、N枚のカードそれぞれが、どの整数Aなのかをカウントして、結果を保持しておく。インデックスを整数A、インデックスに対応する要素にカウントを入れれば良い。そして最後にパターンを満たすような積の法則を使えば良い。

#include <bits/stdc++.h>
using namespace std;

int main() {
  long long n, s = 0, result = 0, fac = 1;
  cin >> n;
  vector<long long> vec(n);
  vector<long long> count(100000);
  
  for(long long i = 0; i < n; i++) {
    cin >> vec.at(i);
  }
  
  for(int j = 0; j < 100000; j++) {
    count.at(j) = 0;
  }
  
  for (long long k = 0; k < n; k++) {
    count.at(vec.at(k)) += 1;
  }
  
  for (long long l = 1; l < 50000; l++) {
    s = count.at(l) * count.at(100000 - l);

    if(s > 0) {
      result += s;
    }
  }
    
  // 注) 2つあるときは1通りである。
  if (count.at(50000) > 1) {
    s = count.at(50000) * (count.at(50000) - 1) / 2;
    result +=  s ;
  }
  
  cout << result << endl;
}

参考記事

C++ switch文のサンプル | ITSakura