結果

問題 No.7 プライムナンバーゲーム
ユーザー はむ吉🐹はむ吉🐹
提出日時 2016-05-03 16:55:16
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 119 ms / 5,000 ms
コード長 1,915 bytes
コンパイル時間 643 ms
コンパイル使用メモリ 73,904 KB
実行使用メモリ 6,696 KB
最終ジャッジ日時 2024-04-09 03:58:05
合計ジャッジ時間 2,228 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,564 KB
testcase_01 AC 1 ms
6,688 KB
testcase_02 AC 119 ms
6,688 KB
testcase_03 AC 10 ms
6,688 KB
testcase_04 AC 4 ms
6,692 KB
testcase_05 AC 4 ms
6,688 KB
testcase_06 AC 37 ms
6,692 KB
testcase_07 AC 26 ms
6,696 KB
testcase_08 AC 13 ms
6,692 KB
testcase_09 AC 55 ms
6,692 KB
testcase_10 AC 1 ms
6,688 KB
testcase_11 AC 26 ms
6,688 KB
testcase_12 AC 86 ms
6,692 KB
testcase_13 AC 91 ms
6,692 KB
testcase_14 AC 119 ms
6,692 KB
testcase_15 AC 113 ms
6,692 KB
testcase_16 AC 104 ms
6,692 KB
権限があれば一括ダウンロードができます

ソースコード

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