結果

問題 No.6 使いものにならないハッシュ
ユーザー penqenpenqen
提出日時 2021-03-15 22:28:14
言語 Elixir
(1.16.2)
結果
AC  
実行時間 652 ms / 5,000 ms
コード長 3,547 bytes
コンパイル時間 1,057 ms
コンパイル使用メモリ 68,872 KB
実行使用メモリ 56,552 KB
最終ジャッジ日時 2024-06-10 00:32:09
合計ジャッジ時間 21,784 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 563 ms
54,516 KB
testcase_01 AC 547 ms
54,916 KB
testcase_02 AC 652 ms
54,940 KB
testcase_03 AC 583 ms
54,552 KB
testcase_04 AC 577 ms
54,616 KB
testcase_05 AC 596 ms
54,476 KB
testcase_06 AC 631 ms
55,360 KB
testcase_07 AC 596 ms
54,396 KB
testcase_08 AC 616 ms
54,508 KB
testcase_09 AC 622 ms
54,248 KB
testcase_10 AC 611 ms
54,124 KB
testcase_11 AC 588 ms
55,612 KB
testcase_12 AC 605 ms
54,384 KB
testcase_13 AC 556 ms
54,804 KB
testcase_14 AC 555 ms
54,724 KB
testcase_15 AC 593 ms
54,524 KB
testcase_16 AC 577 ms
54,600 KB
testcase_17 AC 635 ms
55,116 KB
testcase_18 AC 640 ms
55,124 KB
testcase_19 AC 616 ms
54,476 KB
testcase_20 AC 620 ms
55,024 KB
testcase_21 AC 560 ms
54,412 KB
testcase_22 AC 598 ms
54,288 KB
testcase_23 AC 608 ms
54,940 KB
testcase_24 AC 624 ms
56,552 KB
testcase_25 AC 589 ms
55,100 KB
testcase_26 AC 631 ms
54,632 KB
testcase_27 AC 602 ms
54,988 KB
testcase_28 AC 590 ms
54,376 KB
testcase_29 AC 631 ms
55,144 KB
testcase_30 AC 616 ms
54,380 KB
testcase_31 AC 620 ms
54,792 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
    warning: missing parentheses for expression following "do:" keyword. Parentheses are required to solve ambiguity inside keywords.

    This error happens when you have function calls without parentheses inside keywords. For example:

        function(arg, one: nested_call a, b, c)
        function(arg, one: if expr, do: :this, else: :that)

    In the examples above, we don't know if the arguments "b" and "c" apply to the function "function" or "nested_call". Or if the keywords "do" and "else" apply to the function "function" or "if". You can solve this by explicitly adding parentheses:

        function(arg, one: if(expr, do: :this, else: :that))
        function(arg, one: nested_call(a, b, c))

    Ambiguity found at:
    │
 15 │     def first(n) when is_odd(n), do: if is_prime(n), do: n, else: first(n + 2)
    │     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    │
    └─ Main.exs:15

    warning: missing parentheses for expression following "do:" keyword. Parentheses are required to solve ambiguity inside keywords.

    This error happens when you have function calls without parentheses inside keywords. For example:

        function(arg, one: nested_call a, b, c)
        function(arg, one: if expr, do: :this, else: :that)

    In the examples above, we don't know if the arguments "b" and "c" apply to the function "function" or "nested_call". Or if the keywords "do" and "else" apply to the function "function" or "if". You can solve this by explicitly adding parentheses:

        function(arg, one: if(expr, do: :this, else: :that))
        function(arg, one: nested_call(a, b, c))

    Ambiguity found at:
    │
 23 │       do: if rem(n, 2) == 0, do: false, else: is_prime(n, 3)
    │       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    │
    └─ Main.exs:23

    warning: missing parentheses for expression following "do:" keyword. Parentheses are required to solve ambiguity inside keywords.

    T

ソースコード

diff # 

defmodule Main do
  import Integer, only: [is_odd: 1]
  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 first(1), do: 2
    def first(2), do: 2
    def first(3), do: 3
    def first(n) when is_odd(n), do: if is_prime(n), do: n, else: first(n + 2)
    def first(n), do: first(n + 1)

    def is_prime(n)
    def is_prime(n) when n < 2, do: false
    def is_prime(2), do: true
    def is_prime(3), do: true
    def is_prime(n) when 3 < n,
      do: if rem(n, 2) == 0, do: false, else: is_prime(n, 3)
    defp is_prime(n, i) when i * i <= n,
      do: if rem(n, i) == 0, do: false, else: is_prime(n, i + 2)
    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

  defp r_to_i, do: IO.read(:line) |> String.trim() |> String.to_integer()

  def main do
    IO.puts solve(r_to_i(), r_to_i())
  end

  def solve(k, n) do
    %Prime{value: Prime.first(k)}
    |> Enum.reduce_while({%{}, nil, nil}, fn
      prime, acc when n < prime ->
        {:halt, acc}
      prime, {memo, nil, max} ->
        {:cont, {Map.put(memo, prime, MapSet.new([frank_hash(prime)])), [prime], max}}
      prime, {memo, start_with, max} ->
        hashed_value = frank_hash(prime)
        memo = Map.put(memo, prime, MapSet.new([hashed_value]))
        {memo, max, complete} = start_with
        |> Enum.reduce({memo, max, []}, fn target, {memo, max, complete} ->
          if MapSet.member?(memo[target], hashed_value) do
            with max when not is_nil(max) <- max,
              true <- MapSet.size(memo[max]) <= MapSet.size(memo[target]),
              true <- max < target do
              {memo, target, [max | complete]}
            else
              nil ->
                {memo, target, complete}
              _ ->
                {memo, max, [target | complete]}
            end
          else
            {Map.put(memo, target, MapSet.put(memo[target], hashed_value)), max, complete}
          end
        end)
        {
          :cont,
          {
            Enum.reduce(complete, memo, fn
              v, memo when v == max -> memo
              v, memo -> Map.delete(memo, v)
            end),
            Enum.reject([prime | start_with], fn v -> v in complete end),
            max
          }
        }
    end)
    |> (fn {memo, start_with, max} ->
        start_with
        |> Enum.reduce({memo, max}, fn
          target, {memo, max} ->
            with max when not is_nil(max) <- max,
              true <- MapSet.size(memo[max]) <= MapSet.size(memo[target]),
              true <- max < target do
              {memo, target}
            else
              nil ->
                {memo, target}
              _ ->
                {memo, max}
            end
        end)
        |> elem(1)
    end).()
  end

  defp frank_hash(n) when n < 10, do: n
  defp frank_hash(n), do: n |> Integer.digits() |> Enum.sum() |> frank_hash()
end
0