結果

問題 No.7 プライムナンバーゲーム
ユーザー penqenpenqen
提出日時 2021-03-17 00:21:18
言語 Elixir
(1.16.2)
結果
AC  
実行時間 798 ms / 5,000 ms
コード長 1,922 bytes
コンパイル時間 4,412 ms
コンパイル使用メモリ 62,004 KB
実行使用メモリ 56,208 KB
最終ジャッジ日時 2024-10-01 16:43:21
合計ジャッジ時間 16,895 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 643 ms
54,056 KB
testcase_01 AC 635 ms
54,192 KB
testcase_02 AC 798 ms
56,208 KB
testcase_03 AC 638 ms
53,932 KB
testcase_04 AC 642 ms
54,244 KB
testcase_05 AC 642 ms
54,180 KB
testcase_06 AC 682 ms
54,684 KB
testcase_07 AC 671 ms
54,656 KB
testcase_08 AC 638 ms
54,152 KB
testcase_09 AC 597 ms
55,312 KB
testcase_10 AC 561 ms
54,116 KB
testcase_11 AC 665 ms
54,132 KB
testcase_12 AC 750 ms
55,772 KB
testcase_13 AC 763 ms
55,368 KB
testcase_14 AC 769 ms
55,860 KB
testcase_15 AC 669 ms
56,084 KB
testcase_16 AC 741 ms
55,760 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

defmodule Main do
  defmodule Prime do
    defstruct value: 2
    def next(prime \\ %__MODULE__{value: 2})
    def next(%__MODULE__{value: 2}), do: %__MODULE__{value: 3}
    def next(%__MODULE__{value: n} = prime) do
      if is_prime(n + 2),
        do: %{prime | value: n + 2},
        else: next(%{prime | value: n + 2})
    end

    def is_prime(n)
    def is_prime(n) when n < 2, do: false
    def is_prime(n) when n in [2, 3], do: true
    def is_prime(n) when 3 < n do
      if rem(n, 2) == 0, do: false, else: is_prime(n, 3)
    end
    defp is_prime(n, i) when i * i <= n do
      if rem(n, i) == 0, do: false, else: is_prime(n, i + 2)
    end
    defp is_prime(_, _), do: true

    defimpl Enumerable do
      def count(_), do: {:error, __MODULE__}
      def member?(_, _), do: {:error, __MODULE__}
      def slice(_), do: {:error, __MODULE__}
      def reduce(_prime, {:halt, acc}, _fun), do: {:halted, acc}
      def reduce(prime, {:suspend, acc}, fun), do: {:suspended, acc, &reduce(prime, &1, fun)}
      def reduce(%{value: v} = prime, {:cont, acc}, fun) do
        reduce(Prime.next(prime), fun.(v, acc), fun)
      end
    end
  end

  def main do
    IO.read(:line) |> String.trim() |> String.to_integer() |> solve()
    |> if do
      "Win"
    else
      "Lose"
    end
    |> IO.puts() 
  end

  def solve(n) do
    primes = Enum.reduce_while(%Prime{}, [], fn
      prime, primes when n < prime ->
        {:halt, Enum.reverse(primes)}
      prime, primes ->
        {:cont, [prime | primes]}
    end)

    memo = 2..n
    |> Enum.reduce(%{1 => false}, fn
      i, memo ->
        flag = primes
        |> Enum.reduce_while(false, fn
          _p, true -> {:halt, true}
          p, flag when i < p -> {:halt, flag}
          p, flag when i - p < 2 -> {:halt, flag}
          p, _flag ->
            {:cont, not(memo[i - p])}
        end)
        Map.put(memo, i, flag)
    end)

    memo[n]
  end
end
0