結果

問題 No.7 プライムナンバーゲーム
ユーザー suzusuzu
提出日時 2023-05-02 13:51:48
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 93 ms / 5,000 ms
コード長 1,603 bytes
コンパイル時間 3,699 ms
コンパイル使用メモリ 108,544 KB
実行使用メモリ 24,148 KB
最終ジャッジ日時 2023-08-13 10:38:45
合計ジャッジ時間 6,163 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 57 ms
23,668 KB
testcase_01 AC 57 ms
21,664 KB
testcase_02 AC 93 ms
24,148 KB
testcase_03 AC 59 ms
23,676 KB
testcase_04 AC 58 ms
21,652 KB
testcase_05 AC 58 ms
23,636 KB
testcase_06 AC 69 ms
21,964 KB
testcase_07 AC 66 ms
23,864 KB
testcase_08 AC 61 ms
23,896 KB
testcase_09 AC 74 ms
23,924 KB
testcase_10 AC 57 ms
23,736 KB
testcase_11 AC 65 ms
23,896 KB
testcase_12 AC 83 ms
21,960 KB
testcase_13 AC 85 ms
24,092 KB
testcase_14 AC 93 ms
22,104 KB
testcase_15 AC 93 ms
24,128 KB
testcase_16 AC 89 ms
22,196 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