ElixirでABC178のA,B,C問題を制する！(べき乗の計算に課題あり😥)

Elixir 1.13 or laterでは ** が追加されています！

**/2については、下記の記事を書いています。

はじめに

• @u2dayo さんの【AtCoder解説】PythonでABC178のA,B,C問題を制する！を拝見しまして、私はElixirでやってみようとおもいました

問題

• AtCoder Beginner Contest 178
• A〜Cまで解いてみます

問題A - Not

• 問題文はリンク先をご参照くださいませ
• 自力で行けました

defmodule Main do
  def main do
    IO.read(:line)
    |> String.trim()
    |> solve()
    |> IO.puts()
  end

  defp solve("1"), do: "0"

  defp solve("0"), do: "1"
end

• 提出

問題B - Product Max

• 問題文はリンク先をご参照くださいませ
• 自力で行けました

defmodule Main do
  def main do
    IO.read(:line)
    |> String.trim()
    |> String.split(" ")
    |> Enum.map(&String.to_integer/1)
    |> solve()
    |> IO.puts()
  end

  defp solve([a, b, c, d]), do: Enum.max([a * c, a * d, b * c, b * d])
end

• 提出

問題C - Ubiquity

• 解き方は、元の記事のベン図で理解しました
  • ありがとうございます！
  • $10^N - 2 × 9^N + 8^N$ を計算すればよいわけです
• べき乗計算ですね、イヤな予感がしてきました
• Elixirには**演算子がありません
• Erlangの:math.pow/2が使えますが、結果がfloatですし、roundで整数にしても誤差がでてしまうし、計算できる上限があります

iex> :math.pow(2, 3)
8.0

iex> :math.pow(10, 100) |> round
10000000000000000159028911097599180468360808563945281389781327557747838772170381060813469985856815104

iex> :math.pow(10, 1000000)
** (ArithmeticError) bad argument in arithmetic expression
    (stdlib 3.13) :math.pow(10, 1000000)

• How do I raise a number to a power in Elixir? で紹介されていた、べき乗計算を末尾再帰で行う解法¹で提出してみました
• が、しかしTLE (Time Limit Exceeded)で不合格となっています😥
  • 元の記事にありました「余りを取りながら計算すると高速に計算できます」もやってみたのですが、その工夫の効果よりもべき乗の計算に時間がかかってしまっているようで不合格のままでした

defmodule Main do
  @divisor 1_000_000_007

  def main do
    IO.read(:line)
    |> String.trim()
    |> String.to_integer()
    |> solve()
    |> IO.puts()
  end

  def solve(n) do
    pow(10, n)
    |> Kernel.-(2 * pow(9, n))
    |> Kernel.+(pow(8, n))
    |> rem(@divisor)
  end

  def pow(m, n), do: _pow(m, n, 1)

  defp _pow(_, 0, acc), do: acc

  defp _pow(m, n, acc), do: _pow(m, n - 1, m * acc)
end

• 提出

【追記】 AC (Accepted)が１ケース増えました！

• べき乗の高速化(log n) を参考にさせていただいて、pow/2関数を書き直してみましたところAC (Accepted)が１ケース増えました

defmodule Awesome do
  use Bitwise
 
  def pow(m, n) do
    pow(m, n, 1)
  end

  def pow(_m, n, acc) when n <= 0, do: acc

  def pow(m, n, acc) do
    if (n &&& 1) == 1 do
      pow(m * m, n >>> 1, m * acc)
    else
      pow(m * m, n >>> 1, acc)
    end
  end
end

• :timer.tc/3で計測したところ確かに速くなっています

iex> :timer.tc(Awesome, :pow, [10, 100000]) |> elem(0)     
60575

iex> :timer.tc(Main, :pow, [10, 100000]) |> elem(0)
1274525

• 提出
  • まだまだ不合格 TLE (Time Limit Exceeded)が多い

【追記】 @suzuki-navi さんが解いてくださいました！

• ElixirでABC178のC Ubiquityを解いてみる
• 

Ruby

• とりあえず、Elixirの言語仕様に強い影響を与えたと言われていて、Elixirの母だと言われることもあるRubyで提出したところ、あっさり合格しました
  • ありがとう、おっかさん！

n = gets.to_i
 
puts ((10 ** n - 2 * (9 ** n) + (8 ** n)) % 1000000007)

• 提出

Wrapping Up

• Elixirのべき乗計算はどうやると速くできるのでしょうか
  • 自分で分かったら更新したいと思いますし、ご存知の方はぜひ教えてくださいませ
• Enjoy Elixir !!!

1. 私は末尾再帰になっているものだと思っているのですが間違っていたらご指摘ください ↩