AtCoder Beginner Contest 130

Jun 17, 2019 01:44 · 755 words · 2 minute read

AtCoder Beginner Contest 130

これまた出場できませんでした(・ω<) てへぺろ
(野球観戦などしていたので)

帰ってきてから解いたものを書く。

A - Rounding

問題文をちゃんと読めるかという読解力が問われる問題。

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

if x < a
    puts 0
else
    puts 10
end

B - Bounding

超えるまで何回足せるか実際に数える。

n, x = gets.strip.split.map(&:to_i)
ls = gets.strip.split.map(&:to_i)

ans = 1
now = 0
ls.each do |i|
    now += i
    break if x < now
    ans += 1
end

puts ans

インクリメントをnow++みたいに書いて無限にエラーになった。

C - Rectangle Cutting

えーこれむずそうと思ったけど目を凝らしてみるとそうでもなかった。

点(x, y)と長方形の中心を通る直線で分割すれば必ず半分にできるので
面積の大きくない方の面積の最大値は、元の長方形の面積の半分になる。

点(x, y)が長方形の中心だった場合は縦横で分割できるので2通りある。
それ以外のときは、(x, y)と中心を通るような直線は一意に決まる。

面積を求めているところのw * h / 2.0を最初w * h / 2と書いていて、
1ケースだけWAを食らってしまった。

w, h, x, y = gets.strip.split.map(&:to_i)

s = w * h / 2.0
is_center = x * 2 == w && y * 2 == h

puts "#{s} #{is_center ? 1 : 0}"

D - Enough Array

問題見た瞬間、あーこれ尺取り法と思って実装考えたけど、尺取り法なんもわからんなので結局ググった。

恒例のけんちょんさんのQiitaの記事を参考にして実装した。

n, k = gets.strip.split.map(&:to_i)
as = gets.strip.split.map(&:to_i)

ans = 0
sum = 0
right = 0
n.times do |left|
    while right < n && sum < k
        sum += as[right]
        right += 1
    end

    # rightを限界まで動かしてもsumがkより小さければ
    # leftを動かしても無駄なので終了
    break if sum < k

    ans += n - right + 1

    if right == left
        right += 1
    else
        # leftが次の値になる前の準備
        sum -= as[left]
    end
end

puts ans

E問題, F問題

ノータッチ\(^o^)/

DPは言わずもがな、尺取り法と累積和がめちゃくちゃ苦手だなって再認識した。

逆にいうと、あとは尺取り法と累積和と初歩的なDPが確実に書けるようになれば目標に届く気もする(⁎˃ᴗ˂⁎)