Ruby で解く AtCoder ARC109 B 二分探索

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Regular Contest B - log
Difficulty: 524

今回のテーマ、二分探索

入力例 1の説明で AtCoder らしいミスリードがありますが、n + 1 の長さの丸太で 1 ～ k までの短い丸太をつくればヨシ！

Ruby

ruby.rb

n = gets.to_i
m = (1..).bsearch { _1 * (_1.next) / 2 > n.next } - 1
puts n - m + 1

bsearch.rb

m = (1..).bsearch { _1 * (_1.next) / 2 > n.next } - 1

二分探索です。1 ～ k までの短い丸太の長さの合計は、k * (k + 1) / 2 で求めます。bsearchはブロック内の条件がtrueになった最初の値を返しますので、-1 します。

range.rb

(1..Float.INFINITY)
(1..nil) # Ruby 2.6 以降
(1..)    # Ruby 2.7 以降

終端を持たない範囲オブジェクトの指定方法です。AtCoder の環境はRuby2.7ですので、いずれの書き方でもヨシ！

類題　C - Buy an Integer

AtCoder Beginner Contest C - Buy an Integer
Difficulty: 741

ruby.rb

a, b, x = gets.split.map(&:to_i)
y = (1..).bsearch { _1 * a + _1.to_s.size * b > x }
if y.nil?
  puts 0
elsif y > 1000000000
  puts 1000000000
else
  puts y - 1
end

こちらはB - logに比べ、範囲オブジェクトより低い場合と高い場合がありますので少しだけ難しくなっています。

	B - log	C - Buy an Integer
コード長 (Byte)	84	174
実行時間 (ms)	62	61
メモリ (KB)	14428	14400

まとめ

• ARC 109 B を解いた
• Ruby に詳しくなった

参照したサイト
instance method Range#bsearch
class Range