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
文字列
プログラム
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つの整数が空白区切りで与えられる. 積の偶奇を判定せよ.
プログラム
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を数えよ.
プログラム
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で割る(奇数を割ることはできない)」という処理は何回行えるか.
プログラム
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(A*B*C)$の計算量でOK.
一般的な解法
for(int a=0; a<=A; a++){
for(int b=0; b<=B; b++){
for(int c=0; c<=C; c++){...}
}
}
的なことを書けばいい.
プログラム
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)$でも十分間に合う程度の制約.
プログラム
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人の点数差を求めよ.
プログラム
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個の数字が与えられる. 互いに相異なるような数をいくつまで取ることができるか?
プログラム
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がとれる.
プログラム
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|)$で判定できる. 詳細はこちら
プログラム
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$個与えられるので, 全てを満たすような移動経路が存在するかどうか判定せよ.
プログラム
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の推奨コーディングスタイル」に一致することを保証しません.
より適切な記法がある場合はコメント等で一報いただけると励みになります.
Author And Source
この問題について(AtCoder Beginners Selection with Elixir), 我々は、より多くの情報をここで見つけました https://qiita.com/NASU41/items/a2b0d882e8cc0ae2a5a8著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .