ABC203 C 解答

問題

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
入力は全て整数である。

考察

出来るだけ遠くの村まで移動します。まずは前提となる要素を先に処理しましょう。問題文の1文目です。

10^100+1個の村

これはとっても大きい(多い)ですね。この数字をまともに処理しようとするのはとても大変です。しかし、本問題にてこの数字は

村はどこまでも続いていて、制約の範囲内では終点となる村はない

と言い換えることができます。この条件のもとで問題を考えていきます。

まずは制約に注目しましょう。
村の番号(A)はそこそこ大きいですね。

高橋くんが1つ村を移動すると1円かかる。

みたいなことをしていますと、最後の村まで到着する頃には日が暮れてしまいます。と言いますか2021年が終わってしまいます。計算が間に合いません。

ですので、今回は友人の数(N)に注目しましょう。実際に数を入れて考えます。

あなたは現在スタート地点(村0)にいます。所持金は10円です。

一番近くの友達は村6にいるらしいです。この時、村6に着いた時の残金は

10 - 6 = 4 円

ですね。これは

6 - 0 = 6 円

移動に掛かるためです。ここで、20円もらいました。残金は24円です。次の友達は村15にいるらしいです。歩きましょう。かかる金額は

15 - 6 = 9 円

ですので、残金は 

24 - 9  = 15 円

です。ここで、3円いただいて残金は18円です。次の友達はどうやら村100にいるみたいです。そこまでにかかるお金は

100 - 15 = 85 円

です。ですが、現在は18円しか持っていませんので、残念ながら到達することはできません。なけなしのお金をはたいて限界まで進みますと、

15 + 18 = 33

となります。ということで、村33が最終的な答えとなります。

このように、現在いる村と次の村との差分が移動コストとなりまして、そのコストと所持金を比較することで移動できるかがわかります。移動できる場合（到達時に0円でも良い）には、移動費を支払いまして、現在地をその村に更新します。友達からお金を貰い次の村を目指します。一方で、お金が足りない場合には現在の所持金で行ける村まで進みます。

以上のように、

次の友達は何番目の村にいるか

に注目することで、O(N)で答えを求めることができます。

ここで注意なのが、

入力は村0に近い順番”ではない”

ということです。ということで、pair型に村とお金を入れまして、村番号の早い順に並べ替えてしまいましょう。ここのソートでO(N log N) かかってしまうので、問題の計算量にはlogがついてしまいます。しかし、これでも十分高速ですので間に合います。

また、入力される数がとても大きくint型には収まりません。ですので、long longを使ってオーバーフローに対応しましょう。

実装

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() 
{
   ll n, k;
   cin >> n >> k;
   vector<pair<ll,ll>> ab;
   rep(i, n)
   {
       ll ai, bi;
       cin >> ai >> bi;
       ab.emplace_back(ai, bi);
   }
   sort(ab.begin(), ab.end());
   ll now = 0;
   for (auto [a, b] : ab)
   {        
       if (a - now <= k)
       {
           k -= a - now;
           k += b;
           now = a;
       }
       else break;
   }
   cout << now + k << endl;
   return 0;
}

あとがき

実はこういうシミュレーションをしていく問題を実装するのが苦手だったりします。どのパラメータに注目すればよいのか、値は植木算になるのか、0の値の処理はどうするのか、など考えているとどうしても実装が遅くなってしまいます。スピーディに整理、処理できるようになりたいです。