Ruby基礎(競技プログラミング過去問より)

概要

どうも、島生まれの地元が好きすぎて名前が島んちゅぬ宝をなんとなく英語っぽくしてみたIslanders-Treasure0969です。
私は現在常用雇用型派遣でとある業務アプリケーションを開発する企業の導入/開発エンジニアとして勤務しています。
そんな中、Web系の可能性に魅力を感じて現在転職活動のための勉強＆ポートフォリオ作りの真っ最中です。
転職活動の勉強とポートフォリオをしている側、ふとしたきっかけで最近競技プログラミングを始めてみました。
理由としては以下のとおりです。

①生のRubyをたくさん触って慣れたい

②フレームワークに頼らない低レイヤーの実装力も鍛えたい

そこで、競技プログラミングでコンテストに出たり、過去問を解いていく上で、ヒントになったことや考え方をQiitaにまとめようと思いました。
尚、ここで取り上げる過去問は以下に表示している@drkenさんさんの記事の中で取り組んでおいた方がいい
過去問が厳選されておりましたので、そちらを解いていき、随時更新する形になります。
また、リンクの記事の順番で解いていくわけではないので、ご了承ください。
当方Ruby歴3ヶ月程度の、業務でRubyを使ったことのない、所謂ペーペーなので実装上変なところとか、クソコードが散見されると思うので、見つけたらどしどしマサカリお願いします！！

記載方法

内容は以下のように記載していきます。

コンテスト番号

①問題の難易度-タイトル

②回答

③実装上で悩んだこと・Tips

④参考URL

⑤(あれば)所感

ABC-198

B-Palindrome with leading zeros

回答

sample.rb

str = gets.chomp.to_s

def prefixzerotrim(s)
    s_index = s.length - 1
    news = ""
    s.chars.to_a.each_with_index do | n, i |
        if n != "0"
            return news = s[i..s_index].to_s
        else
        end
    end
    return s 
end        

s1 = prefixzerotrim(prefixzerotrim(str).reverse)
s2 = s1.reverse
s1 == s2 ? puts('Yes') : puts('No')

実装上で悩んだこと・Tips

①問題の意図を理解するのに時間がかかった。
以下問題文抜粋

整数N を標準入力として与えた時にN を十進法で表した文字列の先頭に 0 個以上の 0 をつけることで、回文にすることはできますか？

最初は回文にするのに、文字列の後ろの0と数を合わせないといけないのかと思っていた。
結果的なアプローチとしては以下のようになった
・0を先頭につけて回文になるということは、先頭と末尾の連続した0を除外することでも回文となることを理解する
・先頭と末尾の0をトリムして文字列比較する

②関数で0を除いた文字列を返す方法
・文字列を先頭から走査して、0以外の文字列が出てきたところでその位置から後を新しい
文字列として返すように実装した
・また、DRY原則にならって末尾の0については戻り値の文字列を反転させて再度関数に投げるようにした

2021/4/17
③配列のインデックス指定、関数の戻り値
@superrino130　さんのコメントを受けての気づきです、ありがとうございます。
配列のインデックスにはマイナスでの指定も可能なようです！

return news = s[i..-1] #=> 一番最後の要素までを指定

後、rubyには関数の戻り値を指定する必要はなく、returnで返す値がそのまま返るということでした！

2021/4/20
コメント欄に@scivola さんと @github0013@github さんにご指摘いただいた通り、パターンマッチングで簡単に処理できるようです！

#パターンにマッチしたMatchDataのインデックス１(0*\zが当てはまらない部分文字列)の文字列を反転して比較した結果を真偽値で返す
puts 1210121000.to_s.match(/(\d+?)0*\z/){|m| m[1] == m[1].reverse} ? "Yes" : "No"
#パターンマッチした部分文字列を””（何もない）に置き換えて、反転して比較した結果を真偽値で返す
puts 1210121000.to_s.reverse.sub(/\A0+/,"").then{_1 === _1.reverse} ? "Yes" : "No"

※then内の_1はRuby2.7から実装された番号指定パラメータですが、個人的には直感的ではなく、可読性に今のところ難ありなので普通に|m|などとした方がいいかも

参考URL

each_with_indexの使い方(るびま)
配列　負のインデックス操作

所感

2021/4/15現在で初受験のABCテストで、実装力なさすぎて解けなかった問題です。。。
よくよく考えたら、そんなに難しい問題じゃなかったですね。
初心者の自分には文字列とかその他言語に慣れるためにちょうどいい難易度だと思いました！
そして最初から冒頭のURL以外の問題を解くという。。。
まー緩く楽しくやれればいいか。

ABC-082

B-Two Anagrams

回答

sample.rb

s1 = gets.chomp.chars.sort.join
t1 = gets.chomp.chars.sort.reverse.join

s1 < t1 ? puts('Yes') : puts('No')

実装上で悩んだこと・Tips

①配列→文字列変換でだいぶ悩んだ
以下実験内容

sample.rb

s = gets.chomp.chars.sort.to_s
t = gets.chomp.chars.sort.reverse.to_s
puts("#{s} #{s.class}")
puts("#{t} #{t.class}") 
s < t ? puts('Yes') : puts('No')

s1 = gets.chomp.chars.sort.join
t1 = gets.chomp.chars.sort.reverse.join
puts("#{s1} #{s1.class}") 
puts("#{t1} #{t1.class}")
s1 < t1 ? puts('Yes') : puts('No')

#入力
#adebc
#a
#adebc
#a
#出力
#["a", "b", "c", "d", "e"] String
#["a"] String
#Yes
#abcde String
#a String
#No

文字列をソートして比較するときに、sortメソッドが返す値を気にしておらず、このように記載してしまった
変数sに格納されているのは、["a","b","c","d","e"]という文字列になる
lengthで長さを出力するとわかるが、25と出る。
最初この挙動に少し悩んでしまった。
だが、るりまにも書いてあるとおり、

配列の内容をソートします。要素同士の比較は <=> 演算子を使って行います。sort はソートされた配列を生成して返します。

とのことなので、返ってくる値は配列であり、これをto_sで文字列にしても上記のようになる。
そこで、結果としてはjoinを使用してソートした結果の配列を文字列に結合する必要がある。
joinについてのるりまの説明は以下。

要素がまた配列であれば再帰的に (同じ sep を利用して) join した文字列を連結します。

また、joinメソッドは引数にとった文字列を配列間に挿入して返すこともできるらしい。

sample.rb

s1 = gets.chomp.chars.sort.join('&')
puts("#{s1} #{s1.class}") 
#a&b&c&d&e String

参考URL

join(るりま)
sort(るりま)

所感

配列と文字列の関係が少しだけわかった気がした。
配列と文字列と少しだけ仲良くなれた。
発展的な内容として、文字列は結果的にバイトで比較するようなので、最初からバイトで比較すれば実行結果もまだ早くなる？
なんか他の人のソースみたときに受けた値をバイトに直して比較しているのがあったので、実行結果を考えるならそっちの方がいいと思った(ソースとしては長くなるけど)
こんなんとか
ソース書いてる人

ABC-102

B-Maximum Difference

回答

n = gets.chomp.to_i
arr = gets.chomp.split(' ').to_a.sort{|a,b| a.to_i <=> b.to_i }
puts(arr.last.to_i - arr.first.to_i)

実装上で悩んだこと・Tips

①数値のsort
問題文の本意としては、数値を比較してソートする必要があったのですが、sortメソッドを引数なしで実行すると文字列比較になるので、上記のソースのようにブロックで比較する要素を数値型にして比較する必要がありました。
その上で、配列の最初と最後を比較するだけなので最後は配列の最初と最後の差を出力しています。

参考URL

特になし

(あれば)所感

過去問精選の方ではループの処理を使うようになっているっぽい？問題でも最初に要素数を与えられていたのでそれを使用して解く問題かもしれませんが、自分はループよりこっちの方が先に思い浮かびました！

2021/4/20
@scivola さんの指摘の通り、sortにブロックを渡すと毎回ソートキーを作成するので計算量的に効率が悪いらしいので、sort_byでソートした方がいいとのことでした！
さらに配列の中身が数値の場合はminmaxメソッドで最大値と最小値が取得できるらしいので以下のように書き換えることができそうです！

#splitで空白文字列で取得した配列をmapで数値型にし、minmaxメソッドで受けた値をthenに渡して差を出力する
gets
puts gets.split.map { |e| e.to_i }.minmax.then{|a,b| (b-a)}

ABC -113

①B-Palace

②回答

gets
T, A = gets.split.map { |e| e.to_i }
arr = gets.split.map { |e| e.to_i }

x = ( T - A ) / 0.006

puts (arr.find_index(arr.sort_by{|a| (a.to_i - x).abs }.first) + 1)

③実装上で悩んだこと・Tips

問題文で与えられているA℃となる標高を導出する式を考えるのに少し時間がかかりました。
後はこれまでの知識で解けたのですが、多分最適化はされていないはず。。。
この問題も与えられているNを使用した方が計算量が抑えられるのかわからないのですが、使用しない方法が先に浮かんだので、そちらを採用しました。

・配列から値を検索する処理
前回までの知識から、arrから任意の値を調べるというよりは、配列をxとの差の絶対値で並べ替えて、その一番最初の値で検索するという方法しか思いつきませんでした。
まだ他の方の回答を見ていないため、その上で再考したいです！

④参考URL

るりま(find_index)
るりま(with_index)(ソースの中に必要ないので消した)

⑤(あれば)所感

ABC-072

①B-OddString

②回答

puts gets.chars.filter.with_index{|n,i| i.even?}.join

③実装上で悩んだこと・Tips

・文字列のインデックス操作での絞り込み
最初は文字列をループで回そうとか考えましたが、それより便利なメソッドあるやろなーとArrayをるりまで検索していたら、、、filterメソッドという便利なメソッドがありました。
ですので、方針としては
　①文字列を配列にする
　②配列をインデックス付きでfilerメソッドに渡す
　③配列のインデックスが偶数の時だけ通す
　④joinで結合する
としたらうまいことできました！

④参考URL

るりま(Array)

⑤(あれば)所感

filerにインデックス付きで処理を渡していますが、ここがもう少しないけど。。。
これについては、５分以内にアウトプットを導出できたので少しは慣れてきたと思います！

ABC053

①B - A to Z String

②回答

puts gets.match(/A[A-Z]*Z/ ).to_s.length

③実装上で悩んだこと・Tips

・文字列一致問題ということに気づくまで
問題文を読めばわかるのですが、今回の問題は与えられた文字列の中での先頭が「A」で末尾が「Z」の最長一致の長さを取得する問題でありました。
もはやループで処理を実装する方がパッと思い浮かびませんが。。。
@github0013@github さんにご教授いただ内容で正規表現が出てきていたので、以下の方針で考えました。
　①与えられた文字列に対してmatchメソッドで正規表現にマッチした値を取得する(返り値はMatchdataクラス)
　②文字列型に変換する
　③lengthメソッドで文字列長を取得する

②で文字列型に変換する理由としては、MatchDataクラスのlengthメソッドはstrngクラスとは違うので注意が必要です。MatchDataクラスのlengthメソッドの説明は以下の通り

部分文字列の数を返します(self.to_a.size と同じです)。

とのことですので、今回のmatchメソッド実行後のMatchDataクラスに対してlengthメソッドを実行しても結果は1にしかなりません。
ですのでいちど文字列に変換する必要がありました。

④参考URL

るりま(MatchData)

⑤(あれば)所感

なんかちょっとずつだけどrubyに慣れてきた感！(まだB問題にしか触ってません)

ABC-095

①B - Bitter Alchemy

②回答

N, x = gets.split.map(&:to_i)
marr = Array.new(N) {gets.to_i}
puts(N + (x-marr.sum).div(marr.min))

③実装上で悩んだこと・Tips

・ブロック付きメソッドのに対してブロックを指定するときのシンタックスシュガー
今までsplitで配列にした要素がinteger型をとって欲しい時はブロックのなかでto_iで変換しており、若干手間でした。
これより他に良い方法がないか(というかあるはず！)というところで、「&:」にたどり着きました。
意味を分からず使うと危ないので、当方が理解したをまとめると以下になります。
　①＆はブロック付きメソッドの引数として＆の右のProcオブジェクトを渡す
　②mapメソッドのようなブロック引数をとるメソッドは、そのままの意味の通り引数にはブロックを期待するため、(&:to_i)の部分はブロックであることが期待される
　③よって、:to_iの部分はProcオブジェクトであることが期待されており、暗黙的にto_procが呼ばれる(らしい)
　④Symbol#to_procでは、レシーバー(この場合はmapメソッドの左側間での処理結果)に対して:to_iをメソッドとしたProcが返る
　⑤Procのcallがmapメソッドによって呼ばれたときにsplit間での配列の要素をProcのレシーバーとして一つずつto_iメソッドを実行するようになる
理解した上で、ブロック付き引数を指定するメソッドの後にはこれを使えば簡潔にかけそうです！
参考にしたサイト
とのことでした。
このとき、mapメソッドが引数にとる値はブロックであることが期待されるため、&のあとの:to_iはProcオブジェクトであることが期待され、暗黙的にSymbol#to_procが呼ばれるとのことでした。
Symbol#to_procの挙動は以下参考URLのるりま等をご覧ください！

④参考URL

Rubyのmap &:to_iとはなんなのか
Rubyで "&" を使うと幸せになれるらしいよ (*´Д`)ﾉ
Rubyでメタプログラミング ～暗黙的に呼ばれるto_procメソッド
Symbol#to_proc
第一引数にメソッド名をとり、第二引数以降に引数をとる
結果は、引数のレシーバーをメソッドで処理するProcオブジェクトを返す
Object#send
オブジェクトのメソッドを第一引数として、第二引数以降をメソッドの引数として実行する
第一引数は文字列かシンボルで指定したメソッド名をとる

⑤(あれば)所感

Procオブジェクトとかブロックとか＆(アンパサンド)の使い方とかそれを使用したブロック引数のシンタックスシュガー的な物とか学びが多かった。。。
実装には時間かかったけど、これからのブロック引数の指定がラクになりそう！

ABC-133

①B - Good Distance

②回答

N, D = gets.split.map(&:to_i)
arr = []
N.times{arr << gets.split.map(&:to_i)}
cnt = 0

def distance(a, b)
    Math.sqrt(a.zip(b).map{ |n, m|(n - m)**2 }.sum)
end

arr.combination(2).map{|a, b| cnt += 1 if distance(a, b).to_s.match?(/\.0+?\z/) }
puts cnt

③実装上で悩んだこと・Tips

・配列の組み合わせの作成
今回の問題は初見ではなんとなく解法はわかったのですが、プログラムの方法がわからない問題でした。
２点間の距離の公式に当てはめるとき、次元の数がパラメータとして与えられるので、この距離の公式をしようした距離を求める式は一般化する必要があるので、そこに少し苦労しました。
新しく学んだ配列のメソッドとしては

・combinationメソッド
るりまの説明としては

サイズ n の組み合わせをすべて生成し、それを引数としてブロックを実行します。

とのことです。今回で言えば、arrに各点を配列で格納しているので、それを2点の組み合わせで返すためにcombination(2)としています。
そうすることで2点の組み合わせがかえされるのでそれを使用してその後のmapメソッドで次の処理をしています。

・zipメソッド
　るりまの説明としては

自身と引数に渡した配列の各要素からなる配列の配列を生成して返します。生成される配列の要素数は self の要素数と同じです。

とのことです。combinationメソッドで2点の情報を配列で受けているため、それをzipメソッドで2点間の関係を各次元の配列に直した配列で返すようにしています。
それをその後に定義した関数の２点間の距離の公式を一般化した関数で処理して値を返しています。

さらに、整数かどうかの判断が地味に悩ましかったところで、ググったところめぼしい解決策が正規表現を用いた判断しか思いつきませんでした。
具体的には
・distanceメソッドで帰ってきた値を文字列化した末尾が「.と０の連続」であれば整数とする
というのに基づいて判断しました。

④参考URL

⑤(あれば)所感

ABC-088

①B - Card Game for Two

②回答

gets
arr = gets.split.map(&:to_i).sort.reverse

alice = arr.filter.with_index{|n,i| i.even?}.sum
bob = arr.filter.with_index{|n, i| i.odd?}.sum

puts alice - bob

③実装上で悩んだこと・Tips

・今までの実装での知識で難なく解けたので特に悩む箇所はありませんでした(と言いつつ最初はfilterにindexを渡していなくてeven?やodd?を値に対して行っていたのでWAとなったのは内緒)

④参考URL

⑤(あれば)所感

随時更新予定！！

2021/4/2１
ABC-095のB - Bitter Alchemy を解いたので更新しました！

※なお、現在B問題等にしか当たっていないのは理由がありまして
①まだRubyでの実装に慣れていない(問題文をRubyで考えてアウトプットすることに慣れていない)
②B問題程度の実装で詰まるようではC以降のアルゴリズムや計算量を意識した問題に太刀打ちできない
実際にABCテストを先日受験して、なんとAしか解けないという散々な結果だったのですが、実際にRubyで問題を考えることが全くできない状況でした。
ですので、上記の精選問題で慣れた後にC問題に取り組もうという感じです。
※一応数検2級とかとった経緯もあるので、C問題くらいのアルゴリズムならラクショーやろと思ってたのですが、実際に解いたら激ムズで何も思い浮かびませんでした。。