ABC239 D - Prime Sum Game C++解答例

AtCoder Beginner Contest 239 D - Prime Sum Game を C++で解きます。

問題

問題文をAtCoder のページより引用します。

問題文

高橋君と青木君が次のようなゲームをします。

• まず、高橋君が$A$以上$B$以下の好きな整数を選び、青木君に伝える
• 次に、青木君が$C$以上$D$以下の好きな整数を選ぶ
• 二人の選んだ整数の和が素数なら青木君の勝ち、そうでなければ高橋君の勝ち

二人が最適な戦略を取るとき、どちらが勝ちますか？

制約

• $1 \leq A \leq B \leq 100$
• $1 \leq C \leq D \leq 100$
• 入力に含まれる値は全て整数である

解答例

高橋君の勝利条件を考える

高橋君の勝利条件は、高橋君が選んだ数と、その後に青木君が選んだ数の和が素数にならないことです。

したがって、青木君が出せる数のうちどれを青木君が選んでも和が素数にならない数を高橋君が 1 つでも持っているとき、高橋君は必ず勝つことができます。
逆に、そのような数を高橋君が 1 つも持っていないとき、高橋君がどの数を出そうとも、青木君は和が素数になるような数を出して勝利することができます。

この問題では制約が緩いので、あり得る数を全探索して解を求めます。

プログラム実装例

C++のプログラム実装例を以下に示します。
今回の問題は制約が非常に緩いので、全探索の都度素数判定を行っても十分間に合いますが、ここではエラトステネスの篩を使って高速に素数判定を行っています。

d.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

class EratosthenesSieve {
 public:
  int64_t Number_;
  std::vector<bool> is_prime_;
  std::vector<int64_t> primes_;
  std::vector<int64_t> minimum_factor_;

  EratosthenesSieve(int64_t N)
      : Number_(N),
        is_prime_(N + 1, true),
        primes_(0),
        minimum_factor_(N + 1, -1) {
    is_prime_.at(1) = false;
    minimum_factor_.at(1) = 1;

    for (int64_t p = 2; p <= N; p++) {
      if (!is_prime_.at(p)) continue;

      primes_.push_back(p);
      minimum_factor_.at(p) = p;

      for (int64_t q = p * 2; q <= N; q += p) {
        is_prime_.at(q) = false;

        if (minimum_factor_.at(q) == -1) {
          minimum_factor_.at(q) = p;
        }
      }
    }
  }

  std::vector<std::pair<int64_t, int64_t>> factorize(int64_t N) {
    if (N > Number_) return {};
    std::vector<std::pair<int64_t, int64_t>> result;
    while (N > 1) {
      int64_t p = minimum_factor_.at(N);
      int64_t exp = 0;

      while (minimum_factor_.at(N) == p) {
        N /= p;
        exp++;
      }
      result.push_back(std::make_pair(p, exp));
    }

    return result;
  }

  std::vector<int64_t> dividers(int64_t N) {
    if (N > Number_) return {};
    std::vector<int64_t> result = {1};

    auto primes = factorize(N);

    for (auto p : primes) {
      int64_t size = static_cast<int64_t>(result.size());
      for (int64_t i = 0; i < size; i++) {
        int64_t v = 1;
        for (int64_t j = 0; j < p.second; j++) {
          v *= p.first;
          result.push_back(result.at(i) * v);
        }
      }
    }

    std::sort(result.begin(), result.end());
    return result;
  }

  std::vector<int64_t> primes(void) { return primes_; }

  std::vector<bool> is_prime(void) { return is_prime_; }
};

int main() {
  int64_t A, B, C, D;
  std::cin >> A >> B >> C >> D;

  // 2つの数の和は200を超えないので1000までの篩を作っておけば十分
  EratosthenesSieve es(1000);
  auto is_prime = es.is_prime();

  // 高橋君が必ず勝てるかどうかのフラグ変数
  bool flag = false;
  // 高橋君が出せる全ての数について探索
  for (int64_t i = A; i <= B; i++) {
    // 高橋君が出した数iに対して青木君が勝つ手があるかどうかを表すフラグ変数
    bool aoki = false;
    // 青木君が出せる全ての数について探索
    for (int64_t j = C; j <= D; j++) {
      // 和を計算
      int64_t sum = i + j;

      // 素数判定
      if (is_prime.at(sum)) {
        aoki = true;
      }
    }

    // 青木君がどうやっても勝てないiがあるなら、高橋君は必ず勝てる
    if (!aoki) flag = true;
  }

  // 出力
  if (flag) {
    std::cout << "Takahashi" << std::endl;
  } else {
    std::cout << "Aoki" << std::endl;
  }

  return 0;
}

実際に提出したコードはこちら。