[AtCoder] ABC043 - 正規表現による連続する文字の抽出 [Elixir Livebook]

## はじめに

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

https://atcoder.jp/contests/abc043/

## ABC043A - キャンディーとN人の子供イージー

### ABC043A 問題

https://atcoder.jp/contests/abc043/tasks/abc043_a

### ABC043A 実装したノートブック

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc043/abc043_a

### ABC043A 入出力例

```elixir
"""
3
"""
|> Main.solve()
|> then(&(&1 == 6))
```

```elixir
"""
10
"""
|> Main.solve()
|> then(&(&1 == 55))
```

```elixir
"""
1
"""
|> Main.solve()
|> then(&(&1 == 1))
```

### ABC043A 回答1

単純にnまでの総和です

```elixir
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

全てパイプで繋いだバージョンです

```elixir
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 問題

https://atcoder.jp/contests/abc043/tasks/abc043_b

### ABC043B 実装したノートブック

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc043/abc043_b

### ABC043B 入出力例

```elixir
"""
01B0
"""
|> Main.solve()
|> then(&(&1 == "00"))
```

```elixir
"""
0BB1
"""
|> Main.solve()
|> then(&(&1 == "1"))
```

```elixir
"""
1
"""
|> Main.solve()
|> then(&(&1 == 1))
```

### ABC043B 回答

各キーの入力を `Enum.reduce` で順次実行しています

ただし、末尾に加えるよりも先頭に加える方が楽なので、右方向ではなく左方向に処理してから、最後に反転させます

また、空になった状態で更に消すことはできないので、その場合は空を返しています

```elixir
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 問題

https://atcoder.jp/contests/abc043/tasks/arc059_a

### ABC043C 実装したノートブック

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc043/abc043_c

### ABC043C 入出力例

```elixir
"""
2
4 8
"""
|> Main.solve()
|> then(&(&1 == 8))
```

```elixir
"""
3
1 1 3
"""
|> Main.solve()
|> then(&(&1 == 3))
```

```elixir
"""
3
4 2 5
"""
|> Main.solve()
|> then(&(&1 == 5))
```

```elixir
"""
4
-100 -100 -100 -100
"""
|> Main.solve()
|> then(&(&1 == 0))
```

### ABC043C 回答1

C 問題までなら何も引っかからずにスイスイ解けますね

この問題は整数で分散を計算せよ、ということなので、その通りに実装しています

`:math.pow` は結果が Float になるので、最後に `floor` で整数にしています

```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

  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 - アンバランス

この問題は自力では部分点までしかもらえませんでした

入力が短い間は愚直に問題文通りの実装をしていれば良いのですが、入力が長くなるとそれでは制限時間を超えます

こちらの記事を参考に解きました

https://drken1215.hatenablog.com/entry/2020/10/29/133500

### ABC043D 問題

https://atcoder.jp/contests/abc043/tasks/arc059_b

### ABC043D 実装したノートブック

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc043/abc043_d

### ABC043D 入出力例

```elixir
"""
needed
"""
|> Main.solve()
|> then(&(&1 == "2 3"))
```

```elixir
"""
atcoder
"""
|> Main.solve()
|> then(&(&1 == "-1 -1"))
```

### ABC043D 制限時間超過 回答

愚直に問題文通りの処理を実装したパターンです

これでは計算量が多いので、入力が長いと TLE になってしまいます

```elixir
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

[参考にした記事](https://drken1215.hatenablog.com/entry/2020/10/29/133500)にある通り、アンバランスな部分文字列を含んでいる = 以下の条件を満たす文字列を含んでいる、ということです

- `aa` のように同じ文字が連続している
- `axa` のように、同じ文字の間に1文字別の文字が挟まっている

`axya` のように2文字以上別の文字を挟んだ場合、同じ文字が過半数を超えません

また、 `axyazba` というように、2文字以上別の文字を挟んだものを繰り返しても決して過半数を超えることはありません

従って、入力の中で、同じ文字の間に挟まれる別の文字が 0 〜 1 文字になっている部分文字列を探せば良いことになります

リストへの参照だと非常に遅く、 TLE になってしまうため、各文字を ETS に格納してから参照するようにしました

```elixir
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

もっとシンプルに、正規表現でこの条件に該当するものを検索してみました

正規表現については以下の記事を参考にしました

https://www-creators.com/archives/2616

後方参照 `\1`　を使うことで、前に一致した文字列と同じ文字列がある、という正規表現を書けます

`(.).?\1` とすると、何かの文字があり、 0 〜 1 文字の何らかの別文字を挟んで、最初と同じ文字がある、という意味になります

Elixir では `Regex.run` で正規表現による部分文字列の抽出ができます

また、オプションに `return: :index` を指定することで、文字列そのものではなく、文字列の位置（開始位置と長さ）を取得できます

https://hexdocs.pm/elixir/1.12/Regex.html

正規表現を使うことですごくシンプルになりました

```elixir
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 でした

## まとめ

正規表現は偉大ですね