Pythonで紙幣の両替にかかる最短時間を求める方法

問題の概要

n人のレジ係が紙幣の両替業務を行っているとします。現時点で、i番目のレジ係の前には k[i] 人のお客様が並んでおり、その列に並ぶ j 番目のお客様は m[i,j] 枚の紙幣を持っています。ここで求めたいのは、自分の紙幣の両替が最も早く完了するのはどのレジ係なのか、その最短時間です。ただし、次の条件があるものとします。

• レジ係が1枚の紙幣をスキャンするのに 5秒 かかる
• 1人分の紙幣のスキャンが完了した後、両替処理に 15秒 かかる

例として、入力が n = 6、k = [12, 12, 12, 12, 12, 12] の場合を考えてみましょう。

この場合の出力は 585 になります。各レジ係はお客様の紙幣1枚ごとに5秒かけてスキャンするため、「5 × m[i,j]」を加算します。さらに、レジ係はお客様1人につき15秒を要するため、「15 × k[i]」も合計に含めます。こうして各レジ係の所要時間を計算し、そのうち最小の値が答えとなります。この例では、インデックス5のレジ係（m[5]）が最短の585秒となりました。

解決のための手順

この問題は、以下のステップで解くことができます。

• n := k のサイズ

• minimum := 99999（十分に大きい値で初期化）

• i を 0 から n-1 まで繰り返す：

  • temp := k[i] × 15

  • j を 0 から k[i]-1 まで繰り返す：

    • temp := temp + m[i][j] × 5

  • もし temp < minimum ならば：

    • minimum := temp

• minimum を返す

このアルゴリズムの計算量は O(総紙幣枚数) であり、非常にシンプルかつ効率的です。

実装例

理解を深めるために、以下のPythonでの実装を見てみましょう。

def minTimeToExchange(k, m):
    n = len(k)
    minimum = 99999
    for i in range(n):
        temp = k[i] * 15
        for j in range(k[i]):
            temp += m[i][j] * 5
        if temp < minimum:
            minimum = temp
    return minimum

k = [12, 12, 12, 12, 12, 12]
m = [
    [7,8,9,7,9,6,10,9,9,6,7,8],
    [10,7,10,9,8,9,9,9,9,6,5,6],
    [9,8,8,9,8,6,7,9,10,6,6,7],
    [7,6,9,6,6,9,8,9,6,6,8,9],
    [9,8,7,6,5,10,8,10,7,6,6,8],
    [8,7,6,5,7,9,7,9,6,5,5,7]]
print(minTimeToExchange(k, m))

入力

[12, 12, 12, 12, 12, 12],
[[7,8,9,7,9,6,10,9,9,6,7,8],
[10,7,10,9,8,9,9,9,9,6,5,6],
[9,8,8,9,8,6,7,9,10,6,6,7],
[7,6,9,6,6,9,8,9,6,6,8,9],
[9,8,7,6,5,10,8,10,7,6,6,8],
[8,7,6,5,7,9,7,9,6,5,5,7]]

出力

585