Pythonで一列の中で取り得る位置の数を求めるプログラム

数値 n、p、q が与えられているとします。あなたは n 人が並んでいる列の中に立っており、自分が何番目にいるかは正確には分かりません。ただし、前方には少なくとも p 人、後方には最大でも q 人いることは分かっています。このとき、自分が立ち得る位置の候補が何通りあるかを求めるのがこの問題です。

例として、入力が n = 10、p = 3、q = 4 の場合を考えてみましょう。合計 10 人が並んでおり、前方に最低 3 人、後方に最大 4 人いるため、立つことのできる位置はインデックス [0, 1, 2, 3, 4] の 5 箇所となります。たとえばインデックス 0 の位置では、前方に 9 人、後方に 0 人がいることになります。

解法のアプローチ

この問題の解法は非常にシンプルで、min(q+1, n-p) を返すだけで答えが求まります。

なぜこの式で求まるのか

位置を 0 始まりのインデックスで考えると、次の 2 つの条件が成り立ちます。

• 前方に少なくとも p 人いる → 自分の位置は p 以上でなければならず、候補は最大で n − p 個
• 後方に最大 q 人しかいない → インデックス i の位置に立つと後方には n − 1 − i 人いるため、i ≥ n − 1 − q が必要となり、候補は最大で q + 1 個

したがって、両方の条件を同時に満たせる位置の数は、これら 2 つの上限のうち小さい方、すなわち min(q+1, n-p) となります。

実装例

以下に Python での実装を示します。

class Solution:
    def solve(self, n, p, q):
        return min(q+1, n-p)

ob = Solution()
print(ob.solve(n=10, p=2, q=5))

入力

10, 2, 5

出力

6

この例では n = 10、p = 2、q = 5 です。前方に最低 2 人いるため候補は最大 8 個(n − p = 8)、後方に最大 5 人しかいないため候補は最大 6 個(q + 1 = 6)。両者のうち小さい方の 6 が出力されます。

計算量

時間計算量は O(1)、空間計算量も O(1) であり、単純な比較のみで解ける非常に効率的なアルゴリズムです。