Pythonで指定した秒数の加算・減算だけで12時ちょうどに戻れるか判定する方法

n個の異なる秒数が配列として与えられているとします。このとき、12時ちょうどの時刻から出発し、与えられた秒数を「加算」または「減算」する操作だけを使って、再び12時に戻ることができるかどうかを判定します。ただし、与えられた秒数はすべて必ず一度ずつ使用し、それぞれについて加算か減算のどちらか一方を選ぶものとします。

たとえば、入力が seconds = [40, 90, 50] の場合、まず 40 を加算し、次に 90 を減算し、最後に 50 を加算すると差し引きが 0 になるため、答えは True になります。

解法のアプローチ

この問題は、各秒数に「+」と「−」のどちらを割り当てるかの全パターン（2ⁿ 通り）をビットマスクで総当たりすることで解けます。手順は以下のとおりです。

• size := 2^(seconds 配列の長さ) とする
• c を 0 から size − 1 まで繰り返す
  • add := 0 で初期化する
  • j を 0 から seconds のサイズ − 1 まで繰り返す
    • c AND (2^j) が 0 以外の場合：add := add + seconds[j]
    • それ以外の場合：add := add − seconds[j]
  • add が (24 × 60) で割り切れる場合は True を返す
• すべてのパターンを試しても条件を満たさなければ False を返す

ポイントは、時計の針が一周すれば元の時刻に戻るという性質です。加減算の合計値が時計1周分の周期（ここでは 24 × 60）の倍数になっていれば、開始時刻である12時に戻れたことになります。

実装例

以下の実装を見ると理解が深まります。

def solve(seconds):
    size = 2**len(seconds)
    for c in range(size):
        add = 0
        for j in range(len(seconds)):
            if c & (1 << j):
                add += seconds[j]
            else:
                add -= seconds[j]
        if add % (24 * 60) == 0:
            return True
    return False

seconds = [40, 90, 50]
print(solve(seconds))

入力

[40,90,50]

出力

True

計算量について

この手法の時間計算量は O(2ⁿ × n)、空間計算量は O(1) です。符号の組み合わせが要素数に対して指数的に増えるため、n が小さい場合に有効なアプローチとなります。