AtCoder-ABC203 C - Friends and Travel costs【Python解答例】

AtCoder Beginner Contest203のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 203（Sponsored by Panasonic） - AtCoder

AtCoder Beginner Contest203 C - Friends and Travel costs

C - Friends and Travel costs

問題文

10^100+1 個の村があり、それぞれ村 0, 村 1, …, 村 10^100 と番号がついています。0 以上 10^100−1 以下の全ての整数 i について、村 i で 1 円を払う事で村 (i+1) に移動することができます。 それ以外の移動方法はありません。

太郎君は初め K 円を持った状態で村 0 におり、その後、可能な限り大きな番号の村まで進もうとします。
太郎君には N 人の友達がいます。i 人目の友達は村 Ai にいて、太郎君が村 Ai に着いたときに Bi 円を太郎君に渡します。
太郎君が最終的にたどり着く村の番号を求めてください。

制約

・1≤N≤2×10^5
・1≤K≤10^9
・1≤Ai≤10^18
・1≤Bi≤10^9
・入力は全て整数である。

解答例

n, k = map(int,input().split())

AB = []
for i in range(n):
    a, b = map(int,input().split())
    AB.append([a,b])

AB.sort()

ans = k
for i in range(n):
    if ans < AB[i][0]:
        break
    else:
        ans += AB[i][1]

print(ans)

解説

1円払うことでi番目の村からi+1番目の村に移動することができます。
Ai番目の村にいる友人からBi円貰えるとき、どの村まで到達できるか答える問題です。

配列ABをソートすることで、お金を貰える地点をスタート地点から近い順番に並び替えました。

ソートを終えたあとでお金を貰える地点についてループさせて調べます。
ans変数は解答である到達できる村の番号で、最初k円持っているのでkを代入しました。

このansより次の友人がいる村が遠いとき、これ以上お金は増えないのでansまでしか到達できないことが確定します。
それ以外のとき友人がいる村に到達できますので、貰えるお金の分だけansを足していきました。

このループを抜けたあとは到達できる村の番号がansに代入されていますので、これを出力すればOKです！

ABC203の関連記事はこちら
ebisuke33.hatenablog.com