search
LoginSignup
1

posted at

updated at

ABC245のA, B, C, D問題 を Elixir で解く

これに続いて、Elixir 超初心者が AtCoder に挑戦してみました。

御指導よろしくお願いします。

A問題: Good morning

defmodule Main do
  def main do
    IO.read(:line) |> integer_list()
    |> solve()
    |> IO.puts()
  end
  
  defp integer_list(str) do
    str
    |> String.trim()
    |> String.split(" ")
    |> Enum.map(&String.to_integer/1)
  end
  
  defp solve([a, b, c, d]) do
    if f(a, b, 0) < f(c, d, 1), do: "Takahashi", else: "Aoki"
  end
  
  def f(h, m, s), do: 3600 * h + 60 * m + s
end

関数fで日付の変わった時点からの秒数を求めています。

B問題: Mex

defmodule Main do
  def main do
    IO.read(:line)
    
    IO.read(:line) |> integer_list()
    |> solve()
    |> IO.puts()
  end
  
  defp integer_list(str) do
    str
    |> String.trim()
    |> String.split(" ")
    |> Enum.map(&String.to_integer/1)
  end
  
  defp solve(list) do
    list
    |> Enum.reduce(%{}, &Map.put(&2, &1, true))
    |> find()
  end
  
  defp find(map), do: 0..2000 |> Enum.find(&!map[&1])
end 

Elixir ではリストのランダムアクセスができないので、代わりにマップでやっています。

C問題: Choose Elements

defmodule Main do
  def main do
    nk = IO.read(:line) |> integer_list()
    as = IO.read(:line) |> integer_list()
    bs = IO.read(:line) |> integer_list()
    
    solve(nk, as, bs) |> IO.puts()
  end
  
  defp integer_list(str) do
    str
    |> String.trim()
    |> String.split(" ")
    |> Enum.map(&String.to_integer/1)
  end
  
  defp solve([1, _], _, _), do: "Yes"
  
  defp solve([n, k], [ai | as], [bi | bs]) do
    1..n - 1
    |> Enum.reduce({true, true, ai, bi, as, bs, k}, &judge/2)
    |> output()
  end
  
  def judge(_, {x, y, a0, b0, [a | as], [b | bs], k}) do
    x1 = judge(x, a, a0, k)
    x2 = judge(y, a, b0, k)
    y1 = judge(x, b, a0, k)
    y2 = judge(y, b, b0, k)
    {x1 || x2, y1 || y2, a, b, as, bs, k}
  end
  
  defp judge(f, n, n0, k), do: f && abs(n - n0) <= k
  
  defp output({x, y, _, _, _, _, _}) do
    if x || y, do: "Yes", else: "No"
  end
end

動的計画法なので、Enum.reduce/3を使っています。正直いって、Ruby で解いた下敷きがないとキツかったです。

D問題: Polynomial division

defmodule Main do
  def main do
    IO.read(:line)
    as = IO.read(:line) |> rev_integer_list()
    cs = IO.read(:line) |> rev_integer_list()
    
    solve(as, cs) |> IO.puts()
  end
  
  defp rev_integer_list(str) do
    str
    |> String.trim()
    |> String.split(" ")
    |> Enum.map(&String.to_integer/1)
    |> Enum.reverse()
  end
  
  defp solve(as, cs) do
    al = Enum.count(as)
    cl = Enum.count(cs)
    rem = Enum.take(cs, al)
    cs1 = Enum.drop(cs, al)
    
    1..cl - al + 1
    |> Enum.reduce({[], rem, cs1, as}, &division/2)
    |> output()
  end
  
  defp division(_, {acc, rem, cs, as}) do
    quo = div(hd(rem), hd(as))
    rem1 = Enum.zip(rem, as) |> Enum.map(fn {x, a} -> x - a * quo end)
    [c | cs1] = if Enum.empty?(cs), do: [nil], else: cs
    rem1 = (tl rem1) ++ [c]
    {[quo | acc], rem1, cs1, as}
  end
  
  defp output({result, _, _, _}), do: result |> Enum.join(" ")
end

多項式の割り算をやっているだけなのですが、これもキツかった。Elixir では[x | xs] = []のパターンマッチがエラーになってしまうんですよね。なのでcaseを使ってみたのですが、うまい書き方がありますかねえ。(追記。if ~ elseで書き直しました。)

最後に

reduceaccに何もかも放り込んでしまって、困ったものです。むずかしい。index が使いたくて悶えます笑。
Rubyist なので、あらかじめ Ruby で関数型的に書いて Elixir に置き直しているのです。まだいきなり Elixir では書けませんね。Ruby はもちろん関数型言語ではないですが、関数型っぽく書くのも簡単です。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
1