【ひらめき力】ABC123 C - Five TransportationsをPythonで解いてみた

atcoder.jp

今日は上記の問題を解いてみました。
結論から言いますけど、解けませんでした。解答見ました。
ABCのC問題難しくね？

とりあえず思考過程を書いていきます。
問題は上記のリンクから見てください。

思考過程

なるほど。
まず、制約を確認してみると、すべての変数の最大値が10の15乗と。
for文で純粋に回してしまうと、TLEまっしぐらですね。
気をつけましょう。

入力例1の絵が非常にわかりやすいですね。
しかし、入力文字を使った人数推移がわかりにくいです。
文字を使った図を下に書いてみました。

すべてのパターンがこの通りではないですが、更に要点をつかみやすくなったはず。*1
要するに、この推移を続けていき、全員の移動が完了するまでの回数(TIME)をカウントすればいいわけです。

貪欲にwhileで実装してみます。

コード実装

プログラムの流れは以下のようにする。
1. 最大乗客人数をリスト化
2. 各都市にいる人数を格納するリストを作成。(最後の都市にいる人数は関係ないので、要素数5)
3. 最後の乗り物から移動させていき、リストが空になるまで回す。
4. 回した回数をカウントし、出力

N = int(input())
move_num_list = [0]*5
for i in range(5):
    move_num_list[i] = int(input())  # 最大乗客人数をリスト化

num_list = [0]*5  # 各都市にいる人数を格納するリストを作成。(最後の都市にいる人数は関係ないので、要素数5)
num_list[0] = N
time = 0
while sum(num_list) != 0:  # 最後の乗り物から移動させていき、リストが空になるまで回す。
    time += 1  # 回した回数をカウントし、出力
    for i in range(4, -1, -1):
        num = move_num_list[i]
        if i == 4:
            if num_list[i] > 0:
                if num_list[i] >= num:
                    num_list[i] -= num
                else:
                    num_list[i] = 0
        if num_list[i] > 0:
            if num_list[i] >= num:
                num_list[i] -= num
                num_list[i+1] += num
            else:
                num_list[i+1] += num_list[i]
                num_list[i] = 0

print(time)

TLEになりました。
そりゃそうですね。。
で、各最大乗車人数が1なら、単純計算、10の15乗のループですもんね。

本番でこういうのやらかしたくないですね。

解答を確認

解答としては、乗車人数の最小値を移動人数のボトルネックとするというものです。

確かに。。。。
つまり、各乗り物の移動可能な人数は、最短移動回数を求めるためには関係なく、移動可能な人数が最も小さい部分だけで決まるということですね。

これに気がつけば、
(N人がその乗り物に乗るために必要な時間)+(誰もその乗り物に乗らない空白の時間)
が解答であることがわかります。

(N人がその乗り物に乗るために必要な時間)はNを乗車人数の最小値で割って、切り上げた数。
(誰もその乗り物に乗らない空白の時間)は4分
なので、正解の実装は以下になります。

N = int(input())
move_num_list = [0]*5
for i in range(5):
    move_num_list[i] = int(input())

min_ = min(move_num_list)
print(-(-N//min_)+4)

うわぁ、短くて簡単な実装で済みました。
良い問題ですね。
解けなくて悔しいです。

ですが、移動が一番遅い部分をボトルネックとする、という考え方は他の問題でも利用できそうですね。
勉強になったので良しとしましょう。

*1 NがA以下、AがB以下の場合はこの限りではない。