[AtCoder] ABC134A-D - :ets.tab2list で ETS をリストに変換 [Elixir Livebook]

## はじめに

AtCoder の Beginners Selection コンテスト ABC134 問題を Elixir Livebook で回答しました

https://atcoder.jp/contests/abc134/

なお、 E、F 問題はまだ自分には難しすぎるため、 D 問題までを解いています

## ABC134A - Dodecagon

### ABC134A 問題

https://atcoder.jp/contests/abc134/tasks/abc134_a

### ABC134A 実装したノートブック

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc134/abc134_a

### ABC134A 入出力例

```elixir
"""
4
"""
|> Main.solve()
|> then(&(&1 == 48))
```

```elixir
"""
15
"""
|> Main.solve()
|> then(&(&1 == 675))
```

```elixir
"""
80
"""
|> Main.solve()
|> then(&(&1 == 19200))
```

### ABC134A 回答

問題文の通り、半径 r の円に内接する正十二角形の面積 $3r^2$ を計算します

```elixir
defmodule Main do
  def main do
    :stdio
    |> IO.read(:all)
    |> solve()
    |> IO.puts()
  end

  def solve(input) do
    r =
      input
      |> String.trim()
      |> String.to_integer()

    3 * r * r
  end
end
```

実行時間は 378 ms でした

## ABC134B - Golden Apple

### ABC134B 問題

https://atcoder.jp/contests/abc134/tasks/abc134_b

### ABC134B 実装したノートブック

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc134/abc134_b

### ABC134B 入出力例

```elixir
"""
6 2
"""
|> Main.solve()
|> then(&(&1 == 2))
```

```elixir
"""
14 3
"""
|> Main.solve()
|> then(&(&1 == 2))
```

```elixir
"""
20 4
"""
|> Main.solve()
|> then(&(&1 == 3))
```

### ABC134B 回答

1人の監視員が監視できる木の本数は 2d + 1 本です

従って、 n 本の木を監視するために必要な人数は $\frac{n}{2d + 1}$ の切り上げになります

```elixir
defmodule Main do
  def main do
    :stdio
    |> IO.read(:all)
    |> solve()
    |> IO.puts()
  end

  defp split_words(words) do
    String.split(words, " ")
  end

  def solve(input) do
    [n, d] =
      input
      |> String.trim()
      |> split_words()
      |> Enum.map(&String.to_integer/1)

    ceil(n / (d * 2 + 1))
  end
end
```

実行時間は 359 ms でした

## ABC134C - Exception Handling

### ABC134C 問題

https://atcoder.jp/contests/abc134/tasks/abc134_c

### ABC134C 実装したノートブック

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc134/abc134_c

### ABC134C 入出力例

```elixir
"""
3
1
4
3
"""
|> Main.solve()
|> then(&(&1 == ~S(4
3
4)))
```

```elixir
"""
2
5
5
"""
|> Main.solve()
|> then(&(&1 == ~S(5
5)))
```

### ABC134C 回答

a の i 番目を除いたときの各最大値を出力します

もし最大値になる $a_i$ が複数存在していれば、どの $a_i$ を除いても最大値は変わりません

そうでない場合、最大値と等しい $a_i$ を除いたときだけ2番目に大きい値が最大値になり、それ以外は全体の最大値と同じになります

```elixir
defmodule Main do
  def main do
    :stdio
    |> IO.read(:all)
    |> solve()
    |> IO.puts()
  end

  defp split_lines(lines) do
    lines
    |> String.trim()
    |> String.split("\n")
  end

  def solve(input) do
    [_ | a] =
      input
      |> String.trim()
      |> split_lines()
      |> Enum.map(&String.to_integer/1)

    a_max = Enum.max(a)

    if Enum.count(a, &(&1 == a_max)) > 1 do
      List.duplicate(a_max, Enum.count(a))
    else
      a
      |> Enum.map(fn a_i ->
        if a_i == a_max do
          a
          |> Enum.sort()
          |> Enum.at(-2)
        else
          a_max
        end
      end)
    end
    |> Enum.join("\n")
  end
end
```

実行時間は 1103 ms でした

## ABC134D - Preparing Boxes

### ABC134D 問題

https://atcoder.jp/contests/abc134/tasks/abc134_d

### ABC134D 実装したノートブック

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc134/abc134_d

### ABC134D 入出力例

```elixir
"""
3
1 0 0
"""
|> Main.solve()
|> then(&(&1 == ~s"1
1"))
```

```elixir
"""
5
0 0 0 0 0
"""
|> Main.solve()
|> then(&(&1 == ~s"0
"))
```

### ABC134D 回答

正直、これは問題文を理解することから困難でした

以下の記事を参考に ELixir で実装しましたが、ほぼ自力では解決不可能でした

https://blog.hamayanhamayan.com/entry/2019/07/20/233440

```elixir
defmodule Main do
  def main do
    :stdio
    |> IO.read(:all)
    |> solve()
    |> IO.puts()
  end

  defp split_lines(lines) do
    lines
    |> String.trim()
    |> String.split("\n")
  end

  defp split_words(words) do
    String.split(words, " ")
  end

  defp renew_table(objects, table_name) do
    if :ets.info(table_name) != :undefined do
      :ets.delete(table_name)
    end

    :ets.new(table_name, [:set, :protected, :named_table])
    :ets.insert(table_name, objects)
  end

  defp lookup(table_name, key) do
    case :ets.lookup(table_name, key) do
      [{_, value}] -> value
      _ -> 0
    end
  end

  def solve(input) do
    [[n], a] =
      input
      |> split_lines()
      |> Enum.map(fn line ->
        line
        |> split_words()
        |> Enum.map(&String.to_integer/1)
      end)

    a
    |> Enum.with_index()
    |> Enum.map(fn {a_i, i} -> {i + 1, a_i} end)
    |> renew_table(:a)

    renew_table([], :b)

    n..1
    |> Enum.each(fn i ->
      other =
        2..div(n, i)
        |> Enum.count(fn j -> lookup(:b, i * j) == 1 end)

      if rem(other, 2) != lookup(:a, i) do
        :ets.insert(:b, {i, 1})
      end
    end)

    ans =
      :b
      |> :ets.tab2list()
      |> Enum.filter(fn {_, b_i} -> b_i == 1 end)
      |> Enum.map(&elem(&1, 0))

    ~s"#{length(ans)}\n#{Enum.join(ans, " ")}"
  end
end
```

i の倍数に対して計算するため、参考にした記事では以下のようにループしています

```c++
int other = 0;
for (int x = i * 2; x <= N; x += i) if (B[x]) other++;
```

しかし、  `Range.new/3` は Elixir 1.12 から追加されたものなので、 Elixir 1.10 環境では i ずつ増やす、というようなステップを指定できません

:::note info
AtCoder が Elixir 1.15.2 に対応するようです

https://atcoder.jp/contests/language-test-202301
:::

そのため、以下のようにループ内で倍数にしています

```elixir
other =
  2..div(n, i)
  |> Enum.count(fn j -> lookup(:b, i * j) == 1 end)
```

1.12 以降であれば以下のように表現可能です

```elixir
other =
  (i * 2)..n//i
  |> Enum.count(fn j -> lookup(:b, j) == 1 end)
```

b に対しては倍数で参照する特性上、 ETS を使って高速にアクセスしています

ただし、最後には b の値を並べて出力しなければならないため、 `:ets.tab2list` で List に変換しています

実行時間は 1094 ms でした

## まとめ

ETS の扱いには十分慣れました

最新のコンテストにもそろそろ挑戦してみようかな、、

早く最新版の Elixir で解きたいです

Nx も使えるようになれば、かなり解法が変わってきますが、、、