Zenn
😸

AtCoderをElixirでやってみる

2020/10/11に公開
Elixir
AtCoder
tech

はじめに

  • Elixir楽しんでいますか!
  • AtCoderはご存知でしょうか。
    • 世界最高峰の競技プログラミングサイトです
    • だいたい毎週土曜や日曜の21時すぎにコンテストが行われているようです
    • 出題された問題の答えを出力するプログラムを書いて提出することで自動的に採点されます
    • 実行時間が長かったり、メモリの使用量が多いとパスできません
    • 競技プログラミングというもの自体に私は馴染みがなかったのですが、最近はじめました
  • もちろん、Elixirでも参加できます
    • いまのところバージョンは1.10.2です
  • 私はいまのところA問題、B問題は自力で解けて、C問題は解けたり解けなかったりといった程度のレベルですがElixirで解くうえでのノウハウが溜まったような気がするので、Zenn.dev初投稿で書いておきます
    • AtCoderはコンテストごとに難易度が異なっているようでして、私が練習していたAtCoder Beginner Contest(ABC)でのA〜C問題のレベルの話です
  • 前半はElixirを触ったことがあるが、けれどもAtCoderははじめてだよという方を対象に書き進めています
  • 後半にElixirをインストールからだという方向けにも少しだけ情報を載せております
  • ElixirもAtCoderも猛者の方には物足りないとおもいますが、この関数を使ったほうが良いよといった情報がありましたら、ぜひコメントをください
  • 私が言いたいことはひとつです
    • Elixirを楽しみましょう！

提出の形式

  • MainモジュールにMain.main/0関数を作ります
  • Main.main/0から実行されます
  • 入力を読み込んで、答えを計算して、出力をするという形でプログラムを提出をします
defmodule Main do
  def main do
    IO.read(:line)
    ...

    solve()
    |> IO.puts()
  end
  
  def solve(n) do
    ...
  end
end

入力の読み取りあれこれ

1つの整数を読み取る

入力例

1

プログラム例

n = IO.read(:line) |> String.trim() |> String.to_integer()
  • IO.read/2した値には末尾に改行があります
  • String.trim/1を使って改行を取り除きます
  • おなじみのpipe operator(|>)を使って、気持ちよく書けます

スペースで区切られた整数を読み取る(一行)

入力例①

2 3

プログラム例①

[n, m] =
      IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)
  • String.split/3には、第2引数のpatternに" "を指定したほうが速く処理してくれるようです
  • 私の経験上、" "の有り無しでパスしたり不合格となったりする問題がありました

入力例②

5 4 3 2 1 0 7 7 6 6
  • 200,000個以上並んでいることがあります

プログラム例②

list =
      IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)

スペースで区切られた整数を読み取る(複数行)

  • ここまでの組み合わせともいえます
  • list_of_listsの形になります

入力例

3
1 3 3 100
1 2 2 10
2 3 2 10
  • 3行分スペースで区切られた数字のリストが続いている例です

プログラム例

q = IO.read(:line) |> String.trim() |> String.to_integer()
for _ <- 1..q do
  IO.read(:line)
  |> String.trim()
  |> String.split(" ")
  |> Enum.map(&String.to_integer/1)
end
# [[1, 3, 3, 100], [1, 2, 2, 10], [2, 3, 2, 10]]

出力

  • IO.puts/2は1回だけの呼び出しにするとよいです
  • たとえば複数行出力する場合にはEnum.join/2を使って改行で文字列にしてから、IO.puts/2を呼び出すとよいです

NG例

list
|> Enum.each(&IO.puts/1)
  • 解答数が少ないときは上記でも通るときがありますが、200,000行の回答を出力するような場合には間に合わないことがあります

OK例

list
|> Enum.join("\n")
|> IO.puts()

解く

  • 入力、出力の仕方はだいたいわかったのであとは問題を解いていきます
  • A問題は入力をもとになにかに変換するという感じの問題が多いように思います
  • B問題は多少複雑になりますが入力数が200個程度ですので、そこまでパフォーマンスを意識した書き方をしなくても通る場合が多いように思います
    • 割り算は使わず、式を変形して掛け算で大小判定するようなことをしたほうがいい場合があります
  • C問題はある法則のようなものをみつけて、その上で計算量を減らす工夫ができるとパスできるように思います
    • 以下の関数をうまくつかうと解けることが多いような気がします
    • Enum.at/3をあちこちで使うプログラム(Enum.map等ループしている処理の中でさらにEnum.atを使う)を書いてしまうと答えは合っているかもしれませんが制限時間の中で収まらない傾向にあるようにおもいます
      • どうしてもそういう形でしか解けない問題はリストではなく、マップを使うとうまくいったことがあったようななかったようなという感じです
    • 感覚的なものですが前から処理するのではなく、後ろからみていったらどうなるだろうかとか考えるとうまいやり方をおもいつくことがあります
  • D問題以降は私にはまだちょっと早くて何もいえないです
  • 以下、B問題くらいまではなにかしら役に立つことがあるかもしれないので紹介しておきます

combination

  • オートレース、競馬、競輪、競艇の３連複です
  • 順番関係なしに組み合わせるものです
  • Elixirには標準ではない機能です
defmodule Awesome do
  def combination(_, 0), do: [[]]
  def combination([], _), do: []

  def combination([x | xs], n) do
    for(y <- combination(xs, n - 1), do: [x | y]) ++ combination(xs, n)
  end
end

iex> Awesome.combination([1, 2, 3, 4, 5, 6], 3)
[
  [1, 2, 3],
  [1, 2, 4],
  [1, 2, 5],
  [1, 2, 6],
  [1, 3, 4],
  [1, 3, 5],
  [1, 3, 6],
  [1, 4, 5],
  [1, 4, 6],
  [1, 5, 6],
  [2, 3, 4],
  [2, 3, 5],
  [2, 3, 6],
  [2, 4, 5],
  [2, 4, 6],
  [2, 5, 6],
  [3, 4, 5],
  [3, 4, 6],
  [3, 5, 6],
  [4, 5, 6]
]

permutation

  • オートレース、競馬、競輪、競艇の2連単です
  • Elixirには標準ではない機能です
defmodule Awesome do
  def permutation(_, 0), do: [[]]

  def permutation(list, n) do
    for x <- list, rest <- permutation(list -- [x], n - 1), do: [x | rest]
  end
end

iex> Awesome.permutation([1, 2, 3, 4, 5, 6], 2)
[
  [1, 2],
  [1, 3],
  [1, 4],
  [1, 5],
  [1, 6],
  [2, 1],
  [2, 3],
  [2, 4],
  [2, 5],
  [2, 6],
  [3, 1],
  [3, 2],
  [3, 4],
  [3, 5],
  [3, 6],
  [4, 1],
  [4, 2],
  [4, 3],
  [4, 5],
  [4, 6], 
  [5, 1],
  [5, 2],
  [5, 3],
  [5, 4],
  [5, 6],
  [6, 1],
  [6, 2],
  [6, 3],
  [6, 4],
  [6, 5]
]

1000000007で割った余りを求めなさい

  • 初見だとなんのことやらさっぱりわからないとおもいます
  • この数字はなんなのだろう？　-> 素数なのだそうです
  • 私はちゃんと説明できませんのでリンクを紹介しておきます
  • 足し算、引き算、掛け算は、計算の途中過程で積極的に余りをとってよいということがあるようです
  • 競技プログラミング界では常識のことのようですが、なぜそれで正しい答えがでるのか、そんなの学生時代にでてきたっけ？　と結局ちゃんとはわかっておらず、おっかなびっくりで使うわけですがとりあえずは丸暗記でもこれは知っておいたほうがよいです
  • ElixirでABC178のC Ubiquityを解いてみるを参考にしてみてください
    • 私が解けなかった問題を他の方が解いてくださいました

試しにやってみましょう！

  • ここまでいろいろ書いてきましたがとりあえず簡単な問題を一題やってみましょう
  • PracticeA - Welcome to AtCode
  • 問題は上記リンクをご参照ください
$ mix new at_coder
  • とおもむろにプロジェクトの雛形を作ります
  • lib/practice_1.exを作ります
  • まずは解答のキモになる部分だけを作ります
defmodule Practice1 do
  @doc ~S"""
  https://atcoder.jp/contests/abs/tasks/practice_1

  ## Examples

      iex> Practice1.solve(1, 2, 3, "test")
      "6 test"

      iex> Practice1.solve(72, 128, 256, "myonmyon")
      "456 myonmyon"

  """
  def solve(a, b, c, s), do: "#{a + b + c} #{s}"
end

  • 解答のキモになる部分をDoctestsで書きます

  • test/at_coder_test.exsに設定を追加します

defmodule AtCoderTest do
  use ExUnit.Case
  doctest AtCoder
  doctest Practice1
  • テストの実行ができます！
$ mix test  
Compiling 1 file (.ex)
....

Finished in 0.1 seconds
3 doctests, 1 test, 0 failures

🎉🎉🎉

  • あとはlib/practice_1.exに入力と出力のmain/0関数を追加します
defmodule Practice1 do
  def main do
    a = IO.read(:line) |> String.trim() |> String.to_integer()

    [b, c] =
      IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)

    s = IO.read(:line) |> String.trim()

    solve(a, b, c, s)
    |> IO.puts()
  end

  @doc ~S"""
  https://atcoder.jp/contests/abs/tasks/practice_1

  ## Examples

      iex> Practice1.solve(1, 2, 3, "test")
      "6 test"

      iex> Practice1.solve(72, 128, 256, "myonmyon")
      "456 myonmyon"

  """
  def solve(a, b, c, s), do: "#{a + b + c} #{s}"
end
  • 提出前に手元のiexで動かしてみます
$ iex -S mix

iex> Practice1.main
72
128 256
myonmyon
456 myonmyon
:ok
  • 正しそうです
  • 提出の際にはモジュール名はMainにしておきましょう
  • パスしています
  • 🎉🎉🎉

過去問精選10問

AtCoderをやることで得られるもの

  • 特にEnumモジュールと仲良くなれます
  • Elixirは公式ドキュメントをみるのが一番わかりやすいです
    • 英語で書かれていますが、実行例付きなのでとても読みやすいです

インストール

Wrapping Up

  • Enjoy Elixir !!! 🚀🚀🚀

Discussion