Python3で解く AtCoder Beginner Contest 183 D - Water Heater

単純に与えられた開始タイミングと終了タイミングで使う量をうまく記録して、頭から順番にを超えないかどうかっていうこと

目次

概要

問題

• 時間あたりのお湯の供給量の限界は
• 人いる
• 番目の人は以上未満の時刻でだけお湯を使う。
• 計画がクエリで与えられるので実現可能かを判断して

---

解くときに考えた内容

• すべての時刻においてどれだけ使うかを把握したいのですべての時間分の要素数の配列を用意する。
• すべてのクエリ（人分の予定）分以下を行う。
  • 使い始めの時刻に使うお湯の量をプラスする。
  • 使い終わりの時刻に使ってたお湯の量をマイナスする。
• このようにしておけば、時刻が若い順に足し合わせしていったときにある時刻時点でどれだけお湯を使うかがわかる。
• 実際に最終的にすべての時刻におけるお湯がどれだけ使うことになるかの配列自体は不要で、あるタイミングでお湯の供給量の限界であるを超えたら終わり。そうならなかったらOK。という流れ。

---

コード

n, W = map(int, input().split())
L = [0] * (2*10**5+1)
# ある時点で使う量を先頭からの足しあわせで表現するので
# 使い始めのタイミングsで+p
# 使い終わりのタイミングtで-p（頭から足して至ったときにt時点でpだ使わなくなるので）
for _ in range(n):
    s, t, p = map(int, input().split())
    L[s] += p
    # t時点で使わなくなる分
    L[t] -= p
# すべての時間帯の使う量の完全なリストを持たない場合
# ある時点での使う量がWをこえるか
now = 0
for l in L:
    now += l
    # ある時点での使う量がWを超えたら終わり
    if now > W:
        print('No')
        exit()
# 最後まで超えなかったらOK
print('Yes')

もし、すべての時間帯の使う量完全なリストを持ちたいならこんな感じにすればいい。今回はその必要はない。

# すべての時間帯の使う量完全なリストを持つ場合
for i in range(len(L)-1):
    L[i+1] += L[i]
print('Yes' if all(l <= W for l in L) else 'No')

---

参考になる書籍

• 問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

とうとう発売され自分の手元にも来た（2020-10-03）。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う（答え合わせできるのはありがたい）。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

７章までは別記事に残してある。 blacktanktop.hatenablog.com