Pythonでカップとソーサーを棚にきれいに配置できるか判定する方法

3種類のカップが配列 p に、ソーサーが配列 q に入っており、利用できる棚の数 m が与えられているとします。このとき、カップとソーサーを「きれいに」配置できるかどうかを判定するのが本記事のテーマです。

「きれいな配置」となるための条件

カップとソーサーの配置が整然としていると言えるのは、次の3つの条件をすべて満たす場合です。

• どの棚にも、カップとソーサーを混在させて置くことはできない
• 1つの棚に置けるカップは最大5個まで
• 1つの棚に置けるソーサーは最大10枚まで

入出力の例

たとえば、p = [4, 3, 7]、q = [5, 9, 10]、m = 11 という入力の場合、出力は True になります。理由を確認してみましょう。

• カップの合計数は 4 + 3 + 7 = 14 個。1棚あたり5個なので、必要な棚は 3 棚
• ソーサーの合計数は 5 + 9 + 10 = 24 枚。1棚あたり10枚なので、必要な棚は 3 棚

したがって、必要な棚の合計は 3 + 3 = 6 棚となり、与えられた棚の数 m = 11 よりも少ないため、True が返されます。

解法のアルゴリズム

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

1. 合計値を格納する変数 sum_p と sum_q を 0 で初期化する
2. 配列 p の全要素を sum_p に加算し、カップの総数を求める
3. 配列 q の全要素を sum_q に加算し、ソーサーの総数を求める
4. 切り上げ除算により、カップに必要な棚数 m_p を計算する
5. 同様に、ソーサーに必要な棚数 m_q を計算する
6. m_p + m_q が m 以下なら True、そうでなければ False を返す

実装例

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

def is_valid(p, q, m):
    sum_p = 0
    sum_q = 0
    for i in range(len(p)):
        sum_p += p[i]
    for i in range(len(q)):
        sum_q += q[i]
    # 切り上げ除算で必要な棚数を計算
    m_p = (sum_p + 5 - 1) // 5
    m_q = (sum_q + 10 - 1) // 10
    if m_p + m_q <= m:
        return True
    else:
        return False

p = [4, 3, 7]
q = [5, 9, 10]
m = 11

print(is_valid(p, q, m))

入力

[4, 3, 7], [5, 9, 10], 11

出力

True

コードのポイント

(sum_p + 5 - 1) // 5 のような計算は、切り上げ除算(天井関数)を実現する定番のテクニックです。整数除算演算子 // を使うことで、小数点以下を切り上げた棚数を正確に求められます。

また、Pythonでは組み込み関数 sum() と math.ceil() を使うと、より簡潔に書くこともできます。

import math

def is_valid(p, q, m):
    m_p = math.ceil(sum(p) / 5)
    m_q = math.ceil(sum(q) / 10)
    return m_p + m_q <= m

どちらの実装でも計算量は O(n + m) 程度に収まり、非常に効率的に判定できます。