ABC084-C-SpecialTrains を初心者目線で解いていく

問題の概要

この問題は、Atcoder国に新しくできた鉄道の各駅から最後の駅までの最短到達時間を求めるものです。各駅から次の駅までの列車は、特定の時間S[i]からF[i]秒おきに出発し、C[i]秒で到達します。

問題の解説とコード

問題の詳細

・N個の駅があり、1からNまで番号がつけられています。
・各駅iから駅i+1への列車は、開通式開始S[i]秒後に最初に出発し、その後はF[i]秒おきに出発します。
・列車の移動時間はC[i]秒です。
・各駅から最後の駅Nまでに到達する最短時間を求めます。

1.入力

int N;
cin >> N;
for(int i=0;i<N-1;i++) cin>>C[i]>>S[i]>>F[i];

Nは駅の数。
各駅から次の駅までの列車の情報C[i], S[i], F[i]を入力します。

2.各駅から最後の駅までの最短到達時間の計算

for(int i=0;i<N;i++){
    int ans=0;
    for(int j=i; j<N-1;j++){
        ans=max(ans, S[j]);
        int d= ans - S[j];
        if(d%F[j]) d = F[j] - (d%F[j]);
        else d=0;
        ans += (d+C[j]);
    }
    cout<< ans <<endl;
}

・外側のループで、各駅iから出発する列車について考えます。
・内側のループで、駅iから最後の駅Nまでの最短到達時間ansを計算します。
・ansは、次の駅に到達するための出発時間を表し、Sjと比較して大きい方を選びます。
・dは、次の列車が出発するまでの待ち時間を計算します。dがF[j]で割り切れない場合、次の列車までF[j] - (d % F[j])秒待つ必要があります。
・最終的に、ansに待ち時間dと移動時間C[j]を加えて、次の駅に到達する時間を更新します。
・各駅から最後の駅までの最短到達時間ansを出力します。

コード

C.cpp

#include <bits/stdc++.h>
using namespace std;
int C[505], S[505], F[505];

int main(){
  int N;
  cin >> N;
  for(int i=0;i<N-1;i++) cin>>C[i]>>S[i]>>F[i];

  for(int i=0;i<N;i++){ 
    int ans=0;

    for(int j=i; j<N-1;j++){
      ans=max(ans, S[j]);

      int d= ans - S[j];
      if(d%F[j]) d = F[j] - (d%F[j]) ;
      else d=0;

      ans += (d+C[j]);
    }

    cout<< ans <<endl;
  }

}

まとめ:

この解法であれば計算量が、O(N×N)で解くことができる。

参考記事

はまやんさんの記事