Pythonで時刻tにスタジアムで立っている観客の数を求める方法

スタジアムにはn人の観客がおり、それぞれ1からnまでの番号が付けられています。観客は以下のルールに従って、順番に立ち上がったり座ったりします。

• 時刻t₁に、1番目の観客が立ちます。
• 時刻t₂に、2番目の観客が立ちます。
• ……
• 時刻t_kに、k番目の観客が立ちます。
• 時刻t_k+1に、(k+1)番目の観客が立ち、同時に1番目の観客が座ります。
• 時刻t_k+2に、(k+2)番目の観客が立ち、同時に2番目の観客が座ります。
• ……
• 時刻t_nに、n番目の観客が立ち、同時に(n−k)番目の観客が座ります。
• 時刻t_n+1に、(n+1−k)番目の観客が座ります。
• ……
• 時刻t_n+kに、n番目の観客が座ります。

例えば、入力が n = 11、k = 6、t = 4 の場合、出力は4になります。これは、時刻t₁で1番目の観客が立ち、時刻t₂で2番目、時刻t₃で3番目、そして時刻t₄で4番目の観客が立つためです。つまり、その時点で合計4人の観客が立っていることになり、結果は4となります。

解き方

この問題は、時刻tの値を3つのケースに分けて考えることで解決できます。

• t ≤ k の場合： 観客がまだ順番に立ち上がっている途中なので、tをそのまま返します。
• k < t ≤ n の場合： 立ち上がりが完了し、まだ誰も座り始めていないため、常にkを返します。
• t > n の場合： 観客が座り始める段階です。まず res = t − n として、すでに座った人数を求め、次に res = k − res で立っている人数を計算して返します。

このように、単純な条件分岐だけでO(1)の計算量で答えを導き出せるのがポイントです。

実装例

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

def how_many_stand(n, k, t):
    if t <= k:
        return t
    elif t <= n:
        return k
    else:
        res = t - n
        res = k - res
        return res

n = 11
k = 6
t = 4
print(how_many_stand(n, k, t))

入力

11, 6, 4

出力

4