スクリーンショット_2019-04-04_23

文系ギャルが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に続く!(不定期連載です。)

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

この記事が気に入ったらサポートをしてみませんか?