Pythonで観覧車の利益を最大化するための最小回転数を求めるプログラム

問題の概要

4つのゴンドラを備えた観覧車を考えます。各ゴンドラには最大4人の乗客が乗ることができ、観覧車は反時計回りに回転します。1回転させるごとに「run」の運転コストがかかります。

ここで、n個の要素を持つ配列「cust」が与えられます。各要素 i は、i 回目の回転の前に観覧車の乗車を待っている人数を表します。乗客は乗車の際に「board」の料金を支払い、この料金は観覧車の反時計回り1回転分に相当します。列に並んでいる人は、どれかのゴンドラに空席があればそこへ優先的に案内され、無駄に待たされることはありません。

与えられたデータをもとに、利益を最大化できる最小の回転数を求めるのがこの問題の目的です。

具体例で理解する

入力が cust = [6, 4]、board = 6、run = 4 の場合、出力は 3 になります。

最初、6人が列に並んでいます。まず最初の4人が1つ目のゴンドラに乗り込み、残りの2人は次のゴンドラを待ちます。

観覧車が回転して2つ目のゴンドラが到着すると、その間にさらに4人が列に加わっています。そこで、待っていた2人と新しく並んだ2人の計4人が2つ目のゴンドラに乗り込みます。

観覧車がもう一度回転すると、残った3人が3つ目のゴンドラに乗り込みます。

つまり、すべての顧客にサービスを提供するには最低3回転が必要です。

このとき得られる最大利益は、(10 × 6) − (3 × 4) = 48 となります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• res := -1(答えとなる回転数)、mst := 0(これまでの最大利益)、tmp := 0(現在の累積利益)、wt := 0(待ち行列の人数)として初期化します。

• cust の各インデックス idx と値 val に対して、次の処理を繰り返します。

  • wt := wt + val(待ち人数を更新)

  • chg := min(4, wt)(今回乗せられる人数)

  • wt := wt - chg(乗せた後の残り人数)

  • tmp := tmp + chg × board − run(累積利益を更新)

  • mst < tmp であれば、res := idx + 1、mst := tmp と更新します。

• x := wt ÷ 4(商)、y := wt mod 4(余り)を求めます。

• 4 × board > run であれば、res := res + x とします。

• y × board > run であれば、res := res + 1 とします。

• res を返します。

このアルゴリズムのポイントは、入力を処理している間の各時点で累積利益を追跡し、利益が最大になった時点の回転数を記録しておくことです。それ以降の回転で利益が目減りするようであれば、余計な回転は利益を下げるだけだからです。

ループ終了後も待ち行列に人が残っている場合は、残りを4人ずつのグループに分けて判断します。x は満席ゴンドラの数、y は端数の人数です。満席1基あたりの収益(4 × board)が回転コスト(run)を上回る場合のみ x 回の追加回転を行い、端数のグループについても y × board > run が成り立つときだけ回転させます。こうすることで、赤字になる回転を避けながら利益を最大化できます。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(cust, board, run):
    res = -1
    mst = 0
    tmp = 0
    wt = 0
    for idx, val in enumerate(cust):
        wt += val
        chg = min(4, wt)
        wt -= chg
        tmp += chg * board - run
        if mst < tmp:
            res, mst = idx+1, tmp
    x, y = divmod(wt, 4)
    if 4 * board > run:
        res += x
    if y * board > run:
        res += 1
    return res

print(solve([6,4], 6, 4))

入力

[6,4], 6, 4

出力

3