AtCoder Beginner Contest388振り返り

AtCoder ABC388振り返り

ABC3完。パフォーマンス328。新Rating290（+5）。 Cが解けたのは上出来。でも二分探索は練習不足で時間がかかり過ぎてしまったので、パフォーマンスはあまり高くなかった。 もっとサクサク書けるように練習しよう。

B問題

atcoder.jp

提出コード

n, d = gets.split.map(&:to_i)
a = n.times.map { gets.split.map(&:to_i) }
ans = []
d.times do |k|
  a.each do |t, l|
    ans << (t * (l+k+1))
  end
  puts ans.max
end

修正コード

配列用意しなくてもmapを使えばさらにすっきりする。 最初からこっちで書けるようにしよう。

n, d = gets.split.map(&:to_i)
a = n.times.map { gets.split.map(&:to_i) }
d.times do |k|
  max_weight = a.map {|t, l| t * (l+k+1)}.max
  puts max_weight
end

C問題

atcoder.jp

提出コード

n = gets.to_i
h = Hash.new { |h, k| h[k] = [] }
a = gets.split.map(&:to_i)
a.each_with_index do |val, i|
  h[val] << i
end
cnt = 0
a.each do |i|
  x = a.bsearch { |j| j >= (i * 2) }
  next unless x
  cnt += (n - h[x][0])
end
puts cnt

hashを使ったためコードが長く少しみづらい。 bsearch_indexを使用すればhashを準備する必要がなくなる。

修正コード

bsearch_indexを使った解法。

n = gets.to_i
a = gets.split.map(&:to_i)
cnt = 0
a.each do |val|
  j = a.bsearch_index { |x| x >= val * 2 }
  next unless j
  cnt += n - j
end
puts cnt

もしくはカウントに直接足してしまう書き方。 || nでnilの場合のケアが必要。1行で書けるのですっきりする。

n = gets.to_i
a = gets.split.map(&:to_i)
cnt = 0
a.each do |val|
  cnt += n - (a.bsearch_index { |x| x >= val * 2 } || n)
end
puts cnt

bserchメソッド

条件を満たす値を二分探索で検索。 bsearchはその値、bsearch_indexはその値の添字を返す。 要素が見つからない場合はnilを返す。

irb(main):>ary = [0, 4, 7, 10, 12]
irb(main):> ary.bsearch {|x| x >= 7 }
=> 7

irb(main):> ary = [0, 4, 7, 10, 12]
irb(main):> ary.bsearch_index {|x| x >= 7 }
=> 2

irb(main):> ary = [0, 4, 7, 10, 12]
irb(main):> ary.bsearch {|x| x >= 15 }
=> nil

rurema.clear-code.com

精進進捗

今日までに合計265問（内C107問）解いた。 先週はあまり練習できなかったな。