【競プロ精進ログ】ABC123-C

zuka

ABCをコツコツ解いていきます。

本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC123-C「Five Transportations」です。

ポイント

良問です。この問題のポイントは，ボトルネックを探す点です。ボトルネックとは，交通機関の収容人数をホースの太さで表したときに，一番ホースの太さが細い箇所のことを指します。ホースに水を流すことを考えれば，一番細いホースの部分に依存して全体の水の流れが制限されてしまいます。

つまり，毎分ボトルネックの箇所の収容人数分だけ輸送することを考えれば十分なのです。あとは，毎分ボトルネックの箇所の収容人数送り出すときに，グループ全体が何組に分かれるかを計算して，輸送にかかる時間を計算するだけです。

まず，ボトルネックの箇所の収容人数$x$は以下の式で求められます。

続いて，グループが分かれる組数$y$は以下の式で求められます。

ただし，$\left\lceil \cdot \right\rceil$は天井関数を表します。最後に，輸送にかかる時間$t$は，最初の組は$5$分で都市6に到着し，最初の組が出発してから最後の組が出発するまで$y-1$分かかりますので，結局以下のようにして求められます。

なお，天井関数に関しては以下の記事をご覧ください。

あわせて読みたい

【c++で楽しく実装！】天井関数 本記事では，天井関数の簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は，以下の目次をご覧ください。 目次へジ...

実装

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

// 天井関数
ll my_ceil(ll a, ll b){
  return (a + b - 1) / b;
}

// オーバーフローに注意
ll N, A, B, C, D, E;

int main(){
  cin >> N >> A >> B >> C >> D >> E;
  // t = 5 + (y - 1)をそのまま実装
  cout << 5 + (my_ceil(N, min({A, B, C, D, E})) - 1) << endl;
}