トヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330)の B - Minimize Abs 1 を Elixir で解きましたので，ご報告します．
問題
簡易ローカルテスト環境の構築
次のようなMakefileを書きました．
Makefile
.phony: all clean
test: test_ex
test_ex:
elixir test.exs < in1.txt | diff - out1.txt
elixir test.exs < in2.txt | diff - out2.txt
test.exs
Code.eval_file("main.exs")
Main.main()
入力例1をin1.txt，出力例1をout1.txtのように与え，main.exsに解答を書きます．その後，makeコマンドを実行します．
ローカルテストを通すまでの試行錯誤の過程
ひとまず入力を一通り読み込むところを作ります．
main.exs
defmodule Main do
def main() do
[n, l, r] = read_int_list()
a = read_int_list()
IO.inspect(n, label: "n")
IO.inspect(l, label: "l")
IO.inspect(r, label: "r")
IO.inspect(a, label: "a")
end
def read_int_list() do
IO.read(:line)
|> String.trim()
|> String.split(" ")
|> Enum.map(&String.to_integer/1)
end
end
テスト実行するときは次のようにします．
% elixir test.exs < in1.txt
n: 5
l: 4
r: 7
a: [3, 1, 4, 9, 7]
ちゃんと入力できていますので，次に進みます．
IO.inspect(n, label: "n")のようにすると，n: 5のように表示してくれます．便利ですね．
さしあたり，aを一通り走査してみましょう．
main.exs
defmodule Main do
def main() do
[n, l, r] = read_int_list()
a = read_int_list()
a
|> Enum.map(fn a ->
IO.inspect(a, label: "a")
end)
end
def read_int_list() do
IO.read(:line)
|> String.trim()
|> String.split(" ")
|> Enum.map(&String.to_integer/1)
end
end
% elixir test.exs < in1.txt
warning: variable "l" is unused (if the variable is not meant to be used, prefix it with an underscore)
main.exs:3: Main.main/0
warning: variable "n" is unused (if the variable is not meant to be used, prefix it with an underscore)
main.exs:3: Main.main/0
warning: variable "r" is unused (if the variable is not meant to be used, prefix it with an underscore)
main.exs:3: Main.main/0
a: 3
a: 1
a: 4
a: 9
a: 7
警告は無視すると，ちゃんとaを走査できています．
xをlからrまで走査する二重ループを書いてみましょうか．
main.exs
defmodule Main do
def main() do
[n, l, r] = read_int_list()
a = read_int_list()
a
|> Enum.map(fn a ->
l..r
|> Enum.map(fn x ->
IO.inspect({a, x}, label: "{a, x}")
end)
end)
end
def read_int_list() do
IO.read(:line)
|> String.trim()
|> String.split(" ")
|> Enum.map(&String.to_integer/1)
end
end
% elixir test.exs < in1.txt
warning: variable "n" is unused (if the variable is not meant to be used, prefix it with an underscore)
main.exs:3: Main.main/0
{a, x}: {3, 4}
{a, x}: {3, 5}
{a, x}: {3, 6}
{a, x}: {3, 7}
{a, x}: {1, 4}
{a, x}: {1, 5}
{a, x}: {1, 6}
{a, x}: {1, 7}
{a, x}: {4, 4}
{a, x}: {4, 5}
{a, x}: {4, 6}
{a, x}: {4, 7}
{a, x}: {9, 4}
{a, x}: {9, 5}
{a, x}: {9, 6}
{a, x}: {9, 7}
{a, x}: {7, 4}
{a, x}: {7, 5}
{a, x}: {7, 6}
{a, x}: {7, 7}
良い感じです．
条件 $|X_i - A_i|$ を表示してみましょう．
main.exs
defmodule Main do
def main() do
[n, l, r] = read_int_list()
a = read_int_list()
a
|> Enum.map(fn a ->
l..r
|> Enum.map(fn x ->
IO.inspect(abs(x - a), label: "abs(x - a)")
end)
end)
end
def read_int_list() do
IO.read(:line)
|> String.trim()
|> String.split(" ")
|> Enum.map(&String.to_integer/1)
end
end
% elixir test.exs < in1.txt
warning: variable "n" is unused (if the variable is not meant to be used, prefix it with an underscore)
main.exs:3: Main.main/0
abs(x - a): 1
abs(x - a): 2
abs(x - a): 3
abs(x - a): 4
abs(x - a): 3
abs(x - a): 4
abs(x - a): 5
abs(x - a): 6
abs(x - a): 0
abs(x - a): 1
abs(x - a): 2
abs(x - a): 3
abs(x - a): 5
abs(x - a): 4
abs(x - a): 3
abs(x - a): 2
abs(x - a): 3
abs(x - a): 2
abs(x - a): 1
abs(x - a): 0
良い感じです．
このノリで，三重ループでyも求めてみましょう．
main.exs
defmodule Main do
def main() do
[n, l, r] = read_int_list()
a = read_int_list()
a
|> Enum.map(fn a ->
l..r
|> Enum.map(fn x ->
l..r
|> Enum.map(fn y ->
IO.inspect({abs(x - a) <= abs(y - a), x}, label: "{abs(x - a) <= abs(y - a), x}")
end)
end)
end)
end
def read_int_list() do
IO.read(:line)
|> String.trim()
|> String.split(" ")
|> Enum.map(&String.to_integer/1)
end
end
実行すると次のような感じです．
{abs(x - a) <= abs(y - a), x}: {true, 4}
{abs(x - a) <= abs(y - a), x}: {true, 4}
{abs(x - a) <= abs(y - a), x}: {true, 4}
{abs(x - a) <= abs(y - a), x}: {true, 4}
{abs(x - a) <= abs(y - a), x}: {false, 5}
{abs(x - a) <= abs(y - a), x}: {true, 5}
{abs(x - a) <= abs(y - a), x}: {true, 5}
{abs(x - a) <= abs(y - a), x}: {true, 5}
{abs(x - a) <= abs(y - a), x}: {false, 6}
{abs(x - a) <= abs(y - a), x}: {false, 6}
{abs(x - a) <= abs(y - a), x}: {true, 6}
{abs(x - a) <= abs(y - a), x}: {true, 6}
{abs(x - a) <= abs(y - a), x}: {false, 7}
{abs(x - a) <= abs(y - a), x}: {false, 7}
{abs(x - a) <= abs(y - a), x}: {false, 7}
{abs(x - a) <= abs(y - a), x}: {true, 7}
{abs(x - a) <= abs(y - a), x}: {true, 4}
{abs(x - a) <= abs(y - a), x}: {true, 4}
{abs(x - a) <= abs(y - a), x}: {true, 4}
{abs(x - a) <= abs(y - a), x}: {true, 4}
{abs(x - a) <= abs(y - a), x}: {false, 5}
{abs(x - a) <= abs(y - a), x}: {true, 5}
{abs(x - a) <= abs(y - a), x}: {true, 5}
{abs(x - a) <= abs(y - a), x}: {true, 5}
{abs(x - a) <= abs(y - a), x}: {false, 6}
{abs(x - a) <= abs(y - a), x}: {false, 6}
{abs(x - a) <= abs(y - a), x}: {true, 6}
{abs(x - a) <= abs(y - a), x}: {true, 6}
{abs(x - a) <= abs(y - a), x}: {false, 7}
{abs(x - a) <= abs(y - a), x}: {false, 7}
{abs(x - a) <= abs(y - a), x}: {false, 7}
{abs(x - a) <= abs(y - a), x}: {true, 7}
{abs(x - a) <= abs(y - a), x}: {true, 4}
{abs(x - a) <= abs(y - a), x}: {true, 4}
{abs(x - a) <= abs(y - a), x}: {true, 4}
{abs(x - a) <= abs(y - a), x}: {true, 4}
{abs(x - a) <= abs(y - a), x}: {false, 5}
{abs(x - a) <= abs(y - a), x}: {true, 5}
{abs(x - a) <= abs(y - a), x}: {true, 5}
{abs(x - a) <= abs(y - a), x}: {true, 5}
{abs(x - a) <= abs(y - a), x}: {false, 6}
{abs(x - a) <= abs(y - a), x}: {false, 6}
{abs(x - a) <= abs(y - a), x}: {true, 6}
{abs(x - a) <= abs(y - a), x}: {true, 6}
{abs(x - a) <= abs(y - a), x}: {false, 7}
{abs(x - a) <= abs(y - a), x}: {false, 7}
{abs(x - a) <= abs(y - a), x}: {false, 7}
{abs(x - a) <= abs(y - a), x}: {true, 7}
{abs(x - a) <= abs(y - a), x}: {true, 4}
{abs(x - a) <= abs(y - a), x}: {false, 4}
{abs(x - a) <= abs(y - a), x}: {false, 4}
{abs(x - a) <= abs(y - a), x}: {false, 4}
{abs(x - a) <= abs(y - a), x}: {true, 5}
{abs(x - a) <= abs(y - a), x}: {true, 5}
{abs(x - a) <= abs(y - a), x}: {false, 5}
{abs(x - a) <= abs(y - a), x}: {false, 5}
{abs(x - a) <= abs(y - a), x}: {true, 6}
{abs(x - a) <= abs(y - a), x}: {true, 6}
{abs(x - a) <= abs(y - a), x}: {true, 6}
{abs(x - a) <= abs(y - a), x}: {false, 6}
{abs(x - a) <= abs(y - a), x}: {true, 7}
{abs(x - a) <= abs(y - a), x}: {true, 7}
{abs(x - a) <= abs(y - a), x}: {true, 7}
{abs(x - a) <= abs(y - a), x}: {true, 7}
{abs(x - a) <= abs(y - a), x}: {true, 4}
{abs(x - a) <= abs(y - a), x}: {false, 4}
{abs(x - a) <= abs(y - a), x}: {false, 4}
{abs(x - a) <= abs(y - a), x}: {false, 4}
{abs(x - a) <= abs(y - a), x}: {true, 5}
{abs(x - a) <= abs(y - a), x}: {true, 5}
{abs(x - a) <= abs(y - a), x}: {false, 5}
{abs(x - a) <= abs(y - a), x}: {false, 5}
{abs(x - a) <= abs(y - a), x}: {true, 6}
{abs(x - a) <= abs(y - a), x}: {true, 6}
{abs(x - a) <= abs(y - a), x}: {true, 6}
{abs(x - a) <= abs(y - a), x}: {false, 6}
{abs(x - a) <= abs(y - a), x}: {true, 7}
{abs(x - a) <= abs(y - a), x}: {true, 7}
{abs(x - a) <= abs(y - a), x}: {true, 7}
{abs(x - a) <= abs(y - a), x}: {true, 7}
Enum.reduceを使って$|X_i - A_i| \leq |Y_i - A_i|$を累積してみましょう．
main.exs
defmodule Main do
def main() do
[n, l, r] = read_int_list()
a = read_int_list()
a
|> Enum.map(fn a ->
l..r
|> Enum.map(fn x ->
b = Enum.reduce(l..r, true, fn y, acc ->
abs(x - a) <= abs(y - a) and acc
end)
IO.inspect({x, b}, label: "{x, true or false}")
end)
end)
end
def read_int_list() do
IO.read(:line)
|> String.trim()
|> String.split(" ")
|> Enum.map(&String.to_integer/1)
end
end
% elixir test.exs < in1.txt
warning: variable "n" is unused (if the variable is not meant to be used, prefix it with an underscore)
main.exs:3: Main.main/0
{x, true or false}: {4, true}
{x, true or false}: {5, false}
{x, true or false}: {6, false}
{x, true or false}: {7, false}
{x, true or false}: {4, true}
{x, true or false}: {5, false}
{x, true or false}: {6, false}
{x, true or false}: {7, false}
{x, true or false}: {4, true}
{x, true or false}: {5, false}
{x, true or false}: {6, false}
{x, true or false}: {7, false}
{x, true or false}: {4, false}
{x, true or false}: {5, false}
{x, true or false}: {6, false}
{x, true or false}: {7, true}
{x, true or false}: {4, false}
{x, true or false}: {5, false}
{x, true or false}: {6, false}
{x, true or false}: {7, true}
良い感じで判定できました．あとは，Enum.filterで，2番目がtrueのものだけ抜き出せば良いです．
main.exs
defmodule Main do
def main() do
[n, l, r] = read_int_list()
a = read_int_list()
a
|> Enum.map(fn a ->
l..r
|> Enum.map(fn x ->
b = Enum.reduce(l..r, true, fn y, acc ->
abs(x - a) <= abs(y - a) and acc
end)
{x, b}
end)
|> Enum.filter(fn {_, b} -> b end)
|> Enum.map(fn {x, _} -> x end)
end)
|> IO.inspect()
end
def read_int_list() do
IO.read(:line)
|> String.trim()
|> String.split(" ")
|> Enum.map(&String.to_integer/1)
end
end
% elixir test.exs < in1.txt
warning: variable "n" is unused (if the variable is not meant to be used, prefix it with an underscore)
main.exs:3: Main.main/0
[[4], [4], [4], ~c"\a", ~c"\a"]
結果が文字化けしてしまいましたので，最後のIO.inspect()をIO.inspect(charlists: :as_lists)とします．
main.exs
defmodule Main do
def main() do
[n, l, r] = read_int_list()
a = read_int_list()
a
|> Enum.map(fn a ->
l..r
|> Enum.map(fn x ->
b = Enum.reduce(l..r, true, fn y, acc ->
abs(x - a) <= abs(y - a) and acc
end)
{x, b}
end)
|> Enum.filter(fn {_, b} -> b end)
|> Enum.map(fn {x, _} -> x end)
end)
|> IO.inspect(charlists: :as_list)
end
def read_int_list() do
IO.read(:line)
|> String.trim()
|> String.split(" ")
|> Enum.map(&String.to_integer/1)
end
end
% elixir test.exs < in1.txt
warning: variable "n" is unused (if the variable is not meant to be used, prefix it with an underscore)
main.exs:3: Main.main/0
[[4], [4], [4], [7], [7]]
大体結果が出ましたね．あとは，リストが多重になっているので，List.flatten/1を使って平らにします．
main.exs
defmodule Main do
def main() do
[n, l, r] = read_int_list()
a = read_int_list()
a
|> Enum.map(fn a ->
l..r
|> Enum.map(fn x ->
b = Enum.reduce(l..r, true, fn y, acc ->
abs(x - a) <= abs(y - a) and acc
end)
{x, b}
end)
|> Enum.filter(fn {_, b} -> b end)
|> Enum.map(fn {x, _} -> x end)
end)
|> List.flatten()
|> IO.inspect(charlists: :as_list)
end
def read_int_list() do
IO.read(:line)
|> String.trim()
|> String.split(" ")
|> Enum.map(&String.to_integer/1)
end
end
% elixir test.exs < in1.txt
warning: variable "n" is unused (if the variable is not meant to be used, prefix it with an underscore)
main.exs:3: Main.main/0
[4, 4, 4, 7, 7]
これで，結果が出たので，Enum.joinとIO.putsに書き換えます．また，nは使わなかったので，_nとしておきます．
main.exs
defmodule Main do
def main() do
[_n, l, r] = read_int_list()
a = read_int_list()
a
|> Enum.map(fn a ->
l..r
|> Enum.map(fn x ->
b = Enum.reduce(l..r, true, fn y, acc ->
abs(x - a) <= abs(y - a) and acc
end)
{x, b}
end)
|> Enum.filter(fn {_, b} -> b end)
|> Enum.map(fn {x, _} -> x end)
end)
|> List.flatten()
|> Enum.join(" ")
|> IO.puts()
end
def read_int_list() do
IO.read(:line)
|> String.trim()
|> String.split(" ")
|> Enum.map(&String.to_integer/1)
end
end
makeコマンドを実行してみましょう．
% make
elixir test.exs < in1.txt | diff - out1.txt
elixir test.exs < in2.txt | diff - out2.txt
成功です．
ではAtCoderで提出してみましょう．
おやおや，TLE(実行時間制限超過)になってしまいました．答えそのものは合っていそうです．
AtCoderの楽しみ方として，一旦はここまででも良いのかと思います．しかし，できればTLE(実行時間制限超過)をクリアしたいですよね．
今回の方法だと，三重ループを使っているので，計算量で言うと$O(n^3)$となるので，いかにも遅そうです．実際，問題の制約条件を見てみると，$O(n^3)$のアルゴリズムでは到底AC(正解)は得られないものと考えられます．
次の記事では，まずアルゴリズム上の工夫をしてみたいと思います．