sosuu daihinmin solver

solver.cpp

// #include <boost/multiprecision/cpp_int.hpp>
// #include <boost/multiprecision/miller_rabin.hpp>
// #include <boost/random/mersenne_twister.hpp>
#include <gmpxx.h>

#include "bits/stdc++.h"
//#include "json.hpp"
#include "nlohmann/json.hpp"
using namespace std;
// namespace mp = boost::multiprecision;

using ll = long long;
using T = mpz_class;

// XorShift 乱数生成器
// verified:
// https://atcoder.jp/contests/rco-contest-2019-qual/submissions/4237801
struct XorShift {
  using result_type = uint32_t;
  result_type w = 123456789, x = 362436069, y = 521288629, z = 88675123;
  XorShift(result_type seed = time(nullptr)) {
    w = seed;
    x = w << 13;
    y = (w >> 9) ^ (x << 6);
    z = y >> 7;
  }
  static constexpr result_type min() { return 0; }
  static constexpr result_type max() { return 0x7FFFFFFF; }
  result_type operator()() {
    result_type t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    return w = (w ^ (w >> 19) ^ (t ^ (t >> 8)));
  }
  result_type rand() {
    result_type t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    return w = (w ^ (w >> 19) ^ (t ^ (t >> 8)));
  }
  // [min,max] の整数値乱数
  result_type randInt(result_type min = 0, result_type max = 0x7FFFFFFF) {
    return rand() % (max - min + 1) + min;
  }
  // [min,max] の浮動小数点乱数
  double randDouble(double min = 0, double max = 1) {
    return (double)(rand() % 0xFFFF) / 0xFFFF * (max - min) + min;
  }
};

XorShift rnd(114514);

// constexpr ll TIME_LIMIT = 90000;

const string BELPHEGOR = "1000000000000066600000000000001";
vector<string> MERSENNE = {
    "3",
    //    "7",
    "31", "127", "8191", "131071", "524287", "2147483647",
    "2305843009213693951", "618970019642690137449562111",
    "162259276829213363391578010288127",
    "170141183460469231731687303715884105727",
    "68647976601306097149819007990813932172694353001433054093944634591855431833"
    "97656052122559640661454554977296311391480858037121987999716643812574028291"
    "115057151",
    "53113799281676709868958820655246862732959311772703192319944413820040355986"
    "08522427391625022652292856688893294862465010153465793376527072394095199787"
    "66587351943831270835393219031728127",
    "10407932194664399081925240327364085538615262247266704805319112350403608059"
    "67336029801223944173232418484242161395428100779138356624832346490813990660"
    "56773207629241295093892203457731833496615835504729594205476898112116936771"
    "47548478866962501384438260291732348885311160828538416585028255604666224831"
    "89091880184706822220314052102669843548873295802887805086973618690071472071"
    "0555703168729087"};

// sieve of eratosthenes
// primes[i] != 0 if i is prime
std::vector<int> sieve_of_eratosthenes(int n) {
  std::vector<int> primes(n, 0);
  for (int i = 2; i < n; ++i) primes[i] = i;
  for (int i = 2; i * i < n; ++i)
    if (primes[i])
      for (int j = i * i; j < n; j += i) primes[j] = 0;
  vector<int> ret;
  for (int i = 2; i < n; i++)
    if (primes[i]) ret.push_back(i);
  return ret;
}

const int MAX_N = 100000, MAX_N_six = 1000000;
vector<int> primes, primes_six;
vector<int> hand;
vector<int> cardCount(10, 0);
T last_number = 0;
int numbers_length_sum = 0;
int five_digit_index = -1;

void input_init(const nlohmann::json &obj) {
  /*
  {
      "action": "init",
      "uid": プレイヤーの順番, int
      "names": 全プレイヤーの名前, vector<string>
      "hand": 自分の手札, vector<int>
      "time": 制限時間, double
  }
  */
}

void input_play(const nlohmann::json &obj) {
  /**
  {
      "action": "play",
      "name": 自分の名前, string
      "hand": 自分の手札, vector<int>
      "numbers": 場札のリスト, vector<string>
      "hands": プレイヤーの名前とその手札の枚数の組のリスト,
  vector<pair<string,int>> "record": プレイ履歴,
  vector<tuple<string, string, int, vector<string>>>
  }
   */
  hand.clear();
  for (int i = 0; i < 10; i++) cardCount[i] = 0;
  for (const auto val : obj["hand"]) {
    assert(0 <= val && val <= 9);
    hand.push_back(int(val));
    cardCount[val]++;
  }

  last_number = 0;
  numbers_length_sum = 0;
  mpz_class m;
  for (const auto &number : obj["numbers"]) {
    numbers_length_sum += string(number).size();
    m.set_str(number, 10);
    last_number = m;
  }
}

void remove_newline(std::string &s) {
  std::string target("\n");
  std::string::size_type pos = s.find(target);
  while (pos != std::string::npos) {
    s.replace(pos, target.size(), "");
    pos = s.find(target, pos);
  }
}

void output_play(const vector<int> &ret) {
  /**
  {
      "action": "number",
      "cards": [場に出すカードのリスト], vector<int>
  }
   */
  nlohmann::json out;
  if (ret.size() == 0) {
    out["action"] = "pass";
  } else {
    out["action"] = "number";
    out["cards"] = ret;
  }
  string json(out.dump());
  remove_newline(json);
  cout << json << endl << flush;
}

void output_pass() {
  /**
  {
      "action": "pass"
  }
   */
}

void input_pass(const nlohmann::json &obj) {
  /**
  {
      "action": "pass",
      "name": 自分の名前, string
      "draw": 場札から引いた札のリスト, vector<int> (size=5)
      "record": プレイ履歴
  }
   */
}

void output_flush() { cout << endl << flush; }

bool is_belphefor() {
  return (cardCount[0] >= 26 && cardCount[1] >= 2 && cardCount[6] >= 3);
}

// val を出せるか
bool is_available(const string &val) {
  vector<int> cnt(10, 0);
  for (const auto &c : val) {
    if(c < '0' || '9' < c) return false;
    //assert('0' <= c && c <= '9');
    cnt[c - '0']++;
  }
  for (int i = 0; i <= 9; i++) {
    if (cardCount[i] < cnt[i]) return false;
  }
  return true;
}

// return: 可能ならそのインデックス, そうでなければ -1
int is_mersenne() {
  if (numbers_length_sum == 0) {
    int sz = MERSENNE.size();
    for (int index = 0; index < sz; index++) {
      if (MERSENNE[index].size() > 5) continue;
      if (is_available(MERSENNE[index])) return index;
    }
  } else {
    int sz = MERSENNE.size();
    for (int index = 0; index < sz; index++) {
      if (MERSENNE[index].size() != numbers_length_sum) continue;
      if (!is_available(MERSENNE[index])) continue;
      if (last_number.get_str().size() == numbers_length_sum) {
        mpz_class m;
        m.set_str(MERSENNE[index], 10);
        if (m <= last_number) continue;
      }
      return index;
    }
  }
  return -1;
}

vector<int> str_to_list(const string &vs) {
  vector<int> ret;
  for (const auto &v : vs) {
    assert('0' <= v && v <= '9');
    ret.push_back(v - '0');
  }
  return ret;
}

vector<int> mp_to_list(T val) {
  vector<int> ret;
  while (val) {
    T v = val % 10;
    ret.push_back(v.get_si());
    val /= 10;
  }
  return ret;
}

T vec_to_mpz(const vector<int> &v) {
  T ret(0);
  for (auto val : v) {
    ret *= 10;
    ret += val;
  }
  return ret;
}

const int TRY_COUNT = 200000;

vector<int> solve() {
  vector<int> ret;
  if (is_belphefor()) {
    return str_to_list(BELPHEGOR);
  }
  if (numbers_length_sum == 0 && is_available("99991")) {
    return str_to_list("99991");
  }
  if (numbers_length_sum == 0 && (int)hand.size() <= 5) {
    sort(hand.begin(), hand.end());
    do {
      if (hand[0] == 0) continue;
      auto m = vec_to_mpz(hand);
      if (mpz_probab_prime_p(m.get_mpz_t(), 100)) {
        return str_to_list(m.get_str());
      }
    } while (next_permutation(hand.begin(), hand.end()));
  }
  if (numbers_length_sum == (int)hand.size() && numbers_length_sum <= 8) {
    sort(hand.begin(), hand.end());
    do {
      if (hand[0] == 0) continue;
      auto m = vec_to_mpz(hand);
      if (mpz_probab_prime_p(m.get_mpz_t(), 100) && last_number < m) {
        return str_to_list(m.get_str());
      }
    } while (next_permutation(hand.begin(), hand.end()));
  }
  int index = is_mersenne();
  if (index != -1) {
    return str_to_list(MERSENNE[index]);
  }

  if (numbers_length_sum == 0) {
    int psz = primes.size();
    for (int kaf = 0; kaf < TRY_COUNT; kaf++) {
      int index = rnd.randInt(five_digit_index, psz - 1);
      if (is_available(to_string(primes[index]))) {
        return str_to_list(to_string(primes[index]));
      }
    }
    for (int i = psz - 1; i >= 0; i--) {
      if (is_available(to_string(primes[i]))) {
        return str_to_list(to_string(primes[i]));
      }
    }
    return ret;
  }

  if (numbers_length_sum <= 6) {
    int psz = primes_six.size();
    for (int kaf = 0; kaf < TRY_COUNT; kaf++) {
      int index = rnd.randInt(0, psz - 1);
      if (primes_six[index] <= last_number) continue;
      if (to_string(primes_six[index]).size() != numbers_length_sum) continue;
      if (is_available(to_string(primes_six[index]))) {
        return str_to_list(to_string(primes_six[index]));
      }
    }
    for (int i = psz - 1; i >= 0; i--) {
      if (primes_six[i] <= last_number) continue;
      if (to_string(primes_six[i]).size() != numbers_length_sum) continue;
      if (is_available(to_string(primes_six[i]))) {
        return str_to_list(to_string(primes_six[i]));
      }
    }
    return ret;
  }

  vector<int> upper, lower;
  for (auto v : hand) {
    if (v == 0 || v == 2 || v == 4 || v == 5 || v == 6 || v == 8) {
      upper.push_back(v);
    } else {
      lower.push_back(v);
    }
  }
  for (int kaf = 0; kaf < TRY_COUNT; kaf++) {
    if ((int)upper.size() < numbers_length_sum - 1) break;
    if ((int)lower.size() == 0) break;
    shuffle(upper.begin(), upper.end(), rnd);
    shuffle(lower.begin(), lower.end(), rnd);
    if (upper[0] == 0) continue;
    string s = "";
    for (int i = 0; i < numbers_length_sum - 1; i++) {
      s += char('0' + upper[i]);
    }
    s += char('0' + lower[0]);
    mpz_class m;
    m.set_str(s, 10);
    if (m <= last_number) continue;
    if (!is_available(s)) continue;
    if (mpz_probab_prime_p(m.get_mpz_t(), 100)) {
      return str_to_list(s);
    }
  }
  for (int kaf = 0; kaf < TRY_COUNT; kaf++) {
    if((int)hand.size() < numbers_length_sum) break;
    shuffle(hand.begin(), hand.end(), rnd);
    if (hand[0] == 0) continue;
    string s = "";
    for (int i = 0; i < numbers_length_sum; i++) {
      s += char('0' + hand[i]);
    }
    T m;
    m.set_str(s, 10);
    if (m <= last_number) continue;
    if (!is_available(s)) continue;
    if (mpz_probab_prime_p(m.get_mpz_t(), 100)) {
      return str_to_list(s);
    }
  }
  return ret;
}

int main() {
  primes = sieve_of_eratosthenes(MAX_N);
  primes_six = sieve_of_eratosthenes(MAX_N_six);
  for (int i = 0; i < (int)primes.size(); i++) {
    if (primes[i] <= 9999) five_digit_index = i + 1;
  }
  reverse(MERSENNE.begin(), MERSENNE.end());

  while (true) {
    string s;
    getline(cin, s);
    auto obj = nlohmann::json::parse(s);
    auto action = string(obj["action"]);

    if (action == "init") {
      input_init(obj);
      output_flush();
      continue;
    }
    if (action == "quit") {
      output_flush();
      break;
    }
    if (action == "pass") {
      input_pass(obj);
      output_flush();
      continue;
    }
    assert(action == "play");
    input_play(obj);
    auto ret = solve();
    output_play(ret);
  }
  return 0;
}

第8回 フィックスターズ社内プログラミングコンテスト 素数大貧民ソルバ
https://proc-cpuinfo.fixstars.com/2020/07/in-house-procon-08-result/