結果

問題 No.7 プライムナンバーゲーム
ユーザー suzusuzu
提出日時 2023-05-02 13:51:48
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 59 ms / 5,000 ms
コード長 1,603 bytes
コンパイル時間 2,149 ms
コンパイル使用メモリ 112,076 KB
実行使用メモリ 27,500 KB
最終ジャッジ日時 2024-05-01 03:59:24
合計ジャッジ時間 3,470 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 22 ms
22,836 KB
testcase_01 AC 22 ms
24,940 KB
testcase_02 AC 57 ms
27,500 KB
testcase_03 AC 25 ms
25,076 KB
testcase_04 AC 24 ms
26,904 KB
testcase_05 AC 23 ms
24,748 KB
testcase_06 AC 33 ms
25,316 KB
testcase_07 AC 29 ms
25,148 KB
testcase_08 AC 25 ms
26,988 KB
testcase_09 AC 38 ms
24,956 KB
testcase_10 AC 24 ms
24,952 KB
testcase_11 AC 30 ms
25,008 KB
testcase_12 AC 48 ms
25,120 KB
testcase_13 AC 50 ms
25,396 KB
testcase_14 AC 59 ms
25,076 KB
testcase_15 AC 58 ms
23,352 KB
testcase_16 AC 53 ms
25,332 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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