TakahiroNakamori

TakahiroNakamori

中森崇博(ナカモリタカヒロ)

08 /
28
2021
 

全探索と貪欲法は何が違うのか?

AtCoderの下記の問題で全探索を用いた場合と貪欲法を用いた場合で解説していただいていたので、全探索と貪欲法の違いを理解することを目的に整理します。

B – Magic 2
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

全探索で解く

最大\(K\)回操作できるので、合計が\(K\)回を超えない範囲で、以下の操作パターンの組み合わせが考えられます。

\(K \leq 7\)なので、三重ループ、すなわち、\(K^{3}\)でも解くことができます。

考えられるすべてのパターンを試すのが、全探索で解くということだと思います。

全探索を用いてACしたコード

赤、緑、青のそれぞれの操作回数が\(K\)を超えないようにループを実装してACしたのが、以下のコードです。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (n); ++i)
// const int mod = 1000000007;
// const ll INF = 1LL << 60;
// const int INF = 1001001001;

int main() {
  int A, B, C, K;
  cin >> A >> B >> C >> K;

  for (int i = 0; i <= K; ++i) {
    for (int j = 0; j <= K - i; ++j) {
      for (int k = 0; k <= K - i - j; ++k) {
        int sumA = A * pow(2, i);
        int sumB = B * pow(2, j);
        int sumC = C * pow(2, k);
        if (sumA < sumB && sumB < sumC) {
          cout << "Yes" << endl;
          return 0;
        }
      }
    }
  }

  cout << "No" << endl;
  return 0;
}

貪欲法で解く

この問題は、赤、緑、青のそれぞれに書かれた値、\(A,B,C\) のどれかを\(2\)倍する操作を\(1\)回としたとき、\(K\)回以下の操作で\(A < B < C\)とすることができるか否かが問われています。

\(A\)は最も小さくあるべきなので、赤のカードに対して操作を行う必要はありません。赤のカードに対して操作を行うとその分他のカードに対して操作を行う回数が増えます。したがって、赤のカードへの操作は\(0\)回です。

そして、緑のカードについても\(A < B\)にするのに必要な回数だけでいいです。残った回数で青のカードを操作し、\(B < C\)にできれば魔術は成功です。手順を整理すると以下のようになります。

  1. 赤のカードは操作しません。
  2. 緑のカードについて、\(A < B\)になるのに何回操作が必要かを数える。
  3. 次に、青のカードについて、\(B < C\)になるのに何回操作が必要かを数える。
  4. 最後に、合計操作回数が\(K\)以下かを確認する。

このように、論理的に回答となる手順や式を導き出して実装していく方法が貪欲法です。

貪欲法を用いてACしたコード

上記の考えをもとにACしたコードが以下になります。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (n); ++i)
// const int mod = 1000000007;
// const ll INF = 1LL << 60;
// const int INF = 1001001001;

int main() {
  int A, B, C, K;
  cin >> A >> B >> C >> K;

  int cnt = 0;
  while (B <= A) {
    cnt++;
    B *= 2;
  }
  while (C <= B) {
    cnt++;
    C *= 2;
  }

  if (cnt <= K) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}