コンテンツへスキップ

【Ruby基礎】AtCoder Beginner Contest 022 B – Bumble Bee

  • by

INDEX

■はじめに

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

（5/23時点の方針）
メソッドの切り分け方や値の受け渡しを練習するために、コード長の短さについては気にせずに書くことにする。

（2022/10/17時点の方針）
しばらくはB問題を小さい番号の方からやっていく。たまにA問題もやるかも。

■問題

●出典

AtCoder Beginner Contest 022のB問題
https://atcoder.jp/contests/abc022/tasks/abc022_b

●問題文

高橋君はマルハナバチ(Bumblebee)という種類のミツバチです。

今日も花の蜜を求めて異なる N 個の花を訪れました。

高橋君が i 番目に訪れた花の種類は Ai です。

i 番目の花は、i>j かつ i 番目の花の種類と j 番目の花の種類が同じになるような j が存在すれば受粉します。

高橋君が訪れた N 個の花の種類の情報が与えられるので、そのうちいくつの花が受粉したか求めてください。

なお、高橋君以外による受粉や自家受粉を考える必要はありません。

●入力

入力は以下の形式で標準入力から与えられる。

N
A1
A2
:
AN
  • 1 行目には高橋君が訪れた花の個数を表す整数 N(1≦N≦10^5) が与えられる。
  • 2 行目からの N 行のうち i 行目には i 番目に高橋君が訪れた花の種類を表す整数 Ai (1≦Ai ≦10^5) が与えられる。

●出力

受粉した花の個数を 1 行で出力せよ。出力の末尾にも改行を入れること。

■回答

●愚直に書く

問題文にある条件が少しわかりにくかったけど、「高橋くんが順番に花を訪れて、過去に同じ番号の花を訪れていれば受粉させることができる」ってことだと思う。
ピンときた書き方があるのでやってみる。

n = gets.to_i
a = n.times.map {|a| a = gets.to_i}
puts a.size - a.uniq.size

通った！
sizeで配列の数が出せるのと、uniqで重複文を削除できるから、つまりこれらの差が同じ番号を訪れた数、ということになる。

●メソッド化して書く

メソッドを作る練習のために、あえてそういう書き方をする。

メインメソッド、受粉した数を数えるメソッド、花がいくつあるかを読み込むメソッド、花の種類を配列で取るメソッドの４つで作成した。

def main
  a = read_type_flowers
  puts count_pollination(a)
end

def count_pollination(a)
  a.size - a.uniq.size
end

def read_nums_flowers
  gets.to_i
end

def read_type_flowers
  n = read_nums_flowers
  n.times.map {|a| a = gets.to_i}
end

main

通った！

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

思いつかないので割愛。

●他の方の回答例

同じ考え方の人が多かったけど、自分もちょっと思ってすぐやめたtallyを使っている方がいたのでその方向性もやってみる。

tallyを使うと、配列内の何の要素が何個ずつあるのかをhashで返してくれる。
tallyで出てきた値からそれぞれ1を引いて足し上げれば、重複した数＝今回求めたい数値が出るということか。

n = gets.to_i
a = n.times.map {|a| a = gets.to_i}
puts a.tally.values.map{|f| f - 1}.sum

通った！なるほど〜。

●出てきたメソッド等

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

■振り返りなど

解法がすぐに思い浮かんで良かったのと、別解を知ることができて良かった。