11 シミュレーション Dif:168 ABC203 C：「AtCoder 凡人が『緑』になるための精選50問詳細解説」サンプル

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/1eb1ee760594502280fd
次：https://qiita.com/sano192/items/f6e495d5d63b46bde374

【目的】
・愚直に実装するとTLE(実行時間制限超過)する問題について、工夫して計算量を減らす方法を身につける。

【概要】
一見「やるだけ」の問題に見える。が、お金がつきるまで村を1つずつ進んでいくと制約条件Kが大きすぎてTLE(実行時間制限超過)する。愚直にシミュレーションするのではなく、省略できるところは省略して計算量を減らせるような工夫ができるようになろう。

【方針】
持っているお金の分先の村へ進むことができる。

例えば100円を持っている場合
(今いる村の番号+100)番の村
へ行くことができる。

というわけで
(1)1円ずつ手持ちのお金をマイナスしながら進んで行く
(2)村に友達がいたら手持ちのお金をもらった分増やす
(3)手持ちのお金が0になったら終わり
と、愚直に実装するとまんまとTLE(実行時間制限超過)する。
手持ちのお金=Kの制約が10^9と大きすぎるからだ。

考え方を変えて
まずはじめにK円分進む(村Kに着く)
(1)進んだ間の村に友達がいるか確認する
(2)友達がいればもらえるお金分先に進む
として(1)、(2)を繰り返すと考えよう。

例えば以下の入力の場合、
3 10
3 10
45 20
11 10

友達の数：N=3
最初に持っているお金：K=10円
友達1：場所＝村3　お金=10円
友達2：場所＝村45　お金=20円
友達3：場所＝村11　お金=10円

まず友達の情報を村0に近い順に並び替える。
友達1：場所＝村3　お金=10
友達3：場所＝村11　お金=10
友達2：場所＝村45　お金=20

はじめにK円分進む。
最初に持っているお金、10円分進んで村10に着く。

(1)進んだ間の村に友達がいるか確認する
村0～村10までにいる友だちを確認する。
村3に友達1がいるから10円もらえている。

(2)友達がいればもらえるお金分先に進む
村10から10円分進んで村20に着く。

(1)進んだ間の村に友達がいるか確認する
村10～村20までにいる友だちを確認する。
村11に友達3がいるから10円もらえている。

(2)友達がいればもらえるお金分先に進む
村20から10円分進んで村30に着く

(1)進んだ間の村に友達がいるか確認する
村20～村30までにいる友だちを確認する。
この間に友達はいないからお金はもらえない。

進めなくなったため終わり。
村30が最終的にたどり着く村。

この方法なら計算回数を減らせるのでTLE(実行時間制限超過)しない。

【実装】
入力を受け取る。
友達の情報は二次元配列で受け取る。

N,K=map(int, input().split())

friends=[]
for i in range(N):
    A,B=map(int, input().split())
    friends.append([A,B])

friendsに[友達のいる村,持っているお金]を格納している。

次に友達の情報を村0に近い順に並び替える。

friends.sort()

今いる村の番号をnow_villageとする。
最初は村0なのでnow_village=0。

now_village=0

まずK円分進む(村Kに着く)
now_villageにKプラスすればOK。

now_village+=K

(1)進んだ間の村に友達がいるか確認する
(2)友達がいればもらえるお金分先に進む
ここから友達の情報を村0に近い順に一人ずつ確認し、進んだ間の村に友達がいたか確認していく。
つまりi番目の友達が今いる村より前の村にいたか確認していく。

for i in range(N):
    friend_village=friends[i][0]
    friend_money=friends[i][1]

    if friend_village<=now_village:
        now_village+=friend_money
    else:
        break

friend_villageはi番目の友達がいる村の番号。
friend_moneyはi番目の友達がくれるお金。

・friend_village<=now_villageの場合
その場所に来るまでに友だちに会っている。
お金を受け取った分更に進む。
・そうでない場合(now_village<friend_village)
i番目の友達、そしてその先の村にいる友だちにも会えないため、そこでfor文を抜ける。

最後にnow_villageを出力して終わり。

print(now_village)

【コード全文】

N,K=map(int, input().split())

friends=[]
for i in range(N):
    A,B=map(int, input().split())
    friends.append([A,B])

friends.sort()

now_village=0

now_village+=K

for i in range(N):
    friend_village=friends[i][0]
    friend_money=friends[i][1]
 
    if friend_village<=now_village:
        now_village+=friend_money
    else:
        break

print(now_village)

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/1eb1ee760594502280fd
次：https://qiita.com/sano192/items/f6e495d5d63b46bde374