結果

問題 No.6 使いものにならないハッシュ
ユーザー penqenpenqen
提出日時 2021-03-15 22:26:00
言語 Elixir
(1.16.2)
結果
WA  
実行時間 -
コード長 3,540 bytes
コンパイル時間 1,263 ms
コンパイル使用メモリ 57,316 KB
実行使用メモリ 51,508 KB
最終ジャッジ日時 2023-08-30 01:19:33
合計ジャッジ時間 26,126 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

defmodule Main do
  import Integer, only: [is_odd: 1]
  defmodule Prime do
    defstruct value: 2
    def next(factor \\ %__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
    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