時刻tで立っている観客の人数を求めるC++プログラム

3つの整数 n、k、t が与えられたとします。Amalは「メキシカンウェーブ」を分析しています。1番からn番までのn人の観客がおり、時刻0から動き始めます。時刻1で1番目の観客が立ち、時刻2で2番目の観客が立ちます。時刻kでk番目の観客が立ち、時刻(k+1)では(k+1)番目の観客が立つと同時に1番目の観客が座ります。さらに時刻(k+2)では(k+2)番目の観客が立ち、2番目の観客が座ります。このように進み、時刻nではn番目の観客が立ち、(n−k)番目の観客が座ります。時刻(n+1)以降も、(n+1−k)番目の観客が座るといった具合に波が続いていきます。

ここで求めたいのは、時刻tにおいて立っている観客の人数です。

例として、入力が n = 10、k = 5、t = 3 の場合を考えてみましょう。このとき出力は 3 になります。なぜなら、時刻5までは誰も座らないため、1番から3番までの観客がすべて立っているからです。

解法のアプローチ

この問題は、次の3つの値の最小値を取ることで解くことができます。

• t（すでに立ち上がった人数）
• k（一度に立っていられる最大人数）
• n + k − t（後半で座り始めた後の残り人数）

つまり、答えは以下の式で表されます。

return min({ t, k, n + k - t });

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
int solve(int n, int k, int t){
   return min({ t, k, n + k - t });
}
int main(){
   int n = 10;
   int k = 5;
   int t = 3;
   cout << solve(n, k, t) << endl;
}

入力

10, 5, 3

出力

3

計算量について

このアルゴリズムは単純な比較のみで構成されているため、時間計算量は O(1)、空間計算量も O(1) となります。どのような入力に対しても即座に答えを返せる、非常に効率的な解法です。