はじめに
AtCoder の Beginners Selection コンテスト ABC043 問題を Elixir Livebook で回答しました
ABC043A - キャンディーとN人の子供イージー
ABC043A 問題
ABC043A 実装したノートブック
ABC043A 入出力例
"""
3
"""
|> Main.solve()
|> then(&(&1 == 6))
"""
10
"""
|> Main.solve()
|> then(&(&1 == 55))
"""
1
"""
|> Main.solve()
|> then(&(&1 == 1))
ABC043A 回答1
単純にnまでの総和です
defmodule Main do
def main do
:stdio
|> IO.read(:all)
|> solve()
|> IO.puts()
end
def solve(input) do
n =
input
|> String.trim()
|> String.to_integer()
Enum.sum(0..n)
end
end
実行時間は 357 ms でした
ABC043A 回答2
全てパイプで繋いだバージョンです
defmodule Main do
def main do
:stdio
|> IO.read(:all)
|> solve()
|> IO.puts()
end
def solve(input) do
input
|> String.trim()
|> String.to_integer()
|> Range.new()
|> Enum.sum()
end
end
実行時間は 365 ms でした
ABC043B - バイナリハックイージー
ABC043B 問題
ABC043B 実装したノートブック
ABC043B 入出力例
"""
01B0
"""
|> Main.solve()
|> then(&(&1 == "00"))
"""
0BB1
"""
|> Main.solve()
|> then(&(&1 == "1"))
"""
1
"""
|> Main.solve()
|> then(&(&1 == 1))
ABC043B 回答
各キーの入力を Enum.reduce で順次実行しています
ただし、末尾に加えるよりも先頭に加える方が楽なので、右方向ではなく左方向に処理してから、最後に反転させます
また、空になった状態で更に消すことはできないので、その場合は空を返しています
defmodule Main do
def main do
:stdio
|> IO.read(:all)
|> solve()
|> IO.puts()
end
def solve(input) do
input
|> String.trim()
|> String.codepoints()
|> Enum.reduce([], fn key, acc ->
case key do
"B" -> if Enum.empty?(acc), do: [], else: tl(acc)
new -> [new | acc]
end
end)
|> Enum.reverse()
|> Enum.join()
end
end
実行時間は 516 ms でした
ABC043C - いっしょ
ABC043C 問題
ABC043C 実装したノートブック
ABC043C 入出力例
"""
2
4 8
"""
|> Main.solve()
|> then(&(&1 == 8))
"""
3
1 1 3
"""
|> Main.solve()
|> then(&(&1 == 3))
"""
3
4 2 5
"""
|> Main.solve()
|> then(&(&1 == 5))
"""
4
-100 -100 -100 -100
"""
|> Main.solve()
|> then(&(&1 == 0))
ABC043C 回答1
C 問題までなら何も引っかからずにスイスイ解けますね
この問題は整数で分散を計算せよ、ということなので、その通りに実装しています
:math.pow は結果が Float になるので、最後に floor で整数にしています
defmodule Main do
def main do
:stdio
|> IO.read(:all)
|> solve()
|> IO.puts()
end
defp split_lines(lines) do
lines
|> String.trim()
|> String.split("\n")
end
defp split_words(words) do
String.split(words, " ")
end
def solve(input) do
a =
input
|> String.trim()
|> split_lines()
|> Enum.at(1)
|> split_words()
|> Enum.map(&String.to_integer/1)
mean =
(Enum.sum(a) / length(a))
|> round()
a
|> Enum.map(fn a_i ->
:math.pow(a_i - mean, 2)
end)
|> Enum.sum()
|> floor()
end
end
実行結果は 346 ms でした
ABC043D - アンバランス
この問題は自力では部分点までしかもらえませんでした
入力が短い間は愚直に問題文通りの実装をしていれば良いのですが、入力が長くなるとそれでは制限時間を超えます
こちらの記事を参考に解きました
ABC043D 問題
ABC043D 実装したノートブック
ABC043D 入出力例
"""
needed
"""
|> Main.solve()
|> then(&(&1 == "2 3"))
"""
atcoder
"""
|> Main.solve()
|> then(&(&1 == "-1 -1"))
ABC043D 制限時間超過 回答
愚直に問題文通りの処理を実装したパターンです
これでは計算量が多いので、入力が長いと TLE になってしまいます
defmodule Main do
def main do
:stdio
|> IO.read(:all)
|> solve()
|> IO.puts()
end
defp is_unbalance?(str) do
len = String.length(str)
half = floor(len / 2)
str
|> String.codepoints()
|> Enum.group_by(& &1)
|> Enum.any?(fn {_, list} -> length(list) > half end)
end
def solve(input) do
s = String.trim(input)
len = String.length(s)
for sub_start <- 0..(len - 2),
sub_end <- (sub_start + 1)..(len - 1),
sub_s = String.slice(s, sub_start..sub_end),
is_unbalance?(sub_s) do
[sub_start + 1, sub_end + 1]
end
|> Enum.at(0, [-1, -1])
|> Enum.join(" ")
end
end
ABC043D 回答1
参考にした記事にある通り、アンバランスな部分文字列を含んでいる = 以下の条件を満たす文字列を含んでいる、ということです
-
aaのように同じ文字が連続している -
axaのように、同じ文字の間に1文字別の文字が挟まっている
axya のように2文字以上別の文字を挟んだ場合、同じ文字が過半数を超えません
また、 axyazba というように、2文字以上別の文字を挟んだものを繰り返しても決して過半数を超えることはありません
従って、入力の中で、同じ文字の間に挟まれる別の文字が 0 〜 1 文字になっている部分文字列を探せば良いことになります
リストへの参照だと非常に遅く、 TLE になってしまうため、各文字を ETS に格納してから参照するようにしました
defmodule Main do
def main do
:stdio
|> IO.read(:all)
|> solve()
|> IO.puts()
end
defp renew_table(objects, table_name) do
if :ets.info(table_name) != :undefined do
:ets.delete(table_name)
end
:ets.new(table_name, [:set, :protected, :named_table])
:ets.insert(table_name, objects)
end
defp lookup(table_name, key) do
case :ets.lookup(table_name, key) do
[{_, value}] ->
value
_ ->
""
end
end
def solve(input) do
list =
input
|> String.trim()
|> String.codepoints()
list
|> Enum.with_index()
|> Enum.map(fn {char, index} -> {index, char} end)
|> renew_table(:char_list)
0..(length(list) - 2)
|> Enum.map(fn sub_start ->
char_1 = lookup(:char_list, sub_start)
char_2 = lookup(:char_list, sub_start + 1)
char_3 = lookup(:char_list, sub_start + 2)
case char_1 do
^char_2 ->
[sub_start + 1, sub_start + 2]
^char_3 ->
[sub_start + 1, sub_start + 3]
_ ->
[]
end
end)
|> Enum.find(
[-1, -1],
fn
[] -> false
_ -> true
end
)
|> Enum.join(" ")
end
end
実行時間は 654 ms でした
ABC043D 回答2
もっとシンプルに、正規表現でこの条件に該当するものを検索してみました
正規表現については以下の記事を参考にしました
後方参照 \1 を使うことで、前に一致した文字列と同じ文字列がある、という正規表現を書けます
(.).?\1 とすると、何かの文字があり、 0 〜 1 文字の何らかの別文字を挟んで、最初と同じ文字がある、という意味になります
Elixir では Regex.run で正規表現による部分文字列の抽出ができます
また、オプションに return: :index を指定することで、文字列そのものではなく、文字列の位置（開始位置と長さ）を取得できます
正規表現を使うことですごくシンプルになりました
defmodule Main do
def main do
:stdio
|> IO.read(:all)
|> solve()
|> IO.puts()
end
def solve(input) do
s = String.trim(input)
{start_index, end_index} =
case Regex.run(~r/(.).?\1/, s, return: :index) do
[{index, len} | _] -> {index + 1, index + len}
nil -> {-1, -1}
end
"#{start_index} #{end_index}"
end
end
実行時間は 357 ms でした
まとめ
正規表現は偉大ですね