結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー はむ吉🐹
提出日時 2016-05-03 16:55:16
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 102 ms / 5,000 ms
コード長 1,915 bytes
コンパイル時間 662 ms
コンパイル使用メモリ 73,548 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-01 15:43:07
合計ジャッジ時間 1,866 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <set>
#include <vector>


constexpr int UNDEF = -1;
typedef std::set<int> GrundySet;


// 所与の整数(> 1)未満の素数を、Eratosthenesの篩により列挙するる
const std::vector<int> sieve_of_eratosthenes(const int& end) {
    assert(end > 1);
    std::vector<bool> is_prime(end, true);
    std::vector<int> primes;
    is_prime[0] = false;
    is_prime[1] = false;
    for (auto i = 2; i < end; i++)
    {
        if (is_prime[i]) {
            primes.push_back(i);
            for (auto j = 2 * i; j < end; j += i)
            {
                is_prime[j] = false;
            }
        }
    }
    return primes;
}


// 所与の集合に含まれない最小の非負整数を求める
// 参考 http://solorab.net/blog/2015/12/19/srm-676-med/
int mex(const GrundySet& s) {
    int m = 0;
    for (const auto& x : s) {
        if (x == m)
        {
            m++;
        }
        else
        {
            break;
        }
    }
    return m;
}


// 渡された数字がNであるという状態のGrundy数を計算する
int compute_grundy_number(int n) {
    std::vector<int> gs(std::max(n, 3) + 1, UNDEF);
    auto primes = sieve_of_eratosthenes(n + 1);
    // 渡された数字が2, 3であれば、負ける
    gs[2] = 0;
    gs[3] = 0;
    for (auto i = 4; i <= n; i++)
    {
        GrundySet next_gs;
        for (const auto& prime : primes) {
            auto cand = i - prime;
            if (cand < 2)
            {
                break;
            }
            next_gs.insert(gs[cand]);
        }
        gs[i] = mex(next_gs);
    }
    return gs[n];
}


int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int n;
    std::cin >> n;
    auto g = compute_grundy_number(n);
    std::cout << (g > 0 ? "Win" : "Lose") << std::endl;
    return EXIT_SUCCESS;
}
0