結果
問題 | No.3 ビットすごろく |
ユーザー | penqen |
提出日時 | 2021-03-12 23:32:25 |
言語 | Elixir (1.16.2) |
結果 |
AC
|
実行時間 | 644 ms / 5,000 ms |
コード長 | 5,091 bytes |
コンパイル時間 | 1,177 ms |
コンパイル使用メモリ | 59,352 KB |
実行使用メモリ | 54,008 KB |
最終ジャッジ日時 | 2023-08-30 01:18:31 |
合計ジャッジ時間 | 23,156 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 571 ms
50,268 KB |
testcase_01 | AC | 570 ms
50,244 KB |
testcase_02 | AC | 561 ms
49,580 KB |
testcase_03 | AC | 584 ms
50,400 KB |
testcase_04 | AC | 576 ms
49,416 KB |
testcase_05 | AC | 611 ms
52,296 KB |
testcase_06 | AC | 598 ms
50,528 KB |
testcase_07 | AC | 591 ms
49,876 KB |
testcase_08 | AC | 611 ms
50,920 KB |
testcase_09 | AC | 616 ms
52,668 KB |
testcase_10 | AC | 632 ms
53,964 KB |
testcase_11 | AC | 609 ms
52,292 KB |
testcase_12 | AC | 606 ms
52,264 KB |
testcase_13 | AC | 589 ms
49,868 KB |
testcase_14 | AC | 626 ms
53,784 KB |
testcase_15 | AC | 638 ms
53,364 KB |
testcase_16 | AC | 631 ms
53,504 KB |
testcase_17 | AC | 635 ms
53,268 KB |
testcase_18 | AC | 585 ms
50,328 KB |
testcase_19 | AC | 641 ms
53,220 KB |
testcase_20 | AC | 573 ms
49,712 KB |
testcase_21 | AC | 570 ms
49,560 KB |
testcase_22 | AC | 623 ms
54,008 KB |
testcase_23 | AC | 636 ms
53,272 KB |
testcase_24 | AC | 644 ms
53,780 KB |
testcase_25 | AC | 636 ms
53,120 KB |
testcase_26 | AC | 568 ms
50,032 KB |
testcase_27 | AC | 586 ms
50,128 KB |
testcase_28 | AC | 628 ms
53,224 KB |
testcase_29 | AC | 615 ms
52,816 KB |
testcase_30 | AC | 575 ms
50,404 KB |
testcase_31 | AC | 574 ms
49,492 KB |
testcase_32 | AC | 611 ms
52,268 KB |
ソースコード
defmodule Main do def main do IO.read(:line) |> String.trim() |> String.to_integer() |> solve() |> IO.puts() end defmodule Heap do defstruct data: nil, comparator: nil def new(comparator), do: %__MODULE__{comparator: comparator} def empty?(%__MODULE__{data: nil}), do: true def empty?(%__MODULE__{}), do: false def top(%__MODULE__{data: nil}), do: nil def top(%__MODULE__{data: {_size, value, _left, _right}}), do: value def pop(%__MODULE__{data: data, comparator: comp} = heap) do %{ heap | data: do_pop(comp, data)} end defp do_pop(_comparator, nil), do: nil defp do_pop(comparator, {size, _v0, left, right}) do with nil <- swap_on_pop(comparator, left, right) do nil else {v1, left, right} -> {size - 1, v1, do_pop(comparator, left), right} end end defp swap_on_pop(comparator, left, right) defp swap_on_pop(_comparator, nil, nil), do: nil defp swap_on_pop(_comparator, left, nil), do: {elem(left, 1), left, nil} defp swap_on_pop(_comparator, nil, right), do: {elem(right, 1), right, nil} defp swap_on_pop(comparator, left, right), do: if comparator.(elem(left, 1), elem(right, 1)), do: {elem(left, 1), left, right}, else: {elem(right,1), right, left} def push(%__MODULE__{data: data, comparator: comp} = heap, value) do %{heap | data: do_push(value, comp, data)} end defp do_push(value, comparator, data \\ nil) defp do_push(v0, _comparator, nil), do: {1, v0, nil, nil} defp do_push(v0, comparator, {size, v1, nil, nil}) do {v0, v1} = swap_on_push(v0, v1, comparator) {size + 1, v0, do_push(v1, comparator), nil} end defp do_push(v0, comparator, {size, v1, left, nil}) do {v0, v1} = swap_on_push(v0, v1, comparator) {size + 1, v0, left, do_push(v1, comparator)} end defp do_push(v0, comparator, {size, v1, nil, right}) do {v0, v1} = swap_on_push(v0, v1, comparator) {size + 1, v0, do_push(v1, comparator), right} end defp do_push(v0, comparator, {size, v1, {ls, _, _, _} = left, {rs, _, _, _} = right}) do {v0, v1} = swap_on_push(v0, v1, comparator) if rs < ls do {size + 1, v0, left, do_push(v1, comparator, right)} else {size + 1, v0, do_push(v1, comparator, left), right} end end defp swap_on_push(v0, v1, comparator) do if comparator.(v0, v1), do: {v0, v1}, else: {v1, v0} end defimpl Collectable do def into(heap) do { heap, fn heap, {:cont, v} -> Heap.push(heap, v) heap, :done -> heap _heap, :halt -> :ok end } end end defimpl Enumerable do def count(heap), do: {:ok, Heap.size(heap)} def member?(_, _), do: {:error, __MODULE__} def slice(_), do: {:error, __MODULE__} def reduce(_heap, {:halt, acc}, _fun), do: {:halted, acc} def reduce(heap, {:suspend, acc}, fun), do: {:suspended, acc, &reduce(heap, &1, fun)} def reduce(%Heap{data: nil}, {:cont, acc}, _fun), do: {:done, acc} def reduce(heap, {:cont, acc}, fun) do reduce(Heap.pop(heap), fun.(Heap.top(heap), acc), fun) end end end def solve(n) do {sets, seen} = greedy({1, 1}, n) sets |> Enum.into( Heap.new( fn {s0, p0}, {s1, p1} -> s0 < s1 || (s0 == s1 && p0 > p1) end ) ) |> do_solve(n, seen) end defp greedy(seed, n, seen \\ %{}) do fn {s0, p0}, {s1, p1} -> s0 > s1 || (s0 == s1 && p0 > p1) end |> Heap.new() |> Heap.push(seed) |> do_greedy(n, seen) end defp do_greedy(heap, n, seen) do with set <- Heap.top(heap), [] <- next(set, n, seen) do {Enum.to_list(heap), seen} else arr when is_list(arr) -> {step, position} = Heap.top(heap) arr |> Enum.into(Heap.pop(heap)) |> do_greedy(n, Map.put(seen, position, step)) end end def do_solve(heap, n, seen \\ %{}) do with false <- Heap.empty?(heap), {step, position} when position == n <- Heap.top(heap) do step else true -> -1 {step, position} = set -> with [seed] <- next(set, n, seen) do {sets, seen} = greedy(seed, n, Map.put(seen, position, step)) sets |> Enum.into(Heap.pop(heap)) |> do_solve(n, seen) else sets -> sets |> Enum.into(Heap.pop(heap)) |> do_solve(n, Map.put(seen, position, step)) end end end defp next({_s, p}, n, _seen) when n <= p, do: [] defp next({s, p}, n, seen) do p |> to_displacement() |> (fn d -> [{s + 1, p - d}, {s + 1, p + d}] |> Enum.filter(fn {step, position} when 1 < position and position <= n -> is_nil(seen[position]) || step < seen[position] _ -> false end) end).() end defp to_displacement(n), do: n |> Integer.digits(2) |> Enum.sum() end