結果

問題 No.7 プライムナンバーゲーム
ユーザー penqenpenqen
提出日時 2021-03-17 00:21:18
言語 Elixir
(1.16.2)
結果
AC  
実行時間 712 ms / 5,000 ms
コード長 1,922 bytes
コンパイル時間 2,670 ms
コンパイル使用メモリ 62,020 KB
実行使用メモリ 56,732 KB
最終ジャッジ日時 2024-04-09 05:03:35
合計ジャッジ時間 14,532 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 554 ms
54,488 KB
testcase_01 AC 552 ms
54,512 KB
testcase_02 AC 711 ms
55,948 KB
testcase_03 AC 561 ms
54,460 KB
testcase_04 AC 556 ms
54,724 KB
testcase_05 AC 562 ms
54,408 KB
testcase_06 AC 599 ms
55,772 KB
testcase_07 AC 579 ms
54,540 KB
testcase_08 AC 565 ms
55,004 KB
testcase_09 AC 624 ms
56,564 KB
testcase_10 AC 547 ms
54,640 KB
testcase_11 AC 584 ms
54,552 KB
testcase_12 AC 663 ms
56,680 KB
testcase_13 AC 668 ms
56,512 KB
testcase_14 AC 712 ms
56,332 KB
testcase_15 AC 702 ms
56,732 KB
testcase_16 AC 689 ms
56,080 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