[AtCoder] ABC130A-D - 尺取り法 [Elixir Livebook]

## はじめに

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

https://atcoder.jp/contests/abc130/

なお、 E、F 問題はまだ自分には難しすぎるため、 D 問題までを解いています

## ABC130A - Rounding

### ABC130A 問題

https://atcoder.jp/contests/abc130/tasks/abc130_a

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc130/abc130_a

### ABC130A 入出力例

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

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

### ABC130A 回答

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

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

  defp split_words(words) do
    String.split(words, " ")
  end

  def solve(input) do
    input
    |> String.trim()
    |> split_words()
    |> Enum.map(&String.to_integer/1)
    |> judge()
  end

  defp judge([x, a]) when x < a, do: 0

  defp judge(_), do: 10
end
```

実行時間は 357 ms でした

## ABC130B - Bounding

### ABC130B 問題

https://atcoder.jp/contests/abc130/tasks/abc130_b

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc130/abc130_b

### ABC130B 入出力例

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

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

### ABC130B 回答1

配列にボールが跳ねる座標を格納していき、そのうち x 以下の座標の件数を取得しました

```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
    [[n, x], l] =
      input
      |> split_lines()
      |> Enum.map(fn str ->
        str
        |> split_words()
        |> Enum.map(&String.to_integer/1)
      end)

    0..(n - 1)
    |> Enum.reduce([0], fn d, acc ->
      acc ++ [l |> Enum.slice(0..d) |> Enum.sum()]
    end)
    |> Enum.count(&(&1 <= x))
  end
end
```

実行時間は 353 ms でした

### ABC130B 回答2

ボールが跳ねる座標のうち、 x 以下のものを抽出し、件数をカウントしました

最初の座標 0 の分、最後に足しています

```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
    [[n, x], l] =
      input
      |> split_lines()
      |> Enum.map(fn str ->
        str
        |> split_words()
        |> Enum.map(&String.to_integer/1)
      end)

    0..(n - 1)
    |> Stream.filter(fn d ->
      l
      |> Enum.slice(0..d)
      |> Enum.sum()
      |> Kernel.<=(x)
    end)
    |> Enum.count()
    |> Kernel.+(1)
  end
end
```

実行時間は 357 ms でした

## ABC130C - Rectangle Cutting

### ABC130C 問題

https://atcoder.jp/contests/abc130/tasks/abc130_c

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc130/abc130_c

### ABC130C 入出力例

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

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

### ABC130C 回答

この問題はかなりややこしく、場合分けをしながら試行錯誤してなんとか回答しました

まず、問題を単純化するため、指定された点 `{x, y}` を長方形の中心より左上になるよう座標変換します

これによって、分割されたとき左上にある領域が必ず小さい方の領域になります

- 二等分できるケース

  正方形になっている場合（ `w == h` ）、その中のどの点を指定されたとしても、その点と中心を通る直線で分割することで、必ず二等分になります

　　指定された点が原点の場合（　`{x, y} == {0, 0}`　）、ことのときはどんな長方形であろうと、対角線で分割することで必ず二等分になります

　　指定された点が対角線上にある場合（ `w / h == x / y` ）も同様です

　　これらのケースにおいて、指定された点自体が長方形の中心である場合（ `x == w / 2 && y == h / 2` ）、中心を通る線であればどのように分割しようと必ず二等分になるため、分割の仕方は複数あることになります

  それ以外の場合は必ず指定された点と中心を通る線でしか二等分できません

- 二等分できないケース

  上記以外のケースでは二等分できず、横に真っ直ぐ切るか、縦に真っ直ぐ切るかしたうちの、どちらか大きく切れる方が最大になります

  横に真っ直ぐ切ったときと縦に真っ直ぐ切ったときの面積が同じ場合のみ、複数の分割方法があることになります


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

  defp split_words(words) do
    String.split(words, " ")
  end

  def solve(input) do
    [w, h, x, y] =
      input
      |> String.trim()
      |> split_words()
      |> Enum.map(&String.to_integer/1)

    x = if x > w / 2, do: w - x, else: x
    y = if y > h / 2, do: h - y, else: y

    asp_rec = w / h
    asp_point = if y == 0, do: 0, else: x / y

    {area, eq} =
      cond do
        w == h || {x, y} == {0, 0} || asp_rec == asp_point ->
          {
            w * h / 2,
            if(x == w / 2 && y == h / 2, do: 1, else: 0)
          }

        true ->
          {
            [x * h / 1, y * w / 1] |> Enum.max(),
            if(x * h == y * w, do: 1, else: 0)
          }
      end

    "#{:erlang.float_to_binary(area, decimals: 6)} #{eq}"
  end
end
```

実行結果は 345 ms でした

## ABC130D - Enough Array

### ABC130D 問題

https://atcoder.jp/contests/abc130/tasks/abc130_d

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

https://github.com/RyoWakabayashi/elixir-learning/tree/main/livebooks/atcoder/abc130/abc130_d

### ABC130D 入出力例

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

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

```elixir
"""
10 53462
103 35322 232 342 21099 90000 18843 9010 35221 19352
"""
|> Main.solve()
|> then(&(&1 == 36))
```

### ABC130D 制限時間を超過した回答

ここまでは自力で実装できました

左から順に部分配列を作り、合計が k 未満の組み合わせ数 false_combinations を求めます

全組み合わせから false_combinations を引いて答えを出します

ただし、この実装だと計算量が $O(N^2)$ になるため、 N が大きくなると制限時間を超えてしまいます

```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, k], a] =
      input
      |> split_lines()
      |> Enum.map(fn line ->
        line
        |> split_words()
        |> Enum.map(&String.to_integer/1)
      end)

    a
    |> Enum.with_index()
    |> Enum.map(fn {a_i, i} -> {i, a_i} end)
    |> renew_table(:a)

    renew_table([], :sum)
    renew_table([], :false_combination)

    false_combinations =
      for i <- 0..(n - 1),
          j <- i..(n - 1),
          a_j = lookup(:a, j),
          pre_sum = lookup(:sum, {i, j - 1}),
          sum = pre_sum + a_j,
          :ets.insert(:sum, {{i, j}, sum}),
          sum < k do
        1
      end
      |> length()

    all_combination = div(n * (n + 1), 2)

    all_combination - false_combinations
  end
end
```

### ABC130D 回答

公式の解説を参考に、尺取り法で実装しました

https://img.atcoder.jp/abc130/editorial.pdf

まず、部分配列の左端（添字 i）を固定して右端（添字 j）をどんどん伸ばしていきます

部分配列の合計値が k 以上になった時点で、それ以降右端を伸ばした場合も全て合計値が k を超えるため、左端 i のとき、 `n - j` 個の組み合わせがあることになります

次に右端を固定（ pre_head_j に k 以上になった時点の i をバインドしておく）して、左端を右に近づけていきます

だんだん部分配列が短く、合計値が小さくなりますが、 k より小さくなるまではずっと `n - pre_head_j` 個の組み合わせが加算されます

合計値が k より小さくなったら、また右端を動かして部分配列を伸ばします

このように、部分配列を伸ばしたり縮めたりしながら移動するため、正に尺取の動きを模しているようです

最後に部分配列の右端が全体配列の右端に到達し、かつ部分配列の合計が k 未満になった場合、これ以上は増えなくなるため、計算を終了します

ものすごく苦労しながら `Enum.reduce_while` を使ったものの、あまり綺麗とは言えないですね

```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, k], a] =
      input
      |> split_lines()
      |> Enum.map(fn line ->
        line
        |> split_words()
        |> Enum.map(&String.to_integer/1)
      end)

    a
    |> Enum.with_index()
    |> Enum.map(fn {a_i, i} -> {i, a_i} end)
    |> renew_table(:a)

    {combination_sum, _, _} =
      0..(n - 1)
      |> Enum.reduce_while({0, 0, -1}, fn i, {combination, acc_i, pre_head_j} ->
        # i: 部分配列の左端
        # acc_i: 部分配列の合計
        # pre_head_j: 部分配列の右端
        cond do
          acc_i < k && pre_head_j == n - 1 ->
            # 最後まで計算して、もう合計が k 以上になることがない場合、終了する
            {:halt, {combination, 0, 0}}

          acc_i < k ->
            # k 以上になるまで部分配列の右端をずらす
            # i から pre_head_j までの部分配列の合計は acc_i に入っているので、それより後だけ計算する
            init_j = pre_head_j + 1

            {head_j, sum_j, new_combination} =
              init_j..(n - 1)
              |> Enum.reduce_while({init_j, acc_i, 0}, fn j, {_, acc_j, _} ->
                sum_j = acc_j + lookup(:a, j)

                if sum_j < k do
                  {:cont, {j, sum_j, 0}}
                else
                  # k 以上になったとき、 i から j 以降の合計は全て k 以上になる
                  {:halt, {j, sum_j, n - j}}
                end
              end)

            new_head_j = if head_j > pre_head_j, do: head_j, else: pre_head_j
            {:cont, {combination + new_combination, sum_j - lookup(:a, i), new_head_j}}

          true ->
            # k 以下になるまで部分配列の左端をずらす
            # k 以下になるまで、 i から pre_head_j 以降の合計は全て k 以上になる
            new_combination = n - pre_head_j
            {:cont, {combination + new_combination, acc_i - lookup(:a, i), pre_head_j}}
        end
      end)

    combination_sum
  end
end
```

実行時間は 560 ms でした

## まとめ

尺取り法をなんとか実装できましたが、釈然とはしないですね