🎃

Kickstart2020 RoundB: Bus Route

2021/05/22に公開

Python

binarysearch

kickstart

tech

問題

$N$ 個のバス路線（Bus Route）とバス旅の終了日 $D$ が与えられます。 $N$ 個のバス路線を乗り継いで、 $D$ 日までに全てのバスを乗り終えるとしたとき、最も遅いバス旅の開始日を求めるというのが問題。ただし $i$ 番目のバス路線を $X_i$ とすると、乗車可能日は $X_i, 2X_i, 3X_i$ のように $X_i$ 日毎となる。

例で考える。 $N=3, D=10$ でバス路線が $X_1=3, X_2=7, X_3=2$ と与えられたとすると、 $X_1$ の乗車可能日は $3,6,9,...$ で、同様に $X_2$ の乗車可能日は、 $7,14,21,...$ 、 $X_3$ の乗車可能日は $2,4,6,8,10,...$ となる。この場合、最も遅い開始日は $6$ で、 $X_1$ に $6$ に乗車、 $X_2$ に $7$ に乗車、 $X_3$ に $8$ に乗車すれば、 $D=10$ 日までに全ての路線に乗車することができる。しかし、これより遅い7に開始すると、 $X_1$ に $9$ 、 $X_2$ に $14$ 、 $X_3$ に $14$ に乗車することになり、 $D=10$ に間に合わない。８以降も同様。よって、この問題の解は $6$ となる。

アルゴリズムと実装

$D$ 日までに終える必要があるので、開始日の候補は $1$ から $D$ までとなる。また、上記の例で、例えば解となる日の $6$ よりも前の $5$ も同じように $D=10$ までに $X_3$ まで乗車することが可能。したがって、 $1$ から $D$ までで、 $D$ までに全路線に乗車可能な候補日区間の上限を求めれば良さそう。

ある開始日 $K$ としたとき、 $i=1$ 番目のバス路線に乗車可能な日はどう計算するか。K以上になるような $X_1$ の倍数を求める $\lceil \frac{K}{X_1} \rceil * X_1$ で計算することができる。同様に、 $i+1$ 番目のバス路線に乗車可能な日は、 $\lceil \frac{D_{i}}{X_{i+1}} \rceil * X_{i+1}$ と求めることができる。候補日の末尾 $D$ から、 $N$ 個のバス路線に乗車した日を計算して、 $N$ 番目のバス路線の乗車日がD以内かを判定する処理を繰り返して、最初に条件を満たす日が解となる。この場合の計算量は $O(DN)$ 。
Test set2では $1 \leq D \leq 10^{12}$ であるため、より効率的なBinary Searchを使って繰り返し処理を行う。通常、midの計算時にはleftとrightの合計から中間位置を計算しますが、切り捨ての結果midがleftになり、その時に条件を満たした場合に無限ループになってしまうため、midの計算は切り上げてmidが移動するようにしています。この場合の計算量は $O(N\log{}D)$ です。
Test set1とTest set2のどちらもPassedとなりました。

import math

def binary_search(N, D, Xs, left, right):
    while left < right:
        mid = (left + right + 1) // 2
        days = [math.ceil(mid / Xs[0]) * Xs[0]]
        for i in range(1, N):
            days.append(math.ceil(days[i-1]/Xs[i]) * Xs[i])
        if days[-1] <= D:
            left = mid
        else:
            right = mid - 1
    return left

T = int(input())
for t in range(1, T + 1):
    N, D = list(map(int, input().split()))
    Xs = list(map(int, input().split()))
    res = binary_search(N, D, Xs, 1, D)
    print('Case #{}: {}'.format(t, res))

問題

アルゴリズムと実装

Discussion