文系ギャルが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でぐるぐるするには数が多すぎるんですね。
もっと簡単に…

まず乗り物が何台必要なのかを考えます。
１台で５分、２台だと６分、３台だと７分…
第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に続く！(不定期連載です。)

これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。