ABC203 C問題 Friends and Travel costs を工夫してシンプルに解く

ABC203 C問題を解説します。基本的には公式解説と同じ方針です。

atcoder.jp

問題の概要

個の村があり、1円払うと1つ先の村へ行けます。
友達がいる村 では円もらえます。
1つの村に複数友達がいる場合もあります。
何番目の村までたどり着けるか求める問題です。

難しいポイント

村の数がと多いのと、友達がいる村も最大でで多いです。
例えば、友達のいる場所と金額を連想配列に保存して、到達した村まででもらえるお金を合計するなんてことをやろうとすると、
すぐにの地獄に引きずり込まれます。

解き方の方針

私は遠回りしながら解法に辿り着きましたが、現実的な制約が友達の数に着目すると割と思いつくかもしれません。

村は1円ずつ消費しながら1個ずつ進むので、友達のいる村に到達できないことはあっても飛び越すことはないです。
5番目の村で6円持ってたら、必ず番目の村に到達できます。

まず友達の位置と友達からもらえる金額を配列に保存して、位置でソートします。
到達できる位置を変数にしておきます。
友達の配列をループして、到達できる位置と友達の位置を比較して、到達できる位置の範囲に友達がいれば、金額の分だけ到達できる位置を足します。
最後に到達できる位置を出力します。

実装

N, K = map(int, input().split())
b_arr = [list(map(int, input().split())) for _ in range(N)]

b_arr = sorted(b_arr)
until = K

for b in b_arr:
    if until >= b[0]:
        until += b[1]

print(until)

遠回りして時間をロスしてしまいました。。。
もっと問題解いてると割とすぐに気づくんだろうなと思いました。