AtCoderのB問題が解けるようになった

この記事はフィヨルドブートキャンプ Part 1 Advent Calendar 2022 - Adventarの13日目の記事です。
昨日はHikaruさんの「オブジェクト指向設計実践ガイド（POODR） 感想 & 第1章 まとめ - Light! More Light!」でした。

フィヨルドブートキャンプの今年のアドベントカレンダーはこちらです。

• フィヨルドブートキャンプ Part 1 Advent Calendar 2022 - Adventar
• フィヨルドブートキャンプ Part 2 Advent Calendar 2022 - Adventar

はじめに

こんにちは。フィヨルドブートキャンプ(以下、FBC)卒業生のガラムマサラです。
1日の学習初めの小手試しや、少しだけ時間があって何かコードを書きたいというときに、よくAtCoderの過去問を解いています。
これまでのAtCoderの取り組みや、B問題を解くためのTipsを本記事では紹介してみます。

AtCoderについて

AtCoderはプログラミングを使って問題を解くことを競技化したコンテストを開催するサイト・運営会社です。
AtCoder Beginner Contest、通称ABCは定期的に開催している初心者向けコンテストで、毎週A〜H問題が出題されています。
難易度としてA問題は「プログラミング言語の文法を確認する程度」、B問題は「FizzBuzzを応用する程度」とされています。
過去問が掲載されているので、コンテスト期間とは関係なく問題を解くことができ、各問題に解説があったり、他人の解答を見ることができるので、大変勉強になります。
AtCoderを使った勉強法に関しては、同じAtCoder学習仲間であるsugieさんが一昨日書かれた記事が参考になります。

sugie.co

わたしとAtCoder

FBCでRubyのプラクティスが終わった頃、同期のあんすとさんの紹介でAtCoderの過去問を解き始めました。
最初は標準入力ってどうやって受け取るの？という状態でしたが、それに慣れると少しずつA問題が解くことができました。
B問題となるとループを含んだ実装になるので、eachを使うのでやっとだった自分はほとんど手がつけられない状況でした。

FBCで学び、チーム開発や自作サービスでRubyのコードを書いていった中、久々にB問題に取り組んでみると、「あれ、なんだか解けるぞ！」とブレイクスルーを感じられて嬉しかったです。
多くのRubyistが言う「Rubyで書くが楽しい」ということも、なんとなく感じ取れている気がします。
本日までにB問題は81問解いていました。新しめの問題の方が難しいので、できるだけそちらを解くようにしています。

以降はそのB問題攻略の解き方のコツや便利なRubyメソッドを紹介、一緒に実際の問題も載せておきます。
AtCoder初心者の方の参考になるかもしれません(今回は解くことが目的で、計算量については考えられていないのであしからず…)

標準入力から受け取る

整数nを1つ受け取とった後、n行のスペース区切りの整数を二次元配列で受け取る方法です。

2
1 3 5
2 4 6

n = gets.to_i #=> 2
array = n.times.map { gets.split.map(&:to_i) }
#=> [[1, 3, 5], [2, 4, 6]]

array = n.times.map do
  gets.split(' ').map do |line|
    line.to_i
  end
end
#=> [[1, 3, 5], [2, 4, 6]]

頻繁に出題される形です。
Array.newやreadlinesを使うなど様々な方法がありますが、1つ得意な形を持っておくと応用も効きやすいので良いかなと思います。

全探索

考えられる全ての場合を調べることです。
表や二次元盤面を要する問題など、よくこの方法を使います。
主に二重、場合によって三重でeachやtimesを使って繰り返すことで全探索できることが多いです。

array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count = 0
array.each do |i|
  array.each do |j|
    count += 1 if (i * j).even?
  end
end
puts count
#=> 56

九九の表を1つ1つ評価しているイメージです。

全探索で解いた問題

• B - How many?
• B - Tournament Result
• B - Job Assignment

---

全探索をするよりArrayやEnumerableモジュールのメソッドで簡単に解決できるものもあります。

Enumerable#each_with_index

要素の添え字付きの繰り返し処理です。

array = ['a', 'b', 'c']
array.each_with_index do |a, i|
  p "#{i}: #{a}"
end
#=> "0: a"
#   "1: b"
#   "2: c"

添え字を0以外からにしたいときにはEnumerator#with_indexを使います。

array.each.with_index(1) do |a, i|
  p "#{i}: #{a}"
end
#=> "1: a"
#   "2: b"
#   "3: c"

each_with_indexで解いた問題

• B - Explore
• B - Takahashi's Failure

Array#combinationとArray#permutation

combinationは並び順を考慮しない組み合わせを、permutationは並び順を考慮する順列を生成するメソッド。
引数で選び出す要素の個数を指定できます。

array = [1, 2, 3, 4]
array.combination(2).to_a
#=> [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
array.permutation(2).to_a
#=> [[1,2],[1,3],[1,4],[2,1],[2,3],[2,4],[3,1],[3,2],[3,4],[4,1],[4,2],[4,3]]

重複を許可するArray#repeated_combinationとArray#repeated_permutationもあるので、このあたりは公式リファレンスを確認します(まだ使ったことがない気がする)

combinationで解いた問題

• B - Everyone is Friends
• B - Triangle (Easier)

Enumerable#each_cons

要素を重複ありで引数nずつに区切り、ブロックに渡して繰り返すメソッド。
1回のループで要素を1つずつしか取得できないeachに比べ、こちらは複数個の要素を扱えるので便利です。

array = [1, 2, 3, 4]
array.each_cons(2){ |v| p v }
#=> [1, 2]
#   [2, 3]
#   [3, 4]

each_consで解いた問題

• B - Inverse Prefix Sum
• B - Practical Computing

Array#transpose

行と列の入れ換えをするメソッド。
個人的にFBCのプラクティス「ls コマンドを作る」で使ったメソッドなので思い出に残っています。

[[1, 2],[3, 4],[5, 6]].transpose
#=> [[1, 3, 5], [2, 4, 6]]

transposeで解いた問題

• B - Line Sensor
• B - Matrix Transposition

Array#find_index

indexとしても同様です。配列内の指定した要素の最初の位置を取得するメソッド。
配列内に重複している要素があり、その一つだけを取り出したい場合に、「最初の」インデックス値を取得し操作できるので便利です。
Array#rindexは最後から順に探してくれます。

# 2をひとつだけ削除したい
array = [1, 2, 2, 3, 3, 3]
# これでは2を全て削除してしまう
array.delete(2)
array #=> [1, 3, 3, 3]

# インデックス値を取得できるｓと1つだけ削除可
array.delete_at(array.index(2))
array #=> [1, 2, 3, 3, 3]

indexで解いた問題

• B - Rectangle Detection
• B - Bouzu Mekuri

Enumerable#tally

要素を数え上げ、Hashで返すメソッド。
このメソッドは、僕のAtCoderの先生でもあるharuguchiさんから教えてもらいました。
tallyを使って簡潔に解ける問題も多く、個人的に一番好きなメソッドになりました。

['a', 'b', 'b', 'c', 'c', 'c'].tally
#=> {"a"=>1, "b"=>2, "c"=>3}

tallyで解いた問題

• B - Who is missing?
• B - Pasta
• B - Star or Not

---

配列の合計

配列の和はArray#sum、要素を全て掛けるにはEnumerable#injectを使っています

array = [1, 2, 3, 4]
array.sum #=> 10
array.inject(:*) #=> 24

配列同士の積を求める問題

• B - Orthogonality

四捨五入・切り上げ・切り捨て

A問題から数字の四捨五入や切り上げ・切り捨てが出てくる頻度は高いです。
切り上げ切り捨てがどっちかよく混乱していたんですが、これもharuguchiさんから教えてもらったシーリングライト(天井)とフロア(床)のイメージで定着しました。

• 四捨五入：Numeric#round
• 切り上げ：Float#ceil
• 切り捨て：Float#floor

1.4.round #=> 1
1.5.round #=> 2
1.1.ceil #=> 2
1.9.floor #=> 1

四捨五入・切り上げ・切り捨てに関する問題

• B - Broken Rounding
• B - Round Down

参考文献

プロを目指す人のためのRuby入門［改訂2版

プロを目指す人のためのRuby入門 言語仕様からテスト駆動開発・デバッグ技法まで Software Design plus

FBCメンターの@jnchitoさんが執筆された、言わずと知れたチェリー本です。
配列、Range、Hash、繰り返し処理で迷ったときは必ずチェリー本に戻りました。答えはここに全部詰まっています！

プログラミングコンテストAtCoder入門

アルゴリズム的思考力が身につく！ プログラミングコンテストAtCoder入門

こちらは本記事を書くにあたって読んでみました。 Rubyではなく、C++とPython3のコードを用いて解説されているので、ソースコードに沿っての学習はできませんが、アルゴリズムを知る上で多くの知見が得られます。
この本によると自分は初級編をクリアしたところでした。中級編に進んでいきます！

さいごに

AtCoder運営の方々、いつも楽しませていただいています。ありがとうございます。 今後は実際に時間を調整してコンテストに参加してみたり、アルゴリズムの知識や計算量の意識が必要になってくるC問題以降に手をつけていきたいと考えています。

FBCでは、だいたい木曜日の昼頃にharuguchiさん主催でAtCoderを解く「勝手にモブプロ会」が行われています。
いつも楽しく学びのある会です。haruguchiさん、ありがとうございます！
FBCでAtCoderが気になっている方がいましたら、一緒にモブプロできると嬉しいです。

明日のFBCアドベントカレンダーは、Part1をkazumiさん、Part2をumizaruさんが記事を書いてくださいます。楽しみです！