RubyでAtCoder ABC279(A, B, C, D)を解いてみた

はじめに

Webエンジニアを目指して、RubyやRailsをいじってます。
今回は、RubyでAtCoder ABC279のA, B, C, Dを解きました。備忘録として解き方をまとめていきたいと思います。

A - wwwvvvvvv

a-279.rb

s = gets.chomp
puts s.size + s.count("w")

B - LOOKUP

b-279.rb

# 修正前
s = gets.chomp
t = gets.chomp
n = t.size
for i in 0..s.size - n
    if s[i..i + n - 1] == t
        puts "Yes"
        exit
    end
end
puts "No"

すごく回りくどいことしてました...

b-279.rb

# 修正後
s = gets.chomp
t = gets.chomp

puts s.include?(t) ? "Yes" : "No"

解説

tと一致する部分文字列があるかどうかを順に調べていき、一致するものがあればYesを出力して終了、最後まで一致するものがなければNoを出力します。

C - RANDOM

c-279.rb

h, w = gets.split.map(&:to_i)
s_array = Array.new(h){ gets.chomp.chars }.transpose.sort
t_array = Array.new(h){ gets.chomp.chars }.transpose.sort

puts s_array == t_array ? "Yes" : "No"

解説

列について考えるためtransposeメソッドを使って行と列を交換しています。後は、s_arrayとt_arrayそれぞれをsortした結果が一致しているかどうかを調べればOKです。

D - Freefall

d-279.rb

def f(n)
    return $b * n + $a / Math.sqrt(n + 1)
end

$a, $b = gets.split.map(&:to_i)
ans =  (0..10 ** 18).bsearch { |i| f(i) <= f(i + 1)}
puts [f(ans), f(ans + 1)].min

<追記>
コメントでいただいた別解になります。

別解

a, b = gets.split.map(&:to_i)

h = (((a.to_r / (2 * b)) ** (2/3r)) - 1).to_i
f = ->(x) { b * x + a * (x + 1) ** (-0.5) }
puts (h - 5..h + 5).map { f.(_1) }.select { _1.instance_of?(Float) }.min

解説

<方針>
行った操作回数をnとすると、高橋くんが地面に到達できる時刻はbn+a/√(n+1)となります。

<実装方法>
bsearchメソッドを使って二分探索することで間に合います。また、下に凸のグラフとなるため、探すのはf(i)<=f(i+1)の部分となります。なお、aとbは関数定義でも使うために$をつけてグローバル変数にしています（A, Bのように定数にしてもできます）。

終わりに

D問題は最大が10^18+1と二分探索でも10^9くらいでTLEが微妙でしたが、間に合いました。三分探索という方法もあるみたいで、そっちの方が高速になりそうです。