LoginSignup
7
0
ElixirAdvent Calendar 2023Day 6
@zacky1972(山崎 進)infukuoka.ex：福岡Elixirコミュ

試行錯誤編: B - Minimize Abs 1 を Elixir で解いた〜トヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330)

Last updated at Posted at 2023-12-22

トヨタシステムズプログラミングコンテスト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(正解)は得られないものと考えられます．

次の記事では，まずアルゴリズム上の工夫をしてみたいと思います．

7
0
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
7
0