LoginSignup
10
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

お題は不問！Qiita Engineer Festa 2023で記事投稿！
@RyoWakabayashi(若林 諒)in株式会社オーイーシー

[AtCoder] ABC044 - 複数キーの ETS [Elixir Livebook]

Last updated at Posted at 2023-07-10

はじめに

AtCoder の Beginners Selection コンテスト ABC044 問題を Elixir Livebook で回答しました

ABC044A - 高橋君とホテルイージー

ABC044A 問題

ABC044A 実装したノートブック

ABC044A 入出力例

"""
5
3
10000
9000
"""
|> Main.solve()
|> then(&(&1 == 48000))

"""
2
3
10000
9000
"""
|> Main.solve()
|> then(&(&1 == 20000))

ABC044A 回答

単純に問題文のままを実装しました

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

  def solve(input) do
    [n, k, x, y] =
      input
      |> split_lines()
      |> Enum.map(&String.to_integer/1)

    cond do
      n <= k -> n * x
      true -> k * x + (n - k) * y
    end
  end
end

実行時間は 341 ms でした

ABC044B - 美しい文字列

ABC044B 問題

ABC044B 実装したノートブック

ABC044B 入出力例

"""
abaccaba
"""
|> Main.solve()
|> then(&(&1 == "Yes"))

"""
hthth
"""
|> Main.solve()
|> then(&(&1 == "No"))

ABC044B 回答

String.codepoints で文字の配列にして、 Enum.group_by で文字毎にグループ分けしました

一つでも文字毎の数が奇数であれば（ Enum.find　の結果が nil でなければ） "No"

全ての文字毎の数が偶数であれば "Yes" を表示します

defmodule Main do
  def main do
    :stdio
    |> IO.read(:all)
    |> solve()
    |> IO.puts()
  end

  def solve(input) do
    input
    |> String.trim()
    |> String.codepoints()
    |> Enum.group_by(& &1)
    |> Enum.find(fn {_, value} -> value |> length() |> rem(2) == 1 end)
    |> case do
      nil -> "Yes"
      _ -> "No"
    end
  end
end

実行時間は 511 ms でした

ABC044C - 高橋君とカード

ABC044C 問題

ABC044C 実装したノートブック

ABC044C 入出力例

"""
4 8
7 9 8 9
"""
|> Main.solve()
|> then(&(&1 == 5))

"""
3 8
6 6 9
"""
|> Main.solve()
|> then(&(&1 == 0))

"""
8 5
3 6 2 8 7 6 5 9
"""
|> Main.solve()
|> then(&(&1 == 19))

"""
33 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
"""
|> Main.solve()
|> then(&(&1 == 8_589_934_591))

ABC044C 回答

今回は C 問題から躓きました

以下の記事を参考に、というかそのまま Elixir に翻訳したくらいの形でクリアしました

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

  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
      _ -> 0
    end
  end

  def solve(input) do
    [[n, a], x] =
      input
      |> split_lines()
      |> Enum.map(fn line ->
        line
        |> split_words()
        |> Enum.map(&String.to_integer/1)
      end)

    x
    |> Enum.with_index()
    |> Enum.map(fn {char, index} -> {index, char} end)
    |> renew_table(:x)

    renew_table({{0, 0, 0}, 1}, :dp)

    for i <- 0..(n - 1),
        k <- 0..n,
        s <- 0..(n * a - 1),
        p = lookup(:dp, {i, k, s}),
        p > 0 do
      x_i = lookup(:x, i)
      p_1_key = {i + 1, k, s}
      p_2_key = {i + 1, k + 1, s + x_i}
      p_1 = lookup(:dp, p_1_key)
      p_2 = lookup(:dp, p_2_key)

      :ets.insert(:dp, {p_1_key, p_1 + p})
      :ets.insert(:dp, {p_2_key, p_2 + p})
    end

    1..n
    |> Enum.reduce(0, fn k, acc ->
      acc + lookup(:dp, {n, k, a * k})
    end)
  end
end

先頭から i 個目までの数字から k 個の数字を選んだとき、合計が s になる組み合わせの数、を ETS に :dp テーブルで入れていきます

i, k, s という３つのキーを使うため、 ETS のキーは {i, k, s} のタプルにしました

上記の説明が非常に分かりにくい（私自身もなかなか理解できなかった）で、入出力例1の実行後の :dp テーブルの中身を見てみます

:dp
|> :ets.tab2list()
|> Enum.sort_by(&(&1 |> elem(0)))

入力が 7 9 8 9 のとき、 :dp テーブルの中身は以下のようになります

[
  {{0, 0, 0}, 1},
  {{1, 0, 0}, 1},
  {{1, 1, 7}, 1},
  {{2, 0, 0}, 1},
  {{2, 1, 7}, 1},
  {{2, 1, 9}, 1},
  {{2, 2, 16}, 1},
  {{3, 0, 0}, 1},
  {{3, 1, 7}, 1},
  {{3, 1, 8}, 1},
  {{3, 1, 9}, 1},
  {{3, 2, 15}, 1},
  {{3, 2, 16}, 1},
  {{3, 2, 17}, 1},
  {{3, 3, 24}, 1},
  {{4, 0, 0}, 1},
  {{4, 1, 7}, 1},
  {{4, 1, 8}, 1},
  {{4, 1, 9}, 2},
  {{4, 2, 15}, 1},
  {{4, 2, 16}, 2},
  {{4, 2, 17}, 2},
  {{4, 2, 18}, 1},
  {{4, 3, 24}, 2},
  {{4, 3, 25}, 1},
  {{4, 3, 26}, 1},
  {{4, 4, 33}, 1}
]

  • 数字が 0 個のとき、合計は 0 になる組み合わせが 1 個です

  • 数字が 1 個（7だけ）のとき

    • 0 個の数字を選んだ場合、合計は 0 になる組み合わせが 1 個です
    • 1 個の数字を選んだ場合、合計は 7 になる組み合わせが 1 個です

  • 数字が 2 個（7と9）のとき

    • 0 個の数字を選んだ場合、合計は 0 になる組み合わせが 1 個です
    • 1 個の数字を選んだ場合
      　　- 合計が 7 になる組み合わせが 1 個です
      　　- 合計が 9 になる組み合わせが 1 個です
    • 2 個の数字を選んだ場合、合計は 16 (7+9) になる組み合わせが 1 個です

  • 数字が 3 個（7と9と8）のとき

    • 0 個の数字を選んだ場合、合計は 0 になる組み合わせが 1 個です
    • 1 個の数字を選んだ場合
      　　- 合計が 7 になる組み合わせが 1 個です
      　　- 合計が 9 になる組み合わせが 1 個です
      　　- 合計が 8 になる組み合わせが 1 個です
    • 2 個の数字を選んだ場合
      • 合計が 15 (7+8) になる組み合わせが 1 個です
      • 合計が 16 (7+9) になる組み合わせが 1 個です
      • 合計が 17 (8+9) になる組み合わせが 1 個です
    • 3 個の数字を選んだ場合、合計は 24 (7+8+9) になる組み合わせが 1 個です

...

というように、全部の組み合わせの数が :dpテーブルに入ります

あとは平均が a なので、 k この場合、合計が a * k と等しい組み合わせの数を合計すれば答えが出ます

実行結果は 1755 ms でした

ABC044D - 桁和

正直、この問題に関しては完全には理解できていません

以下の方の Python 実装を Elixir 　に翻訳しただけですね、、、

ABC044D 問題

ABC044D 実装したノートブック

ABC044D 入出力例

"""
87654
30
"""
|> Main.solve()
|> then(&(&1 == 10))

"""
87654
138
"""
|> Main.solve()
|> then(&(&1 == 100))

"""
87654
45678
"""
|> Main.solve()
|> then(&(&1 == -1))

"""
31415926535
1
"""
|> Main.solve()
|> then(&(&1 == 31_415_926_535))

"""
1
31415926535
"""
|> Main.solve()
|> then(&(&1 == -1))

ABC044D 回答

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 digsum(b, n) when n < b, do: n

  defp digsum(b, n), do: rem(n, b) + digsum(b, div(n, b))

  def solve(input) do
    [n, s] =
      input
      |> split_lines()
      |> Enum.map(&String.to_integer/1)

    cond do
      n == s ->
        n + 1

      n < s ->
        -1

      true ->
        {small, big} =
          for i <- 1..(:math.sqrt(n - s) |> ceil() |> Kernel.+(1)),
              rem(n - s, i) == 0 do
            {i, div(n - s, i)}
          end
          |> Enum.reduce({[], []}, fn {small_i, big_i}, {small_acc, big_acc} ->
            {[small_i | small_acc], [big_i | big_acc]}
          end)

        [Enum.reverse(small), big]
        |> List.flatten()
        |> Enum.find(-2, &(digsum(&1 + 1, n) == s))
        |> Kernel.+(1)
    end
  end
end

唯一工夫した点としては、２つの配列を reduce で作ったところくらいでしょうか

元の Python 実装は以下のようになっていました

    small = []
    big = []
    for i in range(1, math.ceil(math.sqrt(a)) + 1):
        if a % i == 0:
            small.append(i)
            big.append(a // i)
    return small + big[::-1]

Elixir だと以下のようになります

        {small, big} =
          for i <- 1..(:math.sqrt(n - s) |> ceil() |> Kernel.+(1)),
              rem(n - s, i) == 0 do
            {i, div(n - s, i)}
          end
          |> Enum.reduce({[], []}, fn {small_i, big_i}, {small_acc, big_acc} ->
            {[small_i | small_acc], [big_i | big_acc]}
          end)

        [Enum.reverse(small), big]
        |> List.flatten()

Enum.reduce でアキュムレーターを　{[], []} のように配列のタプルにすることで、それぞれに対して追加しています

実行時間は 342 ms でした

まとめ

かなり難しかったです

x[i][j][k] = value みたいなことが ETS で　{{i, j, k}, value} として実装できたのは良かったです

10
0
0

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
10
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?