【Python】合計時間が60秒で割り切れる曲のペアを数えるアルゴリズム

曲のリストが与えられ、i番目の曲の再生時間は time[i] 秒であるとします。このとき、2曲の合計時間（秒）が60で割り切れるようなペアの総数を求めるのが本記事のテーマです。

問題の例

たとえば、time配列が [30, 20, 150, 100, 40] の場合、答えは 3 となります。条件を満たすペアは次の3つです。

• (30, 150) → 合計180秒
• (20, 100) → 合計120秒
• (20, 40) → 合計60秒

いずれも合計時間が60で割り切れることが確認できます。

解法のアプローチ

すべてのペアを総当たりで調べると計算量がO(n²)となり非効率です。そこで、各曲の「60で割った余り」をハッシュマップで管理することで、O(n)で解くことができます。

手順

1. 余りを記録するためのマップ rem を用意し、答え ans を0で初期化します。
2. time内の各要素 i について以下を処理します。
   • i が60で割り切れ、かつ 0 が rem に存在する場合：ans += rem[0]
   • それ以外で、60 - (i % 60) が rem に存在する場合：ans += rem[60 - (i % 60)]
   • i % 60 が rem に存在すればカウントを+1、なければ1で新規登録します。
3. 最後に ans を返します。

実装例

以下はPythonでの実装コードです。

class Solution(object):
    def numPairsDivisibleBy60(self, time):
        ans = 0
        remainder = {}
        for i in time:
            if i % 60 == 0 and 0 in remainder:
                ans += remainder[0]
            elif 60 - (i%60) in remainder:
                ans += remainder[60 - (i%60)]
            if i % 60 in remainder:
                remainder[i%60]+=1
            else:
                remainder[i%60]=1
        return ans

ob1 = Solution()
print(ob1.numPairsDivisibleBy60([30,20,150,100,40]))

入力

[30,20,150,100,40]

出力

3

まとめ

この手法では、現在処理中の曲と合計して60の倍数になる「相方となる余り」を持つ曲がすでに何曲登場したかを記録することで、1回の走査でペア数を数え上げています。これにより、総当たり方式のO(n²)から大幅に改善された時間計算量O(n)での解決が可能です。