結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー @abcde
提出日時 2019-03-10 21:01:06
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 129 ms / 5,000 ms
コード長 2,351 bytes
コンパイル時間 1,314 ms
コンパイル使用メモリ 169,716 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-01 16:17:36
合計ジャッジ時間 4,444 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    
    // 2. 素数を用意する.
    // AtCoder Beginner Contest 084
    // https://atcoder.jp/contests/abc084
    map<int, int> m;
    m[2]++;
    // for(int i = 3; i < 1e4 + 1; i += 2) {
    for(int i = 3; i < 1e4 + 1; i += 2) {
        bool isPrime = true;
        for(int j = 3; j < sqrt(i) + 1; j += 2) {
            if(i % j == 0){
                isPrime = false;
                break;
            }
        }
        if(isPrime) m[i]++;
    }
    // for(auto &p : m) cout << p.first << " " << p.second << endl;
    
    // 3. 手番の勝ちパターンを集計.
    // 3-1. 先手勝ちパターンを集計.
    // -> 素数 に, 2 or 3 or 11 or 12 を加算した数字は, 先手勝ちパターンのはず.
    string ans[10002];
    for(int i = 0; i < 10002; i++) ans[i] = "init";
    ans[0] = "Nobody", ans[1] = "Nobody", ans[2] = "Lose", ans[3] = "Lose", ans[11] = "Lose", ans[12] = "Lose";
    for(int i = 2; i < 9999; i++) if(m[i] > 0) ans[i + 2] = "Win", ans[i + 3] = "Win";
    // for(int i = 0; i < 10002; i++) cout << "ans[" << i << "]=" << ans[i] << endl;
    
    // 3-2. 後手勝ちパターンを集計.
    for(int i = 13; i < 10001; i++){
        if(ans[i] == "Win" || ans[i] == "Lose") continue;
        int isWin = 0;
        for(auto &p : m){
            if(p.first >= i) break;
            int diff = i - p.first;
            // cout << i << " " << p.first << " " << ans[diff] << endl;
            // 先手から後手に手番を渡したときに, 
            // ans[diff] が, 後手勝ちのパターンであれば, 
            // ans[i] は, 先手勝ちパターンのはず.
            // -> p.second > 0 は, p.first が 素数 であることの条件.
            if(diff > 1 && p.second > 0 && ans[diff] == "Lose"){
                isWin++;
                break;
            }
        }
        if(isWin == 0) ans[i] = "Lose";
        if(isWin >  0) ans[i] = "Win";
    }
    // ans[27]=Lose は, 多分正しいはず.
    // for(int i = 0; i < 10002; i++) cout << "ans[" << i << "]=" << ans[i] << endl;
    // for(int i = 0; i < 10002; i++) if(i > 7100) cout << "ans[" << i << "]=" << ans[i] << endl;
    
    // 4. 出力.
    cout << ans[N] << endl;
    return 0;
    
}
0