ABC084 C Special Trains 解説
問題文
・駅がN個ある。
・右端の駅以外のすべての駅から、1つ次の駅に向かう電車が運行されている。
・Ciは電車が1つ次の駅に行くのにかかる時間。
・電車はSi秒後に始発が発車する。
・それ以降はFi秒ごとに電車が発車する。
・右端の駅に到達するのにかかる最小の時間はいくつか求める。
ACコード
解説
・ある駅に着いたとき、まだ始発電車が発車していないのなら、始発電車が発車するまで待つ必要がある。
・なので考えるべきは、駅に着いたときすでに始発電車が発車しているパターン。
・それぞれの電車が出発する時間は、Si + Fi * k (kは自然数) とおける。
・よって、すでに始発電車が発車しているときは、現在時刻以上の最小のSi + Fi * kを求めればよい。
解いた感想
体感難易度:☆2
実装するだけの簡単めなC問題であるはずなのに、何度もバグらせてしまった。問題文が長くかみ砕かなくてはいけない問題では、しっかりそれぞれの文字が何を表すのかメモしておく(今回のミスはその勘違い)。コードに確信が少しでも持てないなら、提出する前にいろいろなケースを考えて入力してみる。
テスト投稿
hinamel(Twitter:@nagisaatHN)の競技プログラミングやゲーム制作の精進・制作過程をメモします。
ACコード(テスト)
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<utility>
#include<functional>
#include<stack>
#include<queue>
#include<cmath>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }int main() {
}
解説
abcdefg