結果

問題 No.7 プライムナンバーゲーム
ユーザー te-shte-sh
提出日時 2016-08-27 19:39:42
言語 D
(dmd 2.106.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,084 bytes
コンパイル時間 404 ms
コンパイル使用メモリ 131,160 KB
最終ジャッジ日時 2024-11-14 19:48:50
合計ジャッジ時間 783 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Main.d(24): Error: cannot implicitly convert expression `memo[cast(ulong)n]` of type `Nullable!bool` to `bool`

ソースコード

diff # 

import std.algorithm, std.array, std.container, std.range;
import std.string, std.conv, std.math;
import std.stdio, std.typecons;

void main()
{
  auto n = readln.chomp.to!int;

  auto primes = primes(n);
  primes.reverse();
  auto memo = new Nullable!bool[n + 1];
  auto r = dp(n, true, primes, memo);

  writeln(r ? "Win" : "Lose");
}

bool dp(int n, bool turn, int[] primes, Nullable!bool[] memo)
{
  bool winner_is_me;

  if (n == 0 || n == 1) {
    winner_is_me = true;
  } else if (!memo[n].isNull) {
    winner_is_me = memo[n];
  } else {
    winner_is_me = primes
      .find!(a => a < n)
      .any!(p => dp(n - p, !turn, primes, memo) == turn);
  }

  memo[n] = winner_is_me;
  return !(winner_is_me ^ turn);
}

int[] primes(int n)
{
  auto sieve = new bool[n + 1];
  sieve.fill(true);

  auto max = sqrt(n.to!real).to!int;
  for (auto p = 2; p <= max; ++p) {
    if (sieve[p]) {
      for (auto q = p * 2; q <= n; q += p) {
        sieve[q] = false;
      }
    }
  }

  int[] r;
  for (auto p = 2; p <= n; ++p) {
    if (sieve[p]) {
      r ~= p;
    }
  }

  return r;
}
0