B - Trick or Treat（ABC166復習）

AtCoder

5月3日に開催されたAtCoder Beginner Contest 166にRubyで参加しました。

今日はB問題の復習です。

各問題の制約や入力・出力例はリンク先（AtCoderのサイト）をご覧ください。

B - Trick or Treat

問題文
ある街に、N 人のすぬけ君(すぬけ君 1 、すぬけ君 2 、 ...、 すぬけ君 N )が住んでいます。
この街には、 K 種類のお菓子(お菓子 1 、 お菓子 2 、....、お菓子 K )が売られています。お菓子 i を持っているのは、すぬけ君 Ai,1,Ai,2,⋯,Ai,di の計di 人です。
高橋君は今からこの街を回り、お菓子を 1 つも持っていないすぬけ君にいたずらをします。このとき、何人のすぬけ君がいたずらを受けるでしょうか。

入力
入力は以下の形式で標準入力から与えられる。
N K
d1
A1,1 ... A1,d1
:
dK
AK,1 ... AK,dK

B - Trick or Treat

提出したコード

n, k = gets.split.map(&:to_i)
ary = Array.new
(1..k).each.with_index(1) do |x, i|
  d = gets.to_i
  line = gets.split.map(&:to_i)
  ary = ary.push(*line)
end
puts n - ary.uniq.size

結果：AC（正解） 実行時間：54 ms

考えたことを言語化してみる

1行目：標準入力値を取得して多重代入

2行目：空の配列aryを作る

3〜7行目（each文）
（4行目）標準入力値を取得して変数 d に代入
（5行目）次の行の標準入力値を取得して配列としてlineに代入
（6行目）lineをaryに要素として展開した上で追加
（3行目）4〜6行目の処理を k 回繰り返し

8行目：aryの重複する値を削除した要素数を n から引いて出力

これ、見ればわかる通りwith_indexは不要だったんですけど、最初使うつもりで書いていてうっかりそのまま出してしまいました。

最初問題の意味がよくわからずWA（Wrong Answer：不正解）出しました。いろいろと反省です。

今回はsplat展開というのを使ってみました。

a = [1, 2]
b = [3, 4]
c = a.push(b)
p c
#=> [1, 2, [3, 4]]

配列に要素を追加したいときに、上のコードのように配列をそのまま追加すると、配列が配列のまま1つの要素として追加されてしまいます。この3, 4を、それぞれ要素として追加したいときに使えるのがsplat展開で、*を使って次のように書きます。

a = [1, 2]
b = [3, 4]
c = a.push(*b)
p c
#=> [1, 2, 3, 4]

他の方のコードを見て知ったのですが、こういうときに使えるflattenというメソッドがありました。フラットにする、という意味ですね。これは使えそう！

a = [1, 2]
b = [3, 4]
c = a.push(b)
p c.flatten
#=> [1, 2, 3, 4]

Array#flatten (Ruby 2.7.0 リファレンスマニュアル)

感想

にしてもすぬけって何だろう？？と思っていたら…

そうだったんですね！でもすぬけ君とは…？？謎は深まります。

そろそろ競技プログラミング以外のことも書いていこうかなと思います。