【Ruby基礎】AtCoder Beginner Contest 014 B – 価格の合計

  • by

■はじめに

Rubyの基礎的な問題をたくさん解くことで基本的な考え方やメソッドの使い方を定着させたい。
基本的にはAtCoderというプログラミングコンテスト(競技プログラミング)の過去問を使う。(AtCoderは難易度が分かれており、難易度の低いA問題かB問題を解いていく)

■問題

●出典

AtCoder Beginner Contest 014のB問題
https://atcoder.jp/contests/abc014/tasks/abc014_2

●問題文

今回は数式をうまく書けないのでスクショで…。

●入力

こちらもスクショ。

●出力

部分集合に含まれる商品の価格を合計したものを 1 行に出力せよ.出力の末尾に改行をいれること.

■回答

●愚直に書く

今回やけに難しい…。綺麗かどうかはわからないけど思いついた方法で愚直に書いてみる。
まずは標準入力の1行目と2行目を取る。それぞれの行で配列にするか…。

ary = gets.split.map(&:to_i)
nums = gets.split.map(&:to_i)

p 出力で一旦確認、取れた。

続いて、最終的な数字を足し合わせる際の条件になる「ビットが立っているか」の確認。
1行目の2つ目の数字を2進数にして1つ目の数字分の桁数にする。

binary = ary[1].to_s(2).rjust(ary[0], '0').reverse.split('').map(&:to_i)

余計な構造になっていないか心配だけど、

  • ary[1]「1行目の数字の2番目の数字を」
  • .to_s(2)「to_sで2進数にして」
  • .rjust(ary[0], '0')「rjustメソッドで1行目の1番目の桁数までゼロ埋めして」
  • .reverse「問題文と整合性を取るためにreverseして」
  • .split('').map(&:to_i)「それを配列にする」

ということをやっている。

ここまできて準備ができた。
もし入力が下記の場合に、

4 5
1 10 100 1000

下記のように結果が出るようになった。

[1, 0, 1, 0]
[1, 10, 100, 1000]

上記の2つの配列を二重配列にまとめて、「二重配列内のそれぞれの配列において、1つ目の要素が1なら2つ目の要素を残しておいて、1つ目の要素が0なら2つ目の要素を消す」という処理を行って最後にsumで合計すれば求める結果になるはず…。

# まず二重配列を作る
nums_arys = binary.zip(nums)
# 最終的な計算式を作る
ans = nums_arys.map do |nums_ary|
  if nums_ary[0] == 1
    nums_ary[1]
  else
    0
  end
end

ということで出来上がったのが下記。

ary = gets.split.map(&:to_i)
nums = gets.split.map(&:to_i)

binary = ary[1].to_s(2).rjust(ary[0], '0').reverse.split('').map(&:to_i)
nums_arys = binary.zip(nums)
ans = nums_arys.map do |nums_ary|
  if nums_ary[0] == 1
    nums_ary[1]
  else
    0
  end
end

p ans.sum

通った!!!

●リファクタリング/別アプローチ

例の如く三項演算子にする。

ary = gets.split.map(&:to_i)
nums = gets.split.map(&:to_i)

binary = ary[1].to_s(2).rjust(ary[0], '0').reverse.split('').map(&:to_i)
nums_arys = binary.zip(nums)
ans = nums_arys.map do |nums_ary|
  nums_ary[0] == 1 ? nums_ary[1] : 0
end

p ans.sum

他の方法もありそうだけどギブアップ…。

●他の方の回答例

ちゃんと理解しきれていないけど、少なくとも1行目は2つまとめた配列ではなくて n, x = gets.split.map(&:to_i)くらいで取得する方がシンプルそう。

n, x = gets.split.map(&:to_i)
nums = gets.split.map(&:to_i)

binary = x.to_s(2).rjust(n, '0').reverse.split('').map(&:to_i)
nums_arys = binary.zip(nums)
ans = nums_arys.map do |nums_ary|
  nums_ary[0] == 1 ? nums_ary[1] : 0
end

p ans.sum

●出てきたメソッド等

公式リファレンスを見る訓練。

■振り返りなど

難易度がだいぶ上がったような気がする汗。
かなり時間を取られてしまったので、これだと数日かけてやるくらいが良いかもしれないし、自分の書いたコードを誰かにレビューしてほしくなる。(独力でそれに近い学習効果を得るために、他の人の回答を見て学ぶという今の方法でトライしているのだけど。自分の回答を解析してリファクタリングを提案してくれたり「あなたのこの回答なら、この人の回答が参考になるよ」と教えてくれるサービスが欲しい…!)