AtCoder Beginners Selection with Elixir

はじめに

今年度から大学院生となり, 研究活動の一部としてElixirの学習を始めました.
私はもともと競プロerでしたので, 新しい言語の練習にも競技プログラミングを利用しようと思い, AtCoder の問題演習を中心にしていくことにしました.

AtCoder の"入門者向け"問題集 AtCoder Beginners Selection が公式に用意されているため, これを解いた記録を残します.

AtCoder 全体のルール

今後の説明のため, 提出されたプログラムがAtCoderでどのように処理されるかについて説明します.
この章については, 公式のルール説明から必要な部分を抜き出しています.

処理内容

各問題ごとに指定されたフォーマットに従って標準入力から文字列が入力されます. これを処理して適切な内容を標準出力に出せば "AC" (Acceptedの略. 要するに正解)が得られます.

AtCoder側でElixirプログラムを実行する際には, 内部で以下のようなコマンドを走らせています.

bash -c 'elixirc ./Main.ex -o . 1>&2'
elixir -pa . -e Main.main

したがって, Elixirを用いて回答する際には, そのプログラムにMainという名のモジュールがあり, その中のmainをエントリポイントとする必要があります.

不適切な提出とは

前節では正解を出す手順について説明しましたが, ここからは「正解にならない」プログラムについて説明します.

WA/Wrong Answer

最も分かりやすい"不正解". 出力内容が問題文の指示に合っていないパターンです.

CE/Compilation Error

コンパイルエラー. そもそもElixirプログラムとして正しくないようなコードを提出するとこの判定になります.
うっかり普段使っているJavaコードとしてElixirコードを提出したりするとこうなります()

RE/Runtime Error

ランタイムエラー. 実行中に何らかの理由でエラーが発生したパターン. 配列の範囲外参照とか多いですね.

TLE/Time Limit Exceeded

時間制限. 提出するプログラムは, 実行開始から「2秒以内」で出力を完了して停止する必要があります. この時間を越えた時に出るのがTLEです. これを避けるために競プロerは計算量のオーダーについて頭を悩ませているわけです.

回答記録

PracticeA - Welcome to AtCoder

問題概要

3つの整数と1つの文字列が下のような形で入力される. 「3整数の和」と「最後の文字列」を並べて標準出力せよ.

整数1
整数2 整数3
文字列

プログラム

Main.ex

defmodule Main do
    def main do
        a = IO.gets("") |> String.trim() |> String.to_integer
        [b, c] = IO.gets("") |> String.trim() |> String.split(" ", trim: true) |> Enum.map(&String.to_integer(&1))
        s = IO.gets("") |> String.trim()
        IO.puts("#{a+b+c} #{s}")
    end
end

所感

(改行や空白を含む)入出力の処理について学ぶ. 基本的だがこれから先も重要なテク.

ABC086A - Product

問題概要

2つの整数が空白区切りで与えられる. 積の偶奇を判定せよ.

プログラム

Main.ex

defmodule Main do
    def main do
        a = IO.gets("") |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer(&1))
        prod = a |> List.foldl(1, fn x, acc -> x*acc end)
        if rem(prod, 2) == 0 do
            IO.puts("Even")
        else
            IO.puts("Odd")
        end
    end
end

所感

整数の個数が分かっているのだから別にfoldとか使わなくてもよいのだが, リストの扱いの練習としてこの方法を選んだ.

        # この問題ならこれでも十分
        [x,y] = IO.gets("") |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer(&1))
        prod = x * y

今後の問題で応用していきたいところ.

ABC081A - Placing Marbles

問題概要

0と1のみからなる文字列が与えられる. その中の文字1を数えよ.

プログラム

Main.ex

defmodule Main do
    def main do
        a = IO.gets("") |> String.trim() |> String.split("", trim: true) |> Enum.map(&String.to_integer(&1))
        sum = a |> List.foldl(0, fn x, acc -> x+acc end)
        IO.puts(sum)
    end
end

所感

入力を受け取る段階で1文字ずつに区切っておいた. こうすることで単純な和を取ればよいことになる.

ABC081B - Shift only

問題概要

$N$個の整数が与えられる. 「全ての整数を2で割る(奇数を割ることはできない)」という処理は何回行えるか.

プログラム

Main.ex

defmodule Main do
    def pow2(n) do
        if rem(n, 2)==0 do
            1 + pow2(div(n, 2))
        else
            0
        end
    end
 
    def main do
        _ = IO.gets("") |> String.trim() |> String.to_integer
        a = IO.gets("") |> String.trim() |> String.split(" ", trim: true) |> Enum.map(&String.to_integer(&1))
        a |> Enum.map(&pow2(&1)) |> List.foldr(100000, (fn x, ac -> if x>ac do ac else x end end)) |> IO.puts
    end
end

所感

はじめてエントリポイント以外の関数を作成した問題. これをベタ書きだけでやろうと思ったら結構コードが複雑になりそう...

ABC087B - Coins

問題概要

500円玉$A$枚, 100円玉$B$枚, 50円玉$C$枚の一部を使ってちょうど$X$円を払う方法は何通りあるか? $O(ABC)$の計算量でOK.

一般的な解法

for(int a=0; a<=A; a++){
  for(int b=0; b<=B; b++){
    for(int c=0; c<=C; c++){...}
  }
}

的なことを書けばいい.

プログラム

Main.ex

defmodule Main do
    def solve_1(c, n) do
        if rem(n, 50) == 0 and n >= 0 and n/50 <= c do 1 else 0 end
    end
    def solve_2(b, c, n) do
        0..b |> Enum.map(fn i -> solve_1(c, n-100*i) end) |> List.foldl(0, fn (x, acc) -> x+acc end)
    end
    def solve_3(a, b, c, n) do
        0..a |> Enum.map(fn i -> solve_2(b, c, n-500*i) end) |> List.foldl(0, fn (x, acc) -> x+acc end)
    end

    def main do
        a = IO.gets("") |> String.trim |> String.to_integer
        b = IO.gets("") |> String.trim |> String.to_integer
        c = IO.gets("") |> String.trim |> String.to_integer
        n = IO.gets("") |> String.trim |> String.to_integer


        IO.puts(solve_3(a, b, c, n))
    end
end

所感

3重ループそれぞれに対応する関数を書いてmapすることでなんとかAC.
...もうちょっとマシな方法がありそうな気もするんだけどなぁ

ABC083B - Some Sums

問題概要

$1$以上$N$以下の整数のうち, $10$進法での各桁の和が$A$以上$B$以下であるものの総和を求めてください. $O(N^2)$でも十分間に合う程度の制約.

プログラム

Main.ex

defmodule Main do
    def dsum(n) do # 整数を受け取って各桁の和を返す
        if div(n, 10)==0 do # 10未満ならその値自身を返す
            n
        else # 末尾の数字 + 残り
            rem(n, 10) + dsum(div(n, 10))
        end
    end

    def main do
        [n, a, b] = IO.gets("") |> String.trim()
                 |> String.split(" ", trim: true)
                 |> Enum.map(&String.to_integer(&1))
        sum = 1..n
           |> Enum.map(fn n ->if a<=dsum(n) and dsum(n)<=b do n else 0 end end) 
           |> List.foldl(0, fn (x, acc) -> x+acc end)
        sum |> IO.puts
    end
end

所感

Shift Only と同様, 補助関数をちゃんと用意することでプログラムが一気にわかりやすくなるタイプの問題.

ABC088B - Card Game for Two

問題概要

数字が書かれたN枚のカードをAliceとBobが交互に1枚ずつ選んで取っていく. お互いが「自分の取ったカードに書かれた数字の総和」を最大化するとき, 2人の点数差を求めよ.

プログラム

Main.ex

defmodule Main do
    def main do
        n = IO.gets("") |> String.trim() |> String.to_integer
        a = IO.gets("") |> String.trim() |> String.split(" ", trim: true) |> Enum.map(&String.to_integer(&1))
         |> Enum.sort |> Enum.reverse
        total = a |> Enum.sum
        alice = a |> Enum.take_every(2) |> Enum.sum
        bob = total - alice
        IO.puts(alice-bob)
    end
end

所感

この辺から標準ライブラリのドキュメントとのにらめっこを始める.
単純にmapしてfold! という訳にはいかない問題が出始めるのがこの辺り.
ところで, Bobの得点 = 総和 - Aliceの得点なので何とかなったが, 直接Bobの得点を求める方法ってありますか?
(要は take_everyのオフセット付きver. みたいなのが欲しい)

ABC085B - Kagami Mochi

問題概要

N個の数字が与えられる. 互いに相異なるような数をいくつまで取ることができるか?

プログラム

Main.ex

defmodule Main do
    def main do
        n = IO.gets("") |> String.trim() |> String.to_integer
        d = 1..n |> Enum.map(fn _ ->IO.gets("") |> String.trim() |> String.to_integer end)
        d |> Enum.uniq |> length |> IO.puts
    end
end

所感

標準ライブラリにズバリやりたいことが実装されているパターン.
これは知らないとかなり厳しいだろうなぁ...

ABC085C - Otoshidama

問題概要

$N, Y$が与えられる. $10000a + 5000b + 1000c = Y, a+b+c=N$ の非負整数解を1つ求めよ(存在しない場合はその旨報告せよ). 許容計算量は$O(N^2)$.

一般的な解法

for(int a=0; a<=N; a++){
  for(int b=0; b<=N; b++){
    for(int c=0; c<=N; c++){
      if(a+b+c==N && 10000*a+5000*b+1000*c==Y){...}
    }
  }
}

のような3重ループだと計算量$O(N^3)$で実行時間制限に間に合わない.

for(int a=0; a<=N; a++){
  for(int b=0; b<=N; b++){
    int c = N - a - b;
    if(c >= 0 && 10000*a+5000*b+1000*c==Y){...}
  }
}

とすれば$O(N^2)$で間に合ってACがとれる.

プログラム

Main.ex

defmodule Main do
    def solve_1(a, b, n, y) do
        if n>=0 and 1000*n==y do {a,b,n} else nil end
    end
    def solve_2(a, n, y) do
        0..(div(y, 5000)) |> Enum.map(fn i -> solve_1(a, i, n-i, y-5000*i) end) |> List.foldl(nil, fn (x,y) -> if (is_nil(x)) do y else x end end)
    end
    def solve_3(n, y) do
       0..(div(y, 10000)) |> Enum.map(fn i -> solve_2(i, n-i, y-10000*i) end) |> List.foldl(nil, fn (x,y) -> if (is_nil(x)) do y else x end end)
    end

    def main do
        [n, y] = IO.gets("") |> String.trim() |> String.split(" ", trim: true) |> Enum.map(&String.to_integer(&1))

        ans = solve_3(n, y)
        if(is_nil(ans)) do
            IO.puts("-1 -1 -1")
        else
            {a,b,c} = ans
            IO.puts("#{a} #{b} #{c}")
        end
    end
end

所感

Coinsと同様, ループごとに補助関数を定義する方法でゴリ押し. もうちょっとなんとかならんものかなぁ...

ABC049C - 白昼夢

問題概要

与えられた文字列$S$が, dream, dreamer, erase, eraser を連結することで作れるかどうか判定せよ. 許容計算量は$O(|S|)$.

一般的な解法

手前から区切っていこうとすると dream と dreamer のどちらを用いるべきか分からず詰むが, 実は後ろから区切っていくと使える文字列が高々1択になるので$O(|S|)$で判定できる. 詳細はこちら

プログラム

Main.ex

defmodule Main do
    def proper_list?([]) do true end
    def proper_list?(["m", "a", "e", "r", "d" | tl]) do proper_list?(tl) end
    def proper_list?(["r", "e", "m", "a", "e", "r", "d" | tl]) do proper_list?(tl) end
    def proper_list?(["e", "s", "a", "r", "e" | tl]) do proper_list?(tl) end
    def proper_list?(["r", "e", "s", "a", "r", "e" | tl]) do proper_list?(tl) end
    def proper_list?(_) do false end

    def main do
        a = IO.gets("") |> String.trim() |> String.split("", trim: true)
        if proper_list?(a |> Enum.reverse) do
            IO.puts("YES")
        else
            IO.puts("NO")
        end
    end
end

所感

もともとは下のようなプログラムを書いていたのですが, TLEが生えて悩んでいました.

    def proper_string?(s, n) do
        cond do
            n < 0 -> true
            s |> String.slice((n-4)..n) |> String.equivalent?("dream") -> proper_string?(s, n-5)
            s |> String.slice((n-6)..n) |> String.equivalent?("dreamer") -> proper_string?(s, n-7)
            s |> String.slice((n-4)..n) |> String.equivalent?("erase") -> proper_string?(s, n-5)
            s |> String.slice((n-5)..n) |> String.equivalent?("eraser") -> proper_string?(s, n-6)
            true -> false
        end
    end

どうやらsliceにはもとの文字列の長さに比例する時間がかかるのかな?
関数型言語を使う以上, パターンマッチングをうまく使う意識が必要と感じた問題でした.

ABC086C - Traveling

問題概要

AtCodeerくんは, 時刻$0$で点$(0,0)$にいて, 時間$1$ごとに隣り合う格子点に移動する. 「時刻$t$では点$(x,y)$にいる」という形の制約が$N$個与えられるので, 全てを満たすような移動経路が存在するかどうか判定せよ.

プログラム

Main.ex

defmodule Main do
    def distance({x1, y1}, {x2, y2}) do
        abs(x1 - x2) + abs(y1 - y2)
    end
    def can_travel({x1, y1}, {x2, y2}, t) do
        d = distance({x1, y1}, {x2, y2})
        d <= t and rem(t-d, 2)==0
    end
    def can_travel({t1, x1, y1}, {t2, x2, y2}) do
        can_travel({x1, y1}, {x2, y2}, t2-t1)
    end

    def proper_plan?([]) do true end
    def proper_plan?([_]) do true end
    def proper_plan?([a, b | t]) do
        can_travel(a, b) and proper_plan?([b | t])
    end

    def main do
        n = IO.gets("") |> String.trim() |> String.to_integer
        d = 1..n
            |> Enum.map(fn _ ->IO.gets("") |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer(&1)) end)
            |> Enum.map(fn [t,x,y] -> {t, x, y} end)
        d = [{0, 0, 0} | d]

        if proper_plan?(d) do
            IO.puts("Yes")
        else
            IO.puts("No")
        end
    end
end

所感

ABS最後の問題だけあって補助関数が大量に出現.
distance/2 : 2点間の最短距離を計算する関数.
can_travel/3 : 第1/第2引数が座標, 第3引数が時間. 2点間を指定された時間で移動できるか否かを返す.
can_travel/2 : 各引数は{時刻, x座標, y座標}のタプル. 2点間を指定された時刻に移動できるか否かを返す.
proper_plan?/1 : {時刻, x座標, y座標}のタプルをリストにして与える. 実行できる行程か否かを返す.
ABSのボスらしさを感じつつ, 関数型言語っぽいプログラムを書けたのではないかと思う.

総括

以上でABSの全問題をElixirでACすることができました. 問題演習を通して基礎的なElixirプログラムを書く力がつきました.
とはいえ, 競技プログラミングによる演習だけでは身につかない部分も少なくない(例えば複数ファイルの連携)ため, 今後はそういった点も含めて幅広い学習を進めていこうと思います.

なお, 本記事に登場するプログラムは私が独学で得た知識によって記述したものであるため, 必ずしも「Elixirの推奨コーディングスタイル」に一致することを保証しません.
より適切な記法がある場合はコメント等で一報いただけると励みになります.