結果

問題 No.2 素因数ゲーム
ユーザー バカらっくバカらっく
提出日時 2017-06-25 14:27:15
言語 C#(csc)
(csc 3.9.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,877 bytes
コンパイル時間 1,947 ms
コンパイル使用メモリ 117,160 KB
実行使用メモリ 192,140 KB
最終ジャッジ日時 2024-06-08 00:44:18
合計ジャッジ時間 41,909 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
25,176 KB
testcase_01 AC 36 ms
25,436 KB
testcase_02 AC 40 ms
25,464 KB
testcase_03 AC 39 ms
25,648 KB
testcase_04 AC 38 ms
25,420 KB
testcase_05 AC 39 ms
25,312 KB
testcase_06 AC 186 ms
49,488 KB
testcase_07 AC 213 ms
55,248 KB
testcase_08 AC 199 ms
47,372 KB
testcase_09 AC 2,945 ms
192,140 KB
testcase_10 AC 2,456 ms
171,280 KB
testcase_11 AC 952 ms
99,520 KB
testcase_12 AC 986 ms
97,404 KB
testcase_13 WA -
testcase_14 AC 133 ms
38,104 KB
testcase_15 AC 446 ms
69,584 KB
testcase_16 AC 1,630 ms
119,296 KB
testcase_17 AC 2,570 ms
173,820 KB
testcase_18 AC 2,761 ms
183,120 KB
testcase_19 AC 1,526 ms
116,636 KB
testcase_20 AC 2,075 ms
146,180 KB
testcase_21 AC 2,911 ms
188,076 KB
testcase_22 AC 2,636 ms
179,244 KB
testcase_23 AC 1,127 ms
99,684 KB
testcase_24 AC 2,860 ms
177,360 KB
testcase_25 AC 1,954 ms
141,232 KB
testcase_26 AC 1,286 ms
111,748 KB
testcase_27 AC 557 ms
72,696 KB
testcase_28 AC 1,535 ms
119,640 KB
testcase_29 AC 1,165 ms
100,992 KB
testcase_30 AC 1,089 ms
96,640 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.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

    public void Proc()
    {
        int num = int.Parse(Reader.ReadLine());
        CreatePrimeList(num);
        string ans = "Bob";
        if(IsWin(PrimeDevide(num).Select(a=>a.Value).OrderBy(a=>a).ToList())) {
            ans = "Alice";
        }
        Console.WriteLine(ans);
    }

    private Dictionary<int, int> PrimeDevide(int num) {
        int tmp = num;
        Dictionary<int, int> ret = new Dictionary<int, int>();
        int idx = 0;
        while(tmp>1) {
            if(tmp%PrimeList[idx]==0) {
                if(!ret.ContainsKey(PrimeList[idx])) {
                    ret.Add(PrimeList[idx], 1);
                } else {
                    ret[PrimeList[idx]]++;
                }
                tmp = tmp / PrimeList[idx];
            } else {
                idx++;
            }
        }
        return ret;
    }
    private void CreatePrimeList(int num) {
        bool[] flags = new bool[num + 1];
        List<int> list = new List<int>();
        for (int i = 2; i < flags.Length; i++) {
            if (flags[i]) {
                continue;
            }
            list.Add(i);
            int max = num / i;
            for (int j = 1; j <= max; j++) {
                flags[i * j] = true;
            }
        }
        this.PrimeList = list.ToArray();
    }

    private Dictionary<string, bool> dic = new Dictionary<string, bool>();
    private bool IsWin(List<int> list) {
        string key = string.Join("#", list);
        if(dic.ContainsKey(key)) {
            return dic[key];
        }
        if(list.Count == 0) {
            dic[key] = false;
            return false;
        }
        if(list.Count == 1) {
            dic[key] = true;
            return true;
        }
        bool canWin = false;
        int idx = -1;
        if (list.Any(a => a > 2))
        {
            idx = list.FindIndex(a => a > 2);
            List<int> subList = new List<int>(list);
            subList[idx] = 2;
            bool ret = IsWin(subList.OrderBy(a => a).ToList());
            if(!ret) {
                canWin = true;
            }
            if (!canWin) {
                subList = new List<int>(list);
                subList[idx] = 1;
                ret = IsWin(subList.OrderBy(a => a).ToList());
				if (!ret)
				{
					canWin = true;
				}
			}
            if(!canWin) {
				subList = new List<int>(list);
                subList.RemoveAt(idx);
				ret = IsWin(subList);
				if (!ret)
				{
					canWin = true;
				}

			}
        }
        if((!canWin) && list.Any(a=>a==2)) {
			idx = list.FindIndex(a => a == 2);
			List<int> subList = new List<int>(list);
			subList[idx] = 1;
			bool ret = IsWin(subList.OrderBy(a => a).ToList());
			if (!ret)
			{
				canWin = true;
			}
			if (!canWin)
			{
				subList = new List<int>(list);
				subList.RemoveAt(idx);
				ret = IsWin(subList);
				if (!ret)
				{
					canWin = true;
				}

			}

		}
		if ((!canWin) && list.Any(a => a == 1))
		{
			idx = list.FindIndex(a => a == 1);
			List<int> subList = new List<int>(list);
            subList.RemoveAt(idx);
			bool ret = IsWin(subList);
			if (!ret)
			{
				canWin = true;
			}
		}
        dic[key] = canWin;
        return canWin;
    }



    private int[] PrimeList;

    public class Reader
	{
		private static StringReader sr;
		public static bool IsDebug = false;
		public static string ReadLine()
		{
			if (IsDebug)
			{
				if (sr == null)
				{
					sr = new StringReader(InputText.Trim());
				}
				return sr.ReadLine();
			}
			else
			{
				return Console.ReadLine();
			}
		}
		private static string InputText = @"





100000000




";
	}

	public static void Main(string[] args)
	{
#if DEBUG
		Reader.IsDebug = true;
#endif
		Program prg = new Program();
		prg.Proc();
	}
}
0