Pythonで2台の投票機に全員が時間内に投票できるか判定する方法

問題の概要

n人の人と、同一仕様の2台の投票機があるとします。サイズnの配列timeが与えられ、time[i]はi番目の人が投票機で投票するのにかかる合計時間を表します。同じ瞬間に各投票機を使えるのは1人だけです。さらに、投票機が稼働し続けられる最大時間を表す値xが与えられます。このとき、すべての人が時間内に投票を済ませられるかどうかを判定するのがこの問題の目的です。

たとえば、n = 3、x = 7、time = [3, 5, 3]という入力の場合、出力はTrueになります。時刻t0に0番目の人が1台目の投票機へ、1番目の人が2台目の投票機へ移動します。時刻t3で1台目が空くので、2番目の人が1台目を使い始めます。その後、時刻t5で2台目が空き、時刻t6で1台目も空くため、全員が制限時間内に投票を完了できたことになります。

解決のためのアルゴリズム

この問題は、次の手順に従って解くことができます。

• timeの全要素の合計をtotal_sumとします。
• total_sumがx以下であれば、Trueを返します（全体の作業量が1台分の上限に収まるため）。
• リストtimeを昇順にソートします。
• timeと同じサイズの配列prev_sumを0で初期化し、累積和を格納します。
• prev_sum[0]にtime[0]を代入し、以降はprev_sum[i] = prev_sum[i-1] + time[i]として累積和を求めます。
• 二重ループでiとjの組み合わせごとに、temp_sum = prev_sum[i] + (total_sum - prev_sum[j])を計算します。
• temp_sumがx以下、かつtotal_sum - temp_sumもx以下であれば、Trueを返します。
• どの組み合わせでも条件を満たさなければ、Falseを返します。

ポイントは、ソート後の累積和prev_sumを利用することで、「小さい側の先頭からi番目まで」と「大きい側の末尾からj番目より後」を一方の投票機に割り当てた場合の負荷を効率よく計算できる点です。temp_sumはその投票機の総使用時間、total_sum - temp_sumはもう片方の投票機の総使用時間に対応し、両方がx以下であれば全員が時間内に投票できることになります。

それでは、理解を深めるために実際の実装例を見てみましょう。

Pythonでの実装例

def solve(n, x, time):
    total_sum = sum(time)
    if total_sum <= x:
        return True
    time.sort()
    prev_sum = [0 for i in range(len(time))]
    prev_sum[0] = time[0]
    for i in range(1, len(prev_sum)):
        prev_sum[i] = prev_sum[i - 1] + time[i]
    for i in range(0, len(prev_sum)):
        for j in range(i + 1, len(prev_sum)):
            temp_sum = (prev_sum[i] + (total_sum - prev_sum[j]))
            if temp_sum <= x and total_sum - temp_sum <= x:
                return True
    return False

n = 3
x = 7
time = [3, 5, 3]
print(solve(n, x, time))

入力

3, 7, [3, 5, 3]

出力

True

まとめ

本記事では、2台の投票機と稼働可能時間xが与えられたときに、全員が時間内に投票できるかどうかを判定する方法を紹介しました。合計時間による早期判定、ソートと累積和の活用、二重ループによる割り当てパターンの検証という流れで実装できます。計算量はO(n²)となるため、人数がそれほど多くないケースに適したアプローチです。