第１４回日本情報オリンピック 本選（オンライン） A - 鉄道旅行 (Railroad Trip)

問題

atcoder.jp

考察

M日間の移動で各鉄道を何回利用するかをカウントし、ICカードを購入した場合としない場合で各鉄道の料金が安くなる方を選択します。

提出コード

#include <bits/stdc++.h>
using namespace std;

int M[100100];

int main(){
  int n,m;
  cin>>n>>m;

  //m+1日目の移動を入力
  int p[m];
  for(int i=0;i<m;i++){
    cin>>p[i];
  }

  //鉄道M[j]の利用回数をカウント
  for(int i=0;i<m-1;i++){
    //cout<<p[i]<<" "<<p[i+1]<<endl;
    if(p[i]<p[i+1]){
      for(int j=p[i];j<p[i+1];j++){
        M[j]++;
      }
    }
    else if(p[i]>p[i+1]){
      for(int j=p[i+1];j<p[i];j++){
        M[j]++;
      }
    } 
  }

  //運賃入力
  int a[100100];
  int b[100100];
  int c[100100];
  for(int i=1;i<n;i++){
    cin>>a[i]>>b[i]>>c[i];
  }

  //鉄道毎にカード利用／不利用で安価な方を加算
  long long ans=0;
  for(int i=1;i<=n;i++){
    if(M[i]*a[i]<M[i]*b[i]+c[i]){
      ans+=M[i]*a[i];
    }
    else{
      ans+=(M[i]*b[i]+c[i]);
    }
  }
  cout<<ans<<endl;
  return 0;
}

TLE

残念ながら大きなデータのケースでTLEしました。

鉄道の利用回数をカウントするところをいもす法を使って計算量を落とす必要がありそうです。

もう一工夫します。

修正コード

無事ACしました。

#include <bits/stdc++.h>
using namespace std;

long long M[100100];
long long MC[100100];

int main(){
  int n,m;
  cin>>n>>m;
  int p[m];
  for(int i=0;i<m;i++){
    cin>>p[i];
  }
  
  for(int i=0;i<m-1;i++){
    if(p[i]<p[i+1]){
      MC[p[i]]++;
      MC[p[i+1]]--;
    }
    else if(p[i]>p[i+1]){
      MC[p[i+1]]++;
      MC[p[i]]--;
    }
  }
  for(int i=1;i<n+1;i++){
    M[i]=M[i-1]+MC[i];
  }
   
  long long a[100100];
  long long b[100100];
  long long c[100100];
  for(int i=1;i<n;i++){
    cin>>a[i]>>b[i]>>c[i];
  }
  long long ans=0;
  for(int i=1;i<=n;i++){
    if(M[i]*a[i]<M[i]*b[i]+c[i]){
      ans+=M[i]*a[i];
    }
    else{
      ans+=(M[i]*b[i]+c[i]);
    }
  }
  cout<<ans<<endl;
  //cout<<MC[1]<<" "<<MC[2]<<" "<<MC[3]<<" "<<MC[4]<<endl;
  //cout<<M[1]<<" "<<M[2]<<" "<<M[3]<<endl;
  return 0;
}