[AtCoder] ABC133A-D - Enum.map_reduce で漸化式 [Elixir Livebook]

## はじめに

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

https://atcoder.jp/contests/abc133/

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

## ABC133A - T or T

### ABC133A 問題

https://atcoder.jp/contests/abc133/tasks/abc133_a

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc133/abc133_a

### ABC133A 入出力例

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

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

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

### ABC133A 回答

電車の場合とタクシーの場合で料金を計算し、小さい方を返します

```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, a, b] =
      input
      |> String.trim()
      |> split_words()
      |> Enum.map(&String.to_integer/1)

    Enum.min([n * a, b])
  end
end
```

実行時間は 375 ms でした

## ABC133B - Good Distance

### ABC133B 問題

https://atcoder.jp/contests/abc133/tasks/abc133_b

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc133/abc133_b

### ABC133B 入出力例

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

```elixir
"""
3 4
-3 7 8 2
-12 1 10 2
-2 8 9 3
"""
|> Main.solve()
|> then(&(&1 == 2))
```

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

### ABC133B 回答1

問題文の通り、各点間の距離を計算し、整数（切り上げ `ceil` してもしなくても同じ値）のものをカウントしました

```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

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

    for i <- 0..(n - 2),
        j <- (i + 1)..(n - 1) do
      y = Enum.at(x_list, i)
      z = Enum.at(x_list, j)

      for k <- 0..(d - 1) do
        :math.pow(Enum.at(y, k) - Enum.at(z, k), 2)
      end
      |> Enum.sum()
      |> :math.sqrt()
    end
    |> Enum.count(&(&1 == ceil(&1)))
  end
end
```

実行時間は 338 ms でした

## ABC133C - Remainder Minimization 2019

### ABC133C 問題

https://atcoder.jp/contests/abc133/tasks/abc133_c

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc133/abc133_c

### ABC133C 入出力例

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

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

```elixir
"""
332701087 1753412895
"""
|> Main.solve()
|> then(&(&1 == 0))
```

### ABC133C 回答

まず、 `r - l` が 2019 以上の場合、必ず r と l の間に 2019 の倍数が存在しているので、 i か j のいずれかが 2019 の倍数のとき、 `rem(i * j, 2019)` は必ず 0 になります

それ以外の場合、 l と r が大きい数字だと計算が大変なので、どちらも 2019 で割った余りにしておきます

その範囲内で `rem(i * j, 2019)` を計算し、最小値を返します

```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
    [l, r] =
      input
      |> String.trim()
      |> split_words()
      |> Enum.map(&String.to_integer/1)

    if r - l >= 2019 do
      0
    else
      [nl, nr] =
        [l, r]
        |> Enum.map(&rem(&1, 2019))
        |> Enum.sort()

      for i <- nl..(nr - 1),
          j <- (i + 1)..nr do
        rem(i * j, 2019)
      end
      |> Enum.min()
    end
  end
end
```

実行結果は 637 ms でした

## ABC133D - Enough Array

### ABC133D 問題

https://atcoder.jp/contests/abc133/tasks/abc133_d

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc133/abc133_d

### ABC133D 入出力例

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

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

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

### ABC133D 回答1

自力では解けなかったので、こちらの記事を参考に Elixir に翻訳しました

https://blog.hamayanhamayan.com/entry/2019/07/08/212938

公式の解説も非常に分かりやすかったです

https://img.atcoder.jp/abc133/editorial.pdf

最初の $x_0$ を求めた後は漸化式で残りの x を求めます

今回のパターンは Elixir でも簡単に表現できるタイプだったので、仕組みさえ理解できれば実装は簡単でした

```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, a_i} end)
    |> renew_table(:a)

    s = Enum.sum(a)

    x_0 =
      0..(n - 1)
      |> Enum.reduce(s, fn i, acc ->
        case rem(i, 2) do
          0 -> acc
          _ -> acc - 2 * lookup(:a, i)
        end
      end)

    renew_table({0, x_0}, :x)

    1..(n - 1)
    |> Enum.each(fn i ->
      :ets.insert(:x, {i, 2 * lookup(:a, i - 1) - lookup(:x, i - 1)})
    end)

    :x
    |> :ets.tab2list()
    |> Enum.sort_by(&elem(&1, 0))
    |> Enum.map(fn {_, x_i} -> Integer.to_string(x_i) end)
    |> Enum.join(" ")
  end
end
```

実行時間は 1008 ms でした

### ABC133D 回答2

よくよく考えたら x は ETS に入れる必要はありませんでした

`Enum.map_reduce` を使うと、もっと単純化できました

```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, a_i} end)
    |> renew_table(:a)

    x_0 =
      0..(n - 1)
      |> Enum.reduce(0, fn i, acc ->
        case rem(i, 2) do
          0 -> acc + lookup(:a, i)
          _ -> acc - lookup(:a, i)
        end
      end)

    x =
      1..(n - 1)
      |> Enum.map_reduce(x_0, fn i, acc ->
        x_i = 2 * lookup(:a, i - 1) - acc
        {x_i, x_i}
      end)
      |> elem(0)

    [x_0 | x]
    |> Enum.map(&Integer.to_string/1)
    |> Enum.join(" ")
  end
end
```

実行時間は 477 ms でした

## まとめ

ETS を使うことに慣れすぎると、不要な時でも使ってしまいそうになるのは悪いですね