[AtCoder] ABC044 - 複数キーの ETS [Elixir Livebook]

## はじめに

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

https://atcoder.jp/contests/abc044/

## ABC044A - 高橋君とホテルイージー

### ABC044A 問題

https://atcoder.jp/contests/abc044/tasks/abc044_a

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc044/abc044_a

### ABC044A 入出力例

```elixir
"""
5
3
10000
9000
"""
|> Main.solve()
|> then(&(&1 == 48000))
```

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

### ABC044A 回答

単純に問題文のままを実装しました

```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
    [n, k, x, y] =
      input
      |> split_lines()
      |> Enum.map(&String.to_integer/1)

    cond do
      n <= k -> n * x
      true -> k * x + (n - k) * y
    end
  end
end
```

実行時間は 341 ms でした

## ABC044B - 美しい文字列

### ABC044B 問題

https://atcoder.jp/contests/abc044/tasks/abc044_b

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc044/abc044_b

### ABC044B 入出力例

```elixir
"""
abaccaba
"""
|> Main.solve()
|> then(&(&1 == "Yes"))
```

```elixir
"""
hthth
"""
|> Main.solve()
|> then(&(&1 == "No"))
```

### ABC044B 回答

`String.codepoints` で文字の配列にして、 `Enum.group_by` で文字毎にグループ分けしました

一つでも文字毎の数が奇数であれば（ `Enum.find`　の結果が nil でなければ） "No"

全ての文字毎の数が偶数であれば "Yes" を表示します

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

  def solve(input) do
    input
    |> String.trim()
    |> String.codepoints()
    |> Enum.group_by(& &1)
    |> Enum.find(fn {_, value} -> value |> length() |> rem(2) == 1 end)
    |> case do
      nil -> "Yes"
      _ -> "No"
    end
  end
end
```

実行時間は 511 ms でした

## ABC044C - 高橋君とカード

### ABC044C 問題

https://atcoder.jp/contests/abc044/tasks/arc060_a

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc044/abc044_c

### ABC044C 入出力例

```elixir
"""
4 8
7 9 8 9
"""
|> Main.solve()
|> then(&(&1 == 5))
```

```elixir
"""
3 8
6 6 9
"""
|> Main.solve()
|> then(&(&1 == 0))
```

```elixir
"""
8 5
3 6 2 8 7 6 5 9
"""
|> Main.solve()
|> then(&(&1 == 19))
```

```elixir
"""
33 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
"""
|> Main.solve()
|> then(&(&1 == 8_589_934_591))
```

### ABC044C 回答

今回は C 問題から躓きました

以下の記事を参考に、というかそのまま Elixir に翻訳したくらいの形でクリアしました

https://drken1215.hatenablog.com/entry/2020/04/24/025200

```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], x] =
      input
      |> split_lines()
      |> Enum.map(fn line ->
        line
        |> split_words()
        |> Enum.map(&String.to_integer/1)
      end)

    x
    |> Enum.with_index()
    |> Enum.map(fn {char, index} -> {index, char} end)
    |> renew_table(:x)

    renew_table({{0, 0, 0}, 1}, :dp)

    for i <- 0..(n - 1),
        k <- 0..n,
        s <- 0..(n * a - 1),
        p = lookup(:dp, {i, k, s}),
        p > 0 do
      x_i = lookup(:x, i)
      p_1_key = {i + 1, k, s}
      p_2_key = {i + 1, k + 1, s + x_i}
      p_1 = lookup(:dp, p_1_key)
      p_2 = lookup(:dp, p_2_key)

      :ets.insert(:dp, {p_1_key, p_1 + p})
      :ets.insert(:dp, {p_2_key, p_2 + p})
    end

    1..n
    |> Enum.reduce(0, fn k, acc ->
      acc + lookup(:dp, {n, k, a * k})
    end)
  end
end
```

先頭から i 個目までの数字から k 個の数字を選んだとき、合計が s になる組み合わせの数、を ETS  に `:dp` テーブルで入れていきます

i, k, s という３つのキーを使うため、 ETS のキーは `{i, k, s}` のタプルにしました

上記の説明が非常に分かりにくい（私自身もなかなか理解できなかった）で、入出力例1の実行後の `:dp` テーブルの中身を見てみます

```elixir
:dp
|> :ets.tab2list()
|> Enum.sort_by(&(&1 |> elem(0)))
```

入力が `7 9 8 9` のとき、 `:dp` テーブルの中身は以下のようになります

```elixir
[
  {{0, 0, 0}, 1},
  {{1, 0, 0}, 1},
  {{1, 1, 7}, 1},
  {{2, 0, 0}, 1},
  {{2, 1, 7}, 1},
  {{2, 1, 9}, 1},
  {{2, 2, 16}, 1},
  {{3, 0, 0}, 1},
  {{3, 1, 7}, 1},
  {{3, 1, 8}, 1},
  {{3, 1, 9}, 1},
  {{3, 2, 15}, 1},
  {{3, 2, 16}, 1},
  {{3, 2, 17}, 1},
  {{3, 3, 24}, 1},
  {{4, 0, 0}, 1},
  {{4, 1, 7}, 1},
  {{4, 1, 8}, 1},
  {{4, 1, 9}, 2},
  {{4, 2, 15}, 1},
  {{4, 2, 16}, 2},
  {{4, 2, 17}, 2},
  {{4, 2, 18}, 1},
  {{4, 3, 24}, 2},
  {{4, 3, 25}, 1},
  {{4, 3, 26}, 1},
  {{4, 4, 33}, 1}
]
```

- 数字が 0 個のとき、合計は 0 になる組み合わせが 1 個です

- 数字が 1 個（7だけ）のとき

  - 0 個の数字を選んだ場合、合計は 0 になる組み合わせが 1 個です
  - 1 個の数字を選んだ場合、合計は 7 になる組み合わせが 1 個です

- 数字が 2 個（7と9）のとき

  - 0 個の数字を選んだ場合、合計は 0 になる組み合わせが 1 個です
  - 1 個の数字を選んだ場合
  　　- 合計が 7 になる組み合わせが 1 個です
  　　- 合計が 9 になる組み合わせが 1 個です
  - 2 個の数字を選んだ場合、合計は 16 (7+9) になる組み合わせが 1 個です

- 数字が 3 個（7と9と8）のとき

  - 0 個の数字を選んだ場合、合計は 0 になる組み合わせが 1 個です
  - 1 個の数字を選んだ場合
  　　- 合計が 7 になる組み合わせが 1 個です
  　　- 合計が 9 になる組み合わせが 1 個です
  　　- 合計が 8 になる組み合わせが 1 個です
  - 2 個の数字を選んだ場合
    - 合計が 15 (7+8) になる組み合わせが 1 個です
    - 合計が 16 (7+9) になる組み合わせが 1 個です
    - 合計が 17 (8+9) になる組み合わせが 1 個です
  - 3 個の数字を選んだ場合、合計は 24 (7+8+9) になる組み合わせが 1 個です

...

というように、全部の組み合わせの数が `:dp`テーブルに入ります

あとは平均が a なので、 k この場合、合計が a * k と等しい組み合わせの数を合計すれば答えが出ます

実行結果は 1755 ms でした

## ABC044D - 桁和

正直、この問題に関しては完全には理解できていません

以下の方の Python 実装を Elixir 　に翻訳しただけですね、、、

https://atcoder.jp/contests/abc044/submissions/40594074

### ABC044D 問題

https://atcoder.jp/contests/abc044/tasks/arc060_b

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc044/abc044_d

### ABC044D 入出力例

```elixir
"""
87654
30
"""
|> Main.solve()
|> then(&(&1 == 10))
```

```elixir
"""
87654
138
"""
|> Main.solve()
|> then(&(&1 == 100))
```

```elixir
"""
87654
45678
"""
|> Main.solve()
|> then(&(&1 == -1))
```

```elixir
"""
31415926535
1
"""
|> Main.solve()
|> then(&(&1 == 31_415_926_535))
```

```elixir
"""
1
31415926535
"""
|> Main.solve()
|> then(&(&1 == -1))
```

### ABC044D 回答

```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 digsum(b, n) when n < b, do: n

  defp digsum(b, n), do: rem(n, b) + digsum(b, div(n, b))

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

    cond do
      n == s ->
        n + 1

      n < s ->
        -1

      true ->
        {small, big} =
          for i <- 1..(:math.sqrt(n - s) |> ceil() |> Kernel.+(1)),
              rem(n - s, i) == 0 do
            {i, div(n - s, i)}
          end
          |> Enum.reduce({[], []}, fn {small_i, big_i}, {small_acc, big_acc} ->
            {[small_i | small_acc], [big_i | big_acc]}
          end)

        [Enum.reverse(small), big]
        |> List.flatten()
        |> Enum.find(-2, &(digsum(&1 + 1, n) == s))
        |> Kernel.+(1)
    end
  end
end
```

唯一工夫した点としては、２つの配列を reduce で作ったところくらいでしょうか

元の Python 実装は以下のようになっていました

```python
    small = []
    big = []
    for i in range(1, math.ceil(math.sqrt(a)) + 1):
        if a % i == 0:
            small.append(i)
            big.append(a // i)
    return small + big[::-1]
```

Elixir だと以下のようになります

```elixir
        {small, big} =
          for i <- 1..(:math.sqrt(n - s) |> ceil() |> Kernel.+(1)),
              rem(n - s, i) == 0 do
            {i, div(n - s, i)}
          end
          |> Enum.reduce({[], []}, fn {small_i, big_i}, {small_acc, big_acc} ->
            {[small_i | small_acc], [big_i | big_acc]}
          end)

        [Enum.reverse(small), big]
        |> List.flatten()
```

`Enum.reduce` でアキュムレーターを　{[], []} のように配列のタプルにすることで、それぞれに対して追加しています

実行時間は 342 ms でした

## まとめ

かなり難しかったです

`x[i][j][k] = value` みたいなことが ETS で　`{{i, j, k}, value}` として実装できたのは良かったです