[AtCoder] ABC042 - Elixir による二項係数（組み合わせ数）の高速計算 [Elixir Livebook]

## はじめに

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

https://atcoder.jp/contests/abc042/

他の人の（他の言語の）実装を参考にしながらですが、初めて D 問題を解きました

その中で組み合わせ数の高速計算が必要になったので、 Elixir で実装しています

## ABC042A - 和風いろはちゃんイージー

### ABC042A 問題

https://atcoder.jp/contests/abc042/tasks/abc042_a

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc042/abc042_a

### ABC042A 入出力例

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

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

### ABC042A 回答1

入力を小さいい順に並べ替えて 5 5 7 になれば YES を出力します

```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
    input
    |> String.trim()
    |> split_words()
    |> Enum.sort()
    |> case do
      ["5", "5", "7"] -> "YES"
      _ -> "NO"
    end
  end
end
```

実行結果は 327 ms でした

### ABC042A 回答2

5 が２つ、 7 が1つのパターンを網羅しました

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

  def solve(input) do
    input
    |> String.trim()
    |> case do
      "5 5 7" -> "YES"
      "5 7 5" -> "YES"
      "7 5 5" -> "YES"
      _ -> "NO"
    end
  end
end
```

実行結果は 333 ms でした

## ABC042B - 文字列大好きいろはちゃんイージー

### ABC042B 問題

https://atcoder.jp/contests/abc042/tasks/abc042_b

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc042/abc042_b

### ABC042B 入出力例

```elixir
"""
3 3
dxx
axx
cxx
"""
|> Main.solve()
|> then(&(&1 == "axxcxxdxx"))
```

### ABC042B 回答

先頭行以外を小さい順に並べ替えて結合します

```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
    input
    |> split_lines()
    |> tl()
    |> Enum.sort()
    |> Enum.join()
  end
end
```

実行結果は 343 ms でした

## ABC042C - こだわり者いろはちゃん

### ABC042C 問題

https://atcoder.jp/contests/abc042/tasks/arc058_a

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc042/abc042_c

### ABC042C 入出力例

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

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

### ABC042C 回答1

支払い金額の候補（代金〜9,999円）のうち、全ての桁が嫌いな数字ではない値を探します

`Enum.find` で最初に該当するもの = 最小値が求められます

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

    n..99999
    |> Enum.find(fn payment ->
      all_digits =
        payment
        |> Integer.digits()
        |> Enum.uniq()
        |> Enum.concat(d)

      all_digits
      |> Enum.uniq()
      |> Enum.count()
      |> Kernel.==(Enum.count(all_digits))
    end)
  end
end
```

実行結果は 445 ms でした

### ABC042C 回答2

まず、嫌いな数字ではない数字 = 支払い金額に含んで良い数字 `pay_d` を求めます

0 が嫌いな数字だったとしても、 10 の位以上は 0 があり得るため、 0 も含む `pay_d_up` を求めます

1の位が `pay_d` 、10の位以上が `pay_d_up` の組み合わせでできる数字のうち、代金以上の数字を求めます

0 が嫌いな数字だった場合、改めて支払い金額に 0 が含まれていれば候補から除外します

該当する支払い金額のうち、最小の値を取得します

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

    pay_d = Enum.filter(0..9, &(not Enum.member?(d, &1)))
    pay_d_up = Enum.uniq([0 | pay_d])

    for d_1 <- pay_d,
        d_10 <- pay_d_up,
        d_100 <- pay_d_up,
        d_1000 <- pay_d_up,
        d_10000 <- pay_d_up,
        payment = Integer.undigits([d_10000, d_1000, d_100, d_10, d_1]),
        payment >= n do
      payment
    end
    |> Enum.filter(fn payment ->
      if Enum.member?(d, 0) do
        payment |> Integer.digits() |> Enum.member?(0) |> Kernel.not()
      else
        true
      end
    end)
    |> Enum.min()
  end
end
```

発想はシンプルですが、 0 の扱いのため複雑になってしまいました

実行結果は 386 ms でした

## ABC042D - いろはちゃんとマス目

### ABC042D 問題

https://atcoder.jp/contests/abc042/tasks/arc058_b

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc042/abc042_d

### ABC042D 入出力例

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

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

```elixir
"""
100000 100000 99999 99999
"""
|> Main.solve()
|> then(&(&1 == 1))
```

```elixir
"""
100000 100000 44444 55555
"""
|> Main.solve()
|> then(&(&1 == 738_162_020))
```

### ABC042D 回答

自力では解けなかったので、以下の記事を参考に回答しました

https://drken1215.hatenablog.com/entry/2020/04/06/235844

https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a

W * H の格子を左上から右下に移動する場合、移動する回数は以下のようになります

- 横方向の移動回数: W - 1
- 縦方向の移動回数: H - 1
- 合計: W - 1 + H - 1 = W + H - 2

全ての移動のうち、どのタイミングで縦方向（下）に移動するか、によって移動経路が変わります

従って、移動経路の数 =　全移動回 W + H - 2 から縦方向の移動回数 H - 1 を選択する組み合わせの数

$　{}_{(W+H-2)} \mathrm{C} _{(H-1)}　$

になります

特定の範囲を通らない場合については[参考記事](https://drken1215.hatenablog.com/entry/2020/04/06/235844)に解説してある通りです

ここからが大変でした

値の取りうる範囲が 1　≦　H,　W　≦　100,000 と大きいため、普通に以下の公式を使って計算すると、オーバーフローしたり、メモリがパンクしたり、計算時間が膨大になったりします

${}_n \mathrm{C}_r = \frac{n!}{r!(n-r)!}$

そこで、問題文にある以下の条件を使います

> なお、答えは非常に大きくなることがあるので、答えは 10^9+7 で割ったあまりを出力してください。

もう一つの[参考記事](https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a)から、逆元による組み合わせ数の計算を実装します

また、計算結果に高速アクセスするため、 @zacky1972 さんにオススメ頂いた ETS を使います

https://elixirschool.com/ja/lessons/storage/ets

Livebook で試行錯誤するため、テーブルが既にある場合は削除するようにしています

組み合わせ数計算は他でも使えそうなので、 Combination モジュールとして Main とは別に定義しておき、 `Combination.init` で必要な全ての階乗、逆元を計算しておき、 `Combination.combination` で以下の計算を実行します

${}_n \mathrm{C}_r = n! * r!^{-1} * ((n-r)!)^{-1}$

```elixir
defmodule Combination do
  @mod 1000000007
  @max_index 200000

  defp renew_table(table_name, initial_objects) 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, initial_objects)
  end

  defp lookup(table_name, key) do
    [{_, value}] = :ets.lookup(table_name, key)
    value
  end

  def init do
    renew_table(:factorial, [{0, 1}, {1, 1}])
    renew_table(:inverse, [{1, 1}])
    renew_table(:factorial_inverse, [{0, 1}, {1, 1}])

    2..@max_index
    |> Enum.reduce(1, fn index, acc ->
      factorial = rem(acc * index, @mod)

      mod_inverse = lookup(:inverse, rem(@mod, index))
      inverse = @mod - rem(mod_inverse * div(@mod, index), @mod)

      pre_factorial_inverse = lookup(:factorial_inverse, index - 1)  
      factorial_inverse = rem(pre_factorial_inverse * inverse, @mod)

      :ets.insert(:factorial, {index, factorial})
      :ets.insert(:inverse, {index, inverse})
      :ets.insert(:factorial_inverse, {index, factorial_inverse})

      factorial
    end)
  end

  def combination(n, r) do
    factorial_n = lookup(:factorial, n)
    factorial_inverse_nr = lookup(:factorial_inverse, n - r)
    factorial_inverse_r = lookup(:factorial_inverse, r)

    (factorial_inverse_nr * factorial_inverse_r)
    |> rem(@mod)
    |> Kernel.*(factorial_n)
    |> rem(@mod)
  end
end

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

    Combination.init()

    0..(h - a - 1)
    |> Enum.reduce(0, fn h_i, acc ->
      l = Combination.combination(h_i + b - 1, h_i)
      r = Combination.combination(h + w - h_i - b - 2, h - 1 - h_i)
      acc + l * r
    end)
    |> rem(1_000_000_007)
  end
end
```

逆元による組み合わせ数の計算と、 ETS の利用によって制限時間をクリアできました

実行結果は 908 ms でした