結果

問題 No.3 ビットすごろく
ユーザー penqenpenqen
提出日時 2021-03-12 23:32:25
言語 Elixir
(1.16.2)
結果
AC  
実行時間 719 ms / 5,000 ms
コード長 5,091 bytes
コンパイル時間 1,314 ms
コンパイル使用メモリ 64,696 KB
実行使用メモリ 58,348 KB
最終ジャッジ日時 2024-06-10 00:30:35
合計ジャッジ時間 25,374 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 641 ms
54,064 KB
testcase_01 AC 647 ms
54,944 KB
testcase_02 AC 643 ms
53,984 KB
testcase_03 AC 651 ms
54,232 KB
testcase_04 AC 653 ms
55,144 KB
testcase_05 AC 677 ms
55,784 KB
testcase_06 AC 655 ms
54,376 KB
testcase_07 AC 653 ms
54,740 KB
testcase_08 AC 673 ms
55,300 KB
testcase_09 AC 690 ms
57,812 KB
testcase_10 AC 714 ms
57,132 KB
testcase_11 AC 676 ms
56,256 KB
testcase_12 AC 676 ms
56,300 KB
testcase_13 AC 658 ms
54,108 KB
testcase_14 AC 694 ms
57,544 KB
testcase_15 AC 719 ms
57,368 KB
testcase_16 AC 704 ms
57,192 KB
testcase_17 AC 702 ms
57,128 KB
testcase_18 AC 652 ms
54,712 KB
testcase_19 AC 709 ms
57,192 KB
testcase_20 AC 654 ms
54,416 KB
testcase_21 AC 645 ms
54,736 KB
testcase_22 AC 707 ms
58,332 KB
testcase_23 AC 715 ms
57,452 KB
testcase_24 AC 711 ms
58,348 KB
testcase_25 AC 712 ms
57,256 KB
testcase_26 AC 660 ms
54,376 KB
testcase_27 AC 669 ms
54,504 KB
testcase_28 AC 705 ms
57,828 KB
testcase_29 AC 691 ms
57,052 KB
testcase_30 AC 663 ms
55,616 KB
testcase_31 AC 654 ms
54,316 KB
testcase_32 AC 692 ms
56,696 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:
    │
 36 │       do: if comparator.(elem(left, 1), elem(right, 1)),
    │       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    │
    └─ Main.exs:36

ソースコード

diff # 

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
0