結果

問題 No.6 使いものにならないハッシュ
ユーザー penqenpenqen
提出日時 2021-03-15 22:28:14
言語 Elixir
(1.16.2)
結果
AC  
実行時間 680 ms / 5,000 ms
コード長 3,547 bytes
コンパイル時間 1,247 ms
コンパイル使用メモリ 58,000 KB
実行使用メモリ 50,444 KB
最終ジャッジ日時 2023-08-30 01:20:12
合計ジャッジ時間 23,148 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 565 ms
49,472 KB
testcase_01 AC 567 ms
50,276 KB
testcase_02 AC 679 ms
49,544 KB
testcase_03 AC 585 ms
49,572 KB
testcase_04 AC 591 ms
49,652 KB
testcase_05 AC 597 ms
49,772 KB
testcase_06 AC 625 ms
49,588 KB
testcase_07 AC 601 ms
50,116 KB
testcase_08 AC 620 ms
50,396 KB
testcase_09 AC 592 ms
49,780 KB
testcase_10 AC 576 ms
49,712 KB
testcase_11 AC 588 ms
49,696 KB
testcase_12 AC 642 ms
50,020 KB
testcase_13 AC 588 ms
50,444 KB
testcase_14 AC 594 ms
50,388 KB
testcase_15 AC 632 ms
50,160 KB
testcase_16 AC 618 ms
50,148 KB
testcase_17 AC 658 ms
49,600 KB
testcase_18 AC 680 ms
50,324 KB
testcase_19 AC 665 ms
49,576 KB
testcase_20 AC 644 ms
49,772 KB
testcase_21 AC 583 ms
49,900 KB
testcase_22 AC 657 ms
49,536 KB
testcase_23 AC 652 ms
50,168 KB
testcase_24 AC 661 ms
50,172 KB
testcase_25 AC 622 ms
49,620 KB
testcase_26 AC 661 ms
49,736 KB
testcase_27 AC 641 ms
49,468 KB
testcase_28 AC 612 ms
49,628 KB
testcase_29 AC 660 ms
50,108 KB
testcase_30 AC 654 ms
49,780 KB
testcase_31 AC 645 ms
49,524 KB
権限があれば一括ダウンロードができます

ソースコード

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