AtCoder-ABC185 A - ABC Preparation / B - Smartphone Addiction【Python解答例】

先日AtCoder Beginner Contest185に出場しました。
何とかC問題まで解くことができましたので、今回はAおよびB問題についての解答例として記事にしていきたいと思います。
AtCoder Beginner Contest 185 - AtCoder

AtCoder Beginner Contest185 A - ABC Preparation

A - ABC Preparation

問題文

高橋君は、プログラミングコンテストを何回か開くことにしました。
コンテストを1回開くには、100点問題、200点問題、300点問題、400点問題が1問ずつ必要です。
100,200,300,400点問題の案がそれぞれA1,A2,A3,A4個あるとき、コンテストを最大で何回開けるでしょうか？
なお、同じ問題案は1度しか使えません。

制約

・1≤Ai≤100(1≤i≤4)
・入力は全て整数

解答例

a = list(map(int,input().strip().split()))

a.sort()

print(a[0])

解説

問題分からコンテストの最大開催回数はA1～A4の最も小さい数字となります。
したがって入力をリスト化し、ソートします。
ソートした後にリストの最初の要素を出力すれば、それが最小の数字なのでACでした。

AtCoder Beginner Contest185 B - Smartphone Addiction

B - Smartphone Addiction

問題文

高橋君のスマートフォンのバッテリー容量はN[mAh] であり、時刻 0.5,1.5,2.5,…に、つまり時刻n+0.5(nは整数)を迎える度にバッテリー残量が1[mAh] ずつ減少します。
高橋君はスマートフォンを満充電した状態で時刻0に外出し、途中でM回カフェを訪れ、時刻Tに帰宅します。i回目に訪れるカフェには時刻Aiから時刻Biまで滞在します。カフェに滞在している間はスマートフォンを充電するため、バッテリー残量は減少せず、代わりに時刻n+0.5(nは整数)を迎える度に1[mAh] ずつ増加します。ただし既にバッテリー残量がバッテリー容量と等しい場合、バッテリー残量は増えも減りもしません。
高橋君が途中でスマートフォンのバッテリー残量が0になることなく帰宅することができるかを判定してください。

制約

・1≤N≤10^9
・1≤M≤1000
・1≤T≤10^9
・0

解答例

n, m, t = map(int,input().strip().split())
ab = []
for i in range(m):
    array = list(map(int, input().strip().split()))
    ab.append(array)

can = 1
n_max = n
n = n - ab[0][0] # (※1)
if n <= 0:
    n = 0
    can = 0
n += ab[0][1] - ab[0][0] # (※2)
if n >= n_max:
    n = n_max
for i in range(1,m): # (※3)
    n -= ( ab[i][0] - ab[i-1][1] )
    if n <= 0:
        n = 0
        can = 0
    n += ab[i][1] - ab[i][0]
    if n >= n_max:
        n = n_max
n = n - (t - ab[m-1][1])
if n <= 0:
    can = 0

if can == 1:
    print("Yes")
else:
    print("No")

解説

B問題は非常に悩みました。最初は方針が悪く制限時間を超えTLEとなりました（NG例として後で記載します）。
カフェをおとずれたタイミングを表す入力Ai,Biは 0 < A1 < B1 < A2 < B2 < A3 < B3 < ⋯ < AM < BM < Tという条件がありましたので、次のようにプログラミングしました。

1.時刻0から最初にカフェに訪れる時刻A1までの間に減少するバッテリー量を計算する。(※1)
2.カフェに滞在している時間(B1 - A1)に増加するバッテリー量を計算する。(※2)
3.カフェを離れてから、次のカフェに到着する時間(A2 - B1)からバッテリーの減少量を計算する。(※3)
4.次のカフェの滞在時間(B2 - A2)からバッテリーの回復量を計算する。
5.上記の3と4を繰り返すと、最後のカフェを離れる時刻Bmのバッテリー残量が求まる。
6.最後のカフェを離れてから帰宅するまでの時間(t - Bm)だけバッテリー量を減少させる。
以上の、1～6を行うことで、バッテリー残量の増減を把握することができます。

注意点は問題文にあるように、バッテリー残量は0以下にはならず、初期条件のN以上にもならないように条件を追加しています。
バッテリーが0になるか判断するためcanフラグを作成し、バッテリーが0になればcanフラグも0にしています。
最後にcanフラグが1なら、バッテリーが0にならなかったことなのでYesを出力し、canフラグが0ならNoを出力しています。
何度も同じプログラムを書いており、もっとスマートに書くことができると思いますが（反省です…）、こちらの解答でもACでした。

NG例

n, m, t = map(int,input().strip().split())
ab = []
for i in range(m):
    array = list(map(int, input().strip().split()))
    ab.append(array)

n_max = n
can1 = 1
for i in range(t):
    can = 0
    for j in range(m):
        if i >= ab[j][0] and i < ab[j][1]:
            if n < n_max:
                n += 1
            can = 1
            break
    if can == 0:
        n -= 1
        if n <= 0:
            n = 0
            can1 = 0

if can1 == 1:
    print("Yes")
else:
    print("No")

TLEでNGとなった例です。
最初は0からtまでの時刻に注目したループをまわし、カフェに滞在していればバッテリー残量を+1、そうでなければ-1というプログラムを書きました。
10^9程度に抑えるべき計算量が、時刻tの範囲10^9とカフェを訪れる回数10^3をかけて10^12になっていたと思います（あまり詳しくないので間違っていたら申し訳ないです）。
もともとの方針がよくないと、仮に内容は正しくてもNGとなってしまうという基本的なミスでした。
判断力を磨いていかないといけないですね…（コンテストに出るたび毎回反省です）

C問題についても試行錯誤がありましたので、その内容は次回の記事にまとめていきたいです。