【ruby】AtCorderで死ぬほどハマった問題で使ったメソッド

今回ハマったのはこの問題。問題解きながら使ったメソッドを忘れないようにメモしとく。

map(&:to_i)

この記事で複数数値の入力方法を書いたものの、なんか長ったらしくて… なんかいいのないかなと思ったら、これで良かったのか。

# before
num = gets.split.map{|i| i.to_i}

# after
num = gets.split.map(&:to_i)

パイプ使わない分短くかける。

combination

３辺の組み合わせを評価していけばいいはず！と考えた。配列の中で組み合わせを作るのを自力でやってたけど、メソッドがあったのか…

edges = gets.split.map(&:to_i)
edges.combination(3).to_a  # 3で組み合わせの数、to_aでArrayにする。
# 3 4 2 1
# =>[[3, 4, 2][3, 4, 1][3, 2, 1][4, 2, 1]]

combinationの評価は時間がかかる

combinationは少ない数のものならあまり気にしなくていいが、数が増えるととんでもないことになる。例えばn本の棒から3本選んだ組み合わせはnC3なので
n = 4 => 4
n = 5 => 10
n = 1000 => 166,167,000
e8の計算なんてしていたらとてもじゃないけど2sec以内に終わらない。なので、今回の問題ではcombinationを使わないのが正解の模様。
じゃあ何を使うべきかといったらsortだと思われる。

sort

sortは昇順で並び替えてくれる。ここで注意しなければいけないのは、intgerとstringでsortのされ方が違うってこと。

[20, 100, 1].sort
=> [1, 20, 100]
['20', '100', '1'].sort
=> ['1', '100', '20']

なので、mapと組み合わせて使うときは順番が大事。

# 正しくsortされる
num = gets.split.map(&:to_i).sort

# NG
num = gets.split.sort.map(&:to_i)

each文

繰り返しメソッドを使うとき、いつもwhile使ってたんだけどコード長くなる… ということでeachを使ってみた。

# 入力した複数の数値に対して偶数の個数を返す
# while文
nums = gets.split.map(&:to_i)
i = 0
count = 0
while i < nums.length do
  count += 1 if nums[i] % 2 == 0
  i += 1
end
puts count

# each文
nums = gets.split.map(&:to_i)
count = 0
(0..nums.length - 1).each do |a|
  count += 1 if num[a] % 2 == 0
end
puts count

while文ではiに関する文で２行使っていたけど、eachではそれがなくなったのでスッキリした。

bsearch_index

rubyにはバイナリーサーチ（２分探索）という機能がある。これは昇順・降順にsortされた配列から効率よく探索することができる。

ary = [0, 4, 7, 11, 15]
ary.bsearch {|x| x >= 6}
=> 7  # 6より大きい最初の値を返す
ary.bsearch_index {|x| x >= 8 }
=> 3  # 8より大きい最初の値は11で、そのindexを返す

indexはバイナリーサーチでなくても使えるメソッドだが、通常のindexがn回処理するのに対しbsearch_indexはlogn 2回の処理で済むので若干だが速度が上がる。

まとめ

色々とメソッドを書いたものの、ぶっちゃけAtCorderは「いかに簡単なメソッドを使ってアルゴリズムを組むか」がポイント。高得点者&回答時間短い人の回答を見るとそれがよくわかる。。。