結果
問題 | No.6 使いものにならないハッシュ |
ユーザー | penqen |
提出日時 | 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 |
ソースコード
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