#13 - 文系出身エンジニアが競プロをやる

※このマガジンは不定期投稿です。

Intro

ちわ。今日も過去問を解きます。
今日取り組んだのは、AtCoder Beginner Contest 123のC問題です。
ジムに行きたい vs 競プロやりたい vs ギター弾きたいの三竦みになっており、1日24時間だと足りずに睡眠時間を削るハメになってます。
もっと寝たい。

C - Five Transportations

問題概要

C - Five Transportations

配点: 300点

AtCoder社の台頭から早10年、ついに6つの都市から成るAtCoder帝国になった。この帝国には5つの交通機関があり、それぞれ移動時間（1つの都市を動くのに1分かかる）は同じだがキャパシティが違う。また、都市は全て横並びに存在している。

この時N人全員が、最初の都市から最終都市に到達する最小時間を答えよ。
尚乗り継ぎ時間は考慮しなくて良い。

コード（解答）

あ、ABC123のC解けたぞ

— Ryota Ikezawa (@_pavlog) May 13, 2019

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long int ll;
#define REP(i, I, N) for (int i = I; i < N; ++i)
#define rep(i, N) REP(i, 0, N)

int main() {
    ll N, m = 1000000000000001, order = 5;
    cin >> N;
    
    vector<ll> capacities(order);
    rep(i, order) cin >> capacities[i];
    rep(i, order) m = min(capacities[i], m);

    ll ans = (N / m + (N % m == 0 ? 0 : 1) + order - 1);

    cout << ans << endl;
    return 0;
}

えっ、難しくない？最初愚直に書くかと思って考えていましたが、どうも間に合わなさそう。時間めっちゃかかりました。

考え方を変えます。この移動では、どこに一番時間がかかるかを考えます。
そこで移動時のキャパシティが最小の交通機関にフォーカスします。

    rep(i, order) m = min(capacities[i], m);

Nは人数なので、人数を最小単位で割ると良さそう。
割り切れなかったら+1してあげます。
移動する都市は4つ（5-1）、つまり4分は必ず移動に要しそう。
最後に足し合わせます。

はい、AC。
ただ難しいなこれ…、コンテスト時間内ですぐ解くの無理じゃね…
頑張ります…

Submission #5392423 - AtCoder Beginner Contest 123

Outro

元々noteにこういったメモを残すつもりはなかったんですが、以下の記事とマリー氏に触発されて、思考整理がてら残そうと思った次第です。

文系ギャルが0から始める競技プログラミング｜マリー｜note

PVは伸びなさそうなので、サムイんだろうなあ。まあ勉強のためにも、継続します。