AtCoder ABC081B、ABC051B、ABC045CをElixirで解く

はじめに

• Elixir 楽しんでいますか
• AtCoder ABC081B、ABC051B、ABC045CをElixirで解いてみます

What is AtCoder?

• 世界最高峰の競技プログラミングサイトです
• だいたい毎週土曜や日曜の21時すぎにコンテストが行われているようです
• 出題された問題の答えを出力するプログラムを書いて提出することで自動的に採点されます
• 実行時間が長かったり、メモリの使用量が多いとパスできません
• 競技プログラミングというもの自体に私は馴染みがなかったのですが、最近はじめました

はじめての方は

• ElixirでAtCoderにはじめて取り組まれる方は、手前味噌ですが、「AtCoderをElixirでやってみる」をご参照ください
  • インプットの読み取り方などのTipsを書いています
• Elixir自体がはじめての方はまずインストールしましょう
  • 手前味噌ですがインストールなどをご参照ください

便利なツール

• tamanugi/ex_at_coder
  • @tamanugiさん作
  • AtCoder用のmixタスクを作ってみた
  • @tamanugiさんのex_at_coderを使ってみる (Elixir)
  • 本日はこちらを使います
• g-kenkun/kyopuro
  • @g_kenkunさん作
  • @g_kenkunさんのg-kenkun/kyopuroを使ってみる (Elixir)

プロジェクト作成

$ mkdir awesome_at_coder
$ cd awesome_at_coder
$ asdf local elixir 1.10.2-otp-22
$ mix new .

mix.exs

  defp deps do
    [
      # {:dep_from_hexpm, "~> 0.3.0"},
      # {:dep_from_git, git: "https://github.com/elixir-lang/my_dep.git", tag: "0.1.0"}
      {:ex_at_coder, ">0.0.0"}
    ]
  end

$ mix deps.get

ABC081B

$ mix atcoder.open abc081 b

• 問題文のページがブラウザで開かれます
• 問題をご確認ください

$ mix atcoder.new abc081

• 問題文のページからテストケースや回答モジュールの雛形が作られます

ソースコードを書く

• 自分を信じてがんばって解きましょう

lib/abc081/b.ex

defmodule Abc081.B.Main do
  use Bitwise

  def main() do
    IO.read(:line)
    list = IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)

    0..1_000_000_000
    |> Enum.reduce_while({0, list}, fn _, {acc_cnt, acc_list} ->
      case has_odd?(acc_list) do
        true -> {:halt, {acc_cnt, acc_list}}
        false -> {:cont, {acc_cnt + 1, do_something(acc_list)}}
      end
    end)
    |> elem(0)
    |> IO.puts()
  end

  defp has_odd?(list) do
    Enum.any?(list, &((&1 &&& 1) == 1))
  end

  defp do_something(list) do
    Enum.map(list, &(&1 >>> 1))
  end
end

テストする

$ mix atcoder.test abc081 b
abc081 b
running 3 test...
-------------------------------------
sample1  AC  1ms
actual:
2
expected:
2
-------------------------------------
sample2  AC  0ms
actual:
0
expected:
0
-------------------------------------
sample3  AC  0ms
actual:
8
expected:
8

自信をもって提出しましょう。
提出の際にはモジュール名をMainにして提出します。

---

ABC051B

$ mix atcoder.open abc051 b

• 問題文のページがブラウザで開かれます
• 問題をご確認ください

$ mix atcoder.new abc051

• 問題文のページからテストケースや回答モジュールの雛形が作られます

ソースコードを書く

• 自分を信じてがんばって解きましょう

lib/abc051/b.ex

defmodule Abc051.B.Main do
  def main() do
    [k, s] =
      IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)

    # for(x <- 0..k, y <- 0..k, z = s - x - y, z >= 0, z <= k, do: 1)
    # |> Enum.sum()
    # |> IO.puts()

    0..k
    |> Enum.reduce(0, fn x, acc ->
      Enum.filter(0..k, fn y ->
        z = s - x - y
        z >= 0 && z <= k
      end)
      |> Enum.count()
      |> Kernel.+(acc)
    end)
    |> IO.puts()
  end
end

• for/1を使って書くと短くかけますが、MLE(Memory Limit Exceeded)になっちゃったのでパスするように書きかえました

テストする

$ mix atcoder.test abc051 b
abc051 b
running 2 test...
-------------------------------------
sample1  AC  0ms
actual:
6
expected:
6
-------------------------------------
sample2  AC  0ms
actual:
1
expected:
1

自信をもって提出しましょう。
提出の際にはモジュール名をMainにして提出します。

---

ABC045C

$ mix atcoder.open abc045 c

• 問題文のページがブラウザで開かれます
• 問題をご確認ください

$ mix atcoder.new abc045

• 問題文のページからテストケースや回答モジュールの雛形が作られます

ソースコードを書く

• 自分を信じてがんばって解きましょう

lib/abc045/c.ex

defmodule Abc045.C.Main do
  use Bitwise

  def main() do
    s = IO.read(:line) |> String.trim() |> String.to_integer()
    digits = Integer.digits(s)
    length = Enum.count(digits)

    1..pow(2, length - 1)
    |> Enum.map(fn bit ->
      0..(length - 2)
      |> Enum.reduce([], fn i, acc ->
        case bit &&& 1 <<< i do
          0 -> ["" | acc]
          _ -> ["+" | acc]
        end
      end)
    end)
    |> Enum.map(fn pluses ->
      Enum.with_index(pluses)
      |> Enum.reduce(Enum.intersperse(digits, ""), fn {plus, i}, acc ->
        List.update_at(acc, 2 * i + 1, fn _ -> plus end)
      end)
    end)
    |> Enum.map(&Enum.join/1)
    |> Enum.map(&Code.eval_string/1)
    |> Enum.map(&elem(&1, 0))
    |> Enum.sum()
    |> IO.puts()
  end

  def pow(x, y), do: pow(x, y, 1)

  defp pow(_x, 0, acc), do: acc

  defp pow(x, y, acc), do: pow(x, y - 1, x * acc)
end

テストする

$ mix atcoder.test abc045 c
abc045 c
running 2 test...
-------------------------------------
sample1  AC  0ms
actual:
176
expected:
176
-------------------------------------
sample2  AC  24ms
actual:
12656242944
expected:
12656242944

自信をもって提出しましょう。
提出の際にはモジュール名をMainにして提出します。

Wrapping Up 🎍🎍🎍🎍🎍

• 私は、めちゃくちゃ時間かけて解いています
• 問題は問題解決力を鍛える!アルゴリズムとデータ構造 第3章の章末問題に挙げられていたものをチョイスしました
• Enjoy Elixir