Posted at

競技プログラミングに役立つテクニック 初級編12問をRubyで解いてみた

@Lily0727Kさんの「競技プログラミングで役立つテクニック 初級編12問」にて掲載されている12問をRubyで解いてみました。

詳細な解説は元記事をご覧ください。


8級の問題1

Even or Odd

def even_or_odd(n)

n.even? ? "Even" : "Odd"
end

レシーバーが奇数ならtrueを返す組み込みメソッドのeven?を使いました。

可読性が良くなる組み込みメソッドが用意されているのはRubyのメリットの一つですね。


8級の問題2

Return Negative

def make_negative(n)

-n.abs
end

元記事のコードとほとんど同じですね。

Rubyでは最後に評価された値が返るため、returnを明示する必要がないのでコードが少し短くなりました。


8級の問題3

Grasshopper


a.rb

def summation(n)

(1..n).sum
end


b.rb

def summation(n)

(1..n).inject(:+)
end


c.rb

def summation(n)

n * (n + 1) / 2
end

一番最初に思いつくのはaですが、Rubyのバージョンが低いとsumは使えません。

CodeWarsでは2.5か2.3か選べるので問題ありませんが、AtCoderでは2.3.3固定です。

b、cはそういった問題は起こりませんが、速度面では和の公式を使うcの方がベター。


8級の問題4

Count of positives / sum of negatives


a.rb

def count_positives_sum_negatives(arr)

return [] if arr.empty?

count = 0
sum = 0

arr.each do |i|
i > 0 ? count += 1 : sum += i
end

[count, sum]
end



b.rb

def count_positives_sum_negatives(arr)

arr.empty? ? [] : [arr.select(&:positive?).size, arr.select(&:negative?).sum]
end

bはワンライナーで書いてみました。

selectメソッドと正負を判定するpositive?negative?で要素が正だけ、負だけの配列を作成し、それぞれの要素数、要素の和を取っています。

ただ、selectを2回呼んでいるので、速度はイマイチかもしれません。


7級の問題1

Complementary DNA

def dna_strand(dna)

dic = { "A" => "T", "T" => "A", "G" => "C", "C" => "G" }
dna.gsub(/[ATGC]/, dic)
end

gsubの第2引数に{ マッチした文字列 => 置換文字列 }という形式のハッシュを渡しています。

置換ルールが直感的にわかりやすく、簡単に定義できるので便利なメソッドです。


7級の問題2

Disemvowel Trolls

def disemvowel(str)

str.gsub(/[aiueoAIUEO]/, "")
end

またgsubの出番です。

第2引数に空文字を渡すことでパターンマッチした文字をすべて削除できます。


7級の問題3

You're a square!

def is_square(n)

n >= 0 && Math.sqrt(n) == Math.sqrt(n).to_i
end

引数の平方根を返すMath.sqrtメソッドを使いました。


7級の問題4

Add 2 values for each

def make_new_list(x)

x[0..-2].zip(x[1..-1]).map(&:sum)
end

make_new_list = -> (x) { x[0..-2].zip(x[1..-1]).map(&:sum) }

60文字以内という制約の関係上、言語がPythonに指定されているためRubyでは提出できませんが、書くならこんな感じですかね。

Rubyのzipメソッドは2つの配列の要素数が一致していないと返り値にnilが含まれてしまうのでx[0..-2].zip(x[1..-1])として要素数を合わせています。

(Pythonでは要素数が一致しないとき、余った要素は省かれるようです。)

コードを短くするためにlambda式でも書いてみました。


8級の問題5

Beginner - Reduce but Grow

def grow(arr)

arr.inject(:*)
end

injectメソッドに*演算子を渡して畳み込みの掛け算をしています。


6級の問題1

Find the odd int


a.rb

def find_it(arr)

arr.each do |i|
if arr.count(i).odd?
return i
end
end
end


b.rb

def find_it(arr)

arr.inject(:^)
end

単純に考えるとaですね。

明示的にreturnすることで、解答が見つかった時点でその値を返しています。

bは排他的論理和の性質を利用した解法ですが、自力で考え至ることはなかったと思います。

元記事にて詳しく説明されているので、是非ご覧ください。

数学的な考え方を学べた良い問題でした。


6級の問題2

Persistent Bugger


a.rb

def int_to_array(int)

array = []
array = [0] if int == 0
while int > 0
digit = int % 10
array.unshift(digit)
int /= 10
end
array
end

def persistence(n)
n < 10 ? 0 : persistence(int_to_array(n).inject(&:*)) + 1
end



b.rb

def persistence(n)

n < 10 ? 0 : persistence(n.to_s.split('').map(&:to_i).inject(&:*)) + 1
end

与えられた数値を一桁ずつ配列に格納して、injectで各桁の値をすべて掛け合わせています。

最終的にすべて掛け合わせるため、桁を格納する際の並び順は関係ないのですが、並び順を元の数値と同じにしておいた方がわかりやすかと思い、unshiftを採用しました。

bのようにワンライナーで書くこともできましたが、文字列にキャストしているので遅かったです。

再帰関数の勉強になる良い問題でした。


6級の問題3

Sum of Digits / Digital Root


a.rb

def sum_of_digit(int)

sum = 0
while int > 0
sum += int % 10
int /= 10
end
sum
end

def digital_root(n)
n < 10 ? n : digital_root(sum_of_digit(n))
end



b.rb

def digital_root(n)

!(n % 9).zero? && n % 9 || n.zero? && n || 9
end

aは前問と同じく再帰関数を使った解法です。

bは元記事で紹介されている整数論を使った解法です。

こちらは自力では考え至らなかったと思います。

整数論の重要さを感じた良い問題でした。

元記事は「0false」というPythonの性質を利用しスマートに解いていますが、Rubyでは「0true」なのでこういったコードになりました。

||演算子の「左辺がtrueなら右辺は評価しない」、Rubyの「最後に評価された値を返す」という性質を利用してみました。

if文で書いたほうが可読性は高いですが、ワンライナーで書くならこうなるのかなと。


まとめ

競技プログラミングに関しては初心者なので、簡潔なロジックの書き方の勉強になりました。

また、記事として投稿するにあたって、リファクタできないかを考えたことで言語の理解が深まりました。

記述する内容もできるだけ正確であるように意識し、曖昧な点を調べるきっかけになったため、これからも勉強したことはなるべく投稿していきます。

ただ、自分にはロジックを簡潔に書くために必要な数学的思考力、整数論の知識が欠けていることを感じました。

基礎的なアルゴリズムと並行して勉強していこうと思います。