Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

【AtCoder】ABC183のD問題をRubyで解く

茶色コーダーがABC183のD問題をRubyで解いてみました。

問題

AtCoder Beginner Contest 183

D - Water Heater

給湯器が $1$つあり、毎分$W$リットルのお湯を供給することができます。
$N$人の人がいます。$i$番目の人は時刻$S_i$から$T_i$までの間(時刻$T_i$ちょうどを除く)、この湯沸かし器で沸かしたお湯を毎分 $P_i$リットル使おうと計画しています。お湯はすぐ冷めてしまうので、溜めておくことはできません。
すべての人に計画通りにお湯を供給することはできますか?

制約

$1 \leq N \leq 2 \times 10^5$
$0 \leq S_i \leq 2 \times 10^5$
$1 \leq W, P_i \leq 10^9$
入力はすべて整数

入力

$N$ $W$
$S_1$ $T_1$ $P_1$

$S_N$ $T_N$ $P_N$

回答

nw = gets.chomp.split.map(&:to_i)
n = nw[0]
w = nw[1]

# 時間ごとの使用水量を格納する配列
a = Array.new(200005, 0)

n.times do
    stp = gets.chomp.split.map(&:to_i)
    s = stp[0]
    t = stp[1]
    p = stp[2]

    # 「累積和を格納する配列」にするための準備
    a[s] += p
    a[t] -= p
end

result = true

# 累積和を格納する
200001.times do |i|
    if a[i] > w
        result = false
        break
    end
    a[i+1] += a[i]
end

puts result ? "Yes" : "No"

考え方

累積和を使います。
ただし初めから求めるのではなく、後でやるという点に注意します。

  1. 時間ごとの使用水量を格納する配列を用意する
  2. 使い始め時点と使い終わり時点のみ使用水量を増減させる
  3. 時間ごとに使用水量の累積和を計算する

時間ごとの使用水量を格納する配列を用意する

$T_i \leq 2 \times 10^5$ なので、$200001$個以上の要素を持つ配列を用意します。

使い始め時点と使い終わり時点のみ使用水量を増減させる

前述した通り、初めは累積和を求めないことがポイントです。
最初から求めてしまうと、実行時間が足りなくなります。

まずは$N$人分の情報が入力される際、使い始め時点と使い終わり時点の使用水量を増減させるのみに留めます。
具体的には以下のようにします。

  • 使い始める時点の使用水量を増やす
  • 使い終わる時点の使用水量を減らす

時間ごとに使用水量の累積和を計算する

あとは普段通りに累積和を求めていきます。
$W$を超えていないか判定をしていけばOKです。

感想

自分は初めから累積和を求めにいって、実行時間が足りずACできませんでした。泣
使用水量を使い始めだけ増やして、使い終わりだけ減らすというメモのような形にして後でまとめて帳尻合わせする。
なるほどな~その手があったか~という感じです。

yuya_yuzen
九州工大 B4 | 春から新卒ITエンジニア
https://yuya-yuzen.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away