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

はじめに

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

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

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

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

ABC042A 問題

ABC042A 実装したノートブック

ABC042A 入出力例

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

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

ABC042A 回答1

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

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つのパターンを網羅しました

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 問題

ABC042B 実装したノートブック

ABC042B 入出力例

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

ABC042B 回答

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

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 問題

ABC042C 実装したノートブック

ABC042C 入出力例

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

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

ABC042C 回答1

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

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

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 が含まれていれば候補から除外します

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

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 問題

ABC042D 実装したノートブック

ABC042D 入出力例

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

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

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

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

ABC042D 回答

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

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)}　$

になります

特定の範囲を通らない場合については参考記事に解説してある通りです

ここからが大変でした

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

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

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

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

もう一つの参考記事から、逆元による組み合わせ数の計算を実装します

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

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

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

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

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 でした