結果

問題 No.7 プライムナンバーゲーム
ユーザー suzu
提出日時 2023-05-02 13:51:48
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 67 ms / 5,000 ms
コード長 1,603 bytes
コンパイル時間 3,099 ms
コンパイル使用メモリ 107,008 KB
実行使用メモリ 19,328 KB
最終ジャッジ日時 2024-11-21 04:57:46
合計ジャッジ時間 2,512 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
	static List<int> primeList = new List<int>();
	static bool[,] memo;//探索フラグとその数字が自分に回ってきたとき勝てるかどうか
    static void Main(string[] args)
    {
    	int N = int.Parse(Console.ReadLine());
    	PrimeCheck(N);
    	
    	memo = new bool[N + 1,2];
    	
    	memo[0,0] = memo[0,1] = true;
    	memo[1,0] = memo[1,1] = true;//探索済み。また、０・１が自分に回った来たとき勝確
    	
    	if(judgementCheck(N))
    	{
    		Console.WriteLine("Win");	
    	}else
    	{
    		Console.WriteLine("Lose");
    	}
    	
    	
    }
    static bool judgementCheck(int N)
    {
    	if(memo[N,0])
    	{
    		return memo[N,1];
    	}
    	memo[N,0] = true;
    	foreach(int a in primeList)
    	{
    		if(a <= N)
    		{
    			if(!judgementCheck(N - a		))//相手に負確数字を与えられるとき
    			{
    				return memo[N,1] = true;
    			}
    		}
    	}
    	return false;
    }
    static void PrimeCheck(int N)
    {
    	bool[] array = Enumerable.Repeat(true,N + 1).ToArray();
    	
    	array[0] = array[1] = false;
    	for(int i = 4;i < N + 1;i += 2)
    	{
    		array[i] = false;
    	}
    	
    	for(int i = 3;i <= (int)Math.Sqrt((double)N);i += 2)
    	{
    		if(array[i])
    		{
    			for(int m = i * i;m <= N;m += i)
    			{
    				array[m] = false;
    			}
    		}
    	}
    	
    	for(int i = 2;i <= N;i++)
    	{
    		if(array[i])
    		{
    			primeList.Add(i);
    		}
    	}
    }
    //Himatsubushin様参考
}
0