文系ギャルが0から始める競技プログラミング#23
Intro
この記事は不定期連載です。
↓最初の一本はこちら↓
文系ギャルが0から始める競技プログラミング#0
↓直前の記事はこちら↓
文系ギャルが0から始める競技プログラミング#22
・ABC123C - vsTLE
突然ですが、みなさん絶対優勝!!!って思ってるときのTLEって悲しいですよね?
悲しい気持ちを昇華するために書きます。(ネタバレ)
問題文
AtCoder社は成長し、2028年になってついに6つの都市(都市1,2,3,4,5,6)からなるAtCoder帝国を作りました!
AtCoder帝国には5つの交通機関があります。
電車:都市1から2まで1分で移動する。
1つの電車にはA人まで乗ることができる。
バス:都市2から3まで1分で移動する。
1つのバスにはB人まで乗ることができる。
タクシー:都市3から4まで1分で移動する。
1つのタクシーにはC人まで乗ることができる。
飛行機:都市4から5まで1分で移動する。
1つの飛行機にはD人まで乗ることができる。
船:都市5から6までを1分で移動する。
1つの船にはE人まで乗ることができる。
それぞれの交通機関は、各整数時刻(0,1,2,3,...)に、都市から出発します。
いま、N人のグループが都市1におり、全員都市6まで移動したいです。
全員が都市6に到着するまでに最短で何分かかるでしょうか?
なお、乗り継ぎにかかる時間を考える必要はありません。
制約
1≤N,A,B,C,D,E≤10^15
入力中の値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
A
B
C
D
E
出力
全員が都市6に移動するのに必要な最小の時間を分単位で出力せよ。
― C - Five Transportations
帝国になっちゃったか〜〜〜。
まあまあでもなんとなくしたいことはわかります。
問題を整理します。
ゴールは都市6にみんながたどり着くまでの時間を出力すること。
一番乗れる人数が少ない移動手段だけ考えます。
どうせ詰まるので、その人数だけ出発させます。
で、第一陣は5分掛けて都市6まで移動するので、その後を考えます。
つまり、出力用の変数ansの初期値は5でいいはず!!!
あとはばんばん送り込み、1分ずつ足してぱんぱかぱ〜〜んと行ったろ!とこんな感じに書きました。その時のわたしは。
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
int main(){
long long N,A,B,C,D,E;
cin >> N >> A >> B >> C >> D >> E;
long long MIN = min({A,B,C,D,E});
long long ans = 5;
while(N>0){
if(N-MIN>0){
ans = ans+1;
}
N = N-MIN;
}
cout << ans << endl;
return 0;
}
結果は…
ん…?
何回みてもTLEなので、策を練り直します。
明らかwhileでぐるぐるするには数が多すぎるんですね。
もっと簡単に…
まず乗り物が何台必要なのかを考えます。
1台で5分、2台だと6分、3台だと7分…
第n陣がつくとき、n+4分が必要なのです。
それを切り上げれば…(人なので)
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
int main(){
long long N,A,B,C,D,E;
cin >> N >> A >> B >> C >> D >> E;
long long MIN = min({A,B,C,D,E});
long long ans = 0;
ans = (N+MIN-1)/MIN+4;
cout << ans << endl;
return 0;
}
これで!!!!!!!!!!!優勝!!!!
TLE悔しいですよね。
解決してよかったぁ…。
Outro
#24に続く!(不定期連載です。)
これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。