@Lily0727Kさんの「競技プログラミングで役立つテクニック 初級編12問」にて掲載されている12問をRubyで解いてみました。
詳細な解説は元記事をご覧ください。
8級の問題1
def even_or_odd(n)
n.even? ? "Even" : "Odd"
end
レシーバーが奇数ならtrueを返す組み込みメソッドのeven?を使いました。
可読性が良くなる組み込みメソッドが用意されているのはRubyのメリットの一つですね。
8級の問題2
def make_negative(n)
-n.abs
end
元記事のコードとほとんど同じですね。
Rubyでは最後に評価された値が返るため、returnを明示する必要がないのでコードが少し短くなりました。
8級の問題3
def summation(n)
(1..n).sum
end
def summation(n)
(1..n).inject(:+)
end
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
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
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
def dna_strand(dna)
dic = { "A" => "T", "T" => "A", "G" => "C", "C" => "G" }
dna.gsub(/[ATGC]/, dic)
end
gsubの第2引数に{ マッチした文字列 => 置換文字列 }という形式のハッシュを渡しています。
置換ルールが直感的にわかりやすく、簡単に定義できるので便利なメソッドです。
7級の問題2
def disemvowel(str)
str.gsub(/[aiueoAIUEO]/, "")
end
またgsubの出番です。
第2引数に空文字を渡すことでパターンマッチした文字をすべて削除できます。
7級の問題3
def is_square(n)
n >= 0 && Math.sqrt(n) == Math.sqrt(n).to_i
end
引数の平方根を返すMath.sqrtメソッドを使いました。
7級の問題4
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
def grow(arr)
arr.inject(:*)
end
injectメソッドに*演算子を渡して畳み込みの掛け算をしています。
6級の問題1
def find_it(arr)
arr.each do |i|
if arr.count(i).odd?
return i
end
end
end
def find_it(arr)
arr.inject(:^)
end
単純に考えるとaですね。
明示的にreturnすることで、解答が見つかった時点でその値を返しています。
bは排他的論理和の性質を利用した解法ですが、自力で考え至ることはなかったと思います。
元記事にて詳しく説明されているので、是非ご覧ください。
数学的な考え方を学べた良い問題でした。
6級の問題2
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
def persistence(n)
n < 10 ? 0 : persistence(n.to_s.split('').map(&:to_i).inject(&:*)) + 1
end
与えられた数値を一桁ずつ配列に格納して、injectで各桁の値をすべて掛け合わせています。
最終的にすべて掛け合わせるため、桁を格納する際の並び順は関係ないのですが、並び順を元の数値と同じにしておいた方がわかりやすかと思い、unshiftを採用しました。
bのようにワンライナーで書くこともできましたが、文字列にキャストしているので遅かったです。
再帰関数の勉強になる良い問題でした。
6級の問題3
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
def digital_root(n)
!(n % 9).zero? && n % 9 || n.zero? && n || 9
end
aは前問と同じく再帰関数を使った解法です。
bは元記事で紹介されている整数論を使った解法です。
こちらは自力では考え至らなかったと思います。
整数論の重要さを感じた良い問題でした。
元記事は「0はfalse」というPythonの性質を利用しスマートに解いていますが、Rubyでは「0はtrue」なのでこういったコードになりました。
||演算子の「左辺がtrueなら右辺は評価しない」、Rubyの「最後に評価された値を返す」という性質を利用してみました。
if文で書いたほうが可読性は高いですが、ワンライナーで書くならこうなるのかなと。
まとめ
競技プログラミングに関しては初心者なので、簡潔なロジックの書き方の勉強になりました。
また、記事として投稿するにあたって、リファクタできないかを考えたことで言語の理解が深まりました。
記述する内容もできるだけ正確であるように意識し、曖昧な点を調べるきっかけになったため、これからも勉強したことはなるべく投稿していきます。
ただ、自分にはロジックを簡潔に書くために必要な数学的思考力、整数論の知識が欠けていることを感じました。
基礎的なアルゴリズムと並行して勉強していこうと思います。