paiza Sランク問題「mod7占い」を Elixir で解いてみた

はじめに

paiza S ランク問題を Elixir で解いてみます

mod7占い

与えられた数値から３つ選択したとき、総計が７で割り切れる組み合わせの数を取得します

defmodule Paiza do
  def main do
    [_n | a] =
      :stdio
      |> IO.read(:all)
      |> String.trim()
      |> String.split("\n")

    # 各数を 7 で割った余りを計算し、数値ごとに何個あるのか取得する 
    f =
      a
      |> Enum.map(fn a_k ->
        a_k
        |> String.to_integer()
        |> rem(7)
      end)
      |> Enum.frequencies()

    # 合計が 7 の倍数になる全ての組み合わせを計算する
    [
      conbination(Map.get(f, 0), 3),
      Enum.product([Map.get(f, 0, 0), Map.get(f, 1, 0), Map.get(f, 6, 0)]),
      Enum.product([Map.get(f, 0, 0), Map.get(f, 2, 0), Map.get(f, 5, 0)]),
      Enum.product([Map.get(f, 0, 0), Map.get(f, 3, 0), Map.get(f, 4, 0)]),
      Enum.product([conbination(Map.get(f, 1, 0), 2), Map.get(f, 5, 0)]),
      Enum.product([Map.get(f, 1, 0), Map.get(f, 2, 0), Map.get(f, 4, 0)]),
      Enum.product([Map.get(f, 1, 0), conbination(Map.get(f, 3, 0), 2)]),
      Enum.product([conbination(Map.get(f, 2, 0), 2), Map.get(f, 3, 0)]),
      Enum.product([Map.get(f, 2, 0), conbination(Map.get(f, 6, 0), 2)]),
      Enum.product([Map.get(f, 3, 0), Map.get(f, 5, 0), Map.get(f, 6, 0)]),
      Enum.product([conbination(Map.get(f, 4, 0), 2), Map.get(f, 6, 0)]),
      Enum.product([Map.get(f, 4, 0), conbination(Map.get(f, 5, 0), 2)]),
    ]
    |> Enum.sum()
    |> IO.puts()
  end

  # 階乗
  defp factorial(0), do: 1
  defp factorial(n), do: n * factorial(n - 1)

  # 組み合わせの数
  defp conbination(n, r) when r > n, do: 0
  defp conbination(n, r) do
    div(factorial(n), factorial(r) * factorial(n - r))
  end
end

Paiza.main()

解説

考えたいのは「７ で割り切れるかどうか」なので 7 より大きい数は全て 7 で割った余りと同じ意味になります

入力値は全て 0 〜 6 のいずれかになるので、 0 〜 6 までの数値を３つ選択したときに 7 の倍数になる組み合わせを全て計算すれば良いことになります

以下のようにして、合計が ７ になる全てのパターンを取得できます

for a_1 <- 0..6,
    a_2 <- 0..6,
    a_3 <- 0..6,
    a_1 <= a_2,
    a_2 <= a_3,
    Enum.sum([a_1, a_2, a_3]) |> rem(7) == 0 do
  {a_1, a_2, a_3}
end

実行結果は以下のとおりです

[
  {0, 0, 0},
  {0, 1, 6},
  {0, 2, 5},
  {0, 3, 4},
  {1, 1, 5},
  {1, 2, 4},
  {1, 3, 3},
  {2, 2, 3},
  {2, 6, 6},
  {3, 5, 6},
  {4, 4, 6},
  {4, 5, 5}
]

12 パターンしかないので、それぞれ個別に計算してしまいましょう

例えば 0 が 3 個、 2 が 2 個、 5 が 4 個あったとき、 以下のように計算できます

• {0, 0, 0} のパターンは 0 が3個なので 1 通りだけ作れる
• {0, 2, 5} のパターンは 3 * 2 * 4 = 24 通り作れる
• 他のパターンは作れない
• 全ての組み合わせは 1 + 24 = 25

0 が 5 個ある場合、 5 個から 3 個を選ぶ組み合わせの数なので、以下の数式で計算できます

${}_n \mathrm{C}_r = \frac{n!}{r!(n-r)!}$

つまり

${}_5 \mathrm{C}_3 = \frac{5!}{3!2!} = 5 \times 4 / 2 = 10$

2 が 4 個、 3 が 2 個の場合、 {2, 2, 3} のパターンを作ることができます

2 を 4 個中 2 個選択肢、それぞれに 3 が 2 個組み合わせられるため、

${}_4 \mathrm{C}_2 \times 2 = \frac{4!}{2!2!} \times 2 = 4 \times 3 = 12$

このような計算を全てのパターンで計算して合計すれば OK です

まとめ

S ランクですが、数学の問題だったので解けました

時間制限に引っかかるタイプと比べると楽ですね