C++で解く！面白い瞬間の間隔から試合の視聴時間を求めるアルゴリズム

n個の要素を持つ配列Aがあるとしましょう。Amalは90分間の試合を観戦したいと考えており、試合中に休憩はありません。試合の各1分は「面白い」または「退屈な」のどちらかに分類され、15分連続して退屈な時間が続くと、Amalは直ちにテレビの電源を切ります。配列Aには、面白くなる瞬間の経過時間（分）がn個記録されています。このとき、Amalが合計で何分間試合を視聴することになるのかを求めます。

例えば、入力が A = [7, 20, 88] の場合、出力は 35 になります。20分までは面白い瞬間が15分以内の間隔で訪れるため視聴を続けられますが、その後88分まで次の面白い瞬間が訪れないため、20 + 15 = 35分の時点でテレビを切ることになるからです。

解法のアプローチ

この問題の鍵となるのは、隣り合う面白い瞬間の間隔が15分を超えるかどうかという点です。間隔が15分以下であれば視聴を継続し、15分を超えた時点で「最後の面白い瞬間＋15分」が視聴終了时刻となります。最後まで15分を超える間隔が現れなかった場合は、試合終了の90分がそのまま答えになります。

手順

サイズ100の配列 a を定義する
n := A のサイズ
i := 1 で初期化し、i <= n の間 i を1ずつ増やしながら繰り返す：
    a[i] := A[i - 1]
    もし a[i] - a[i - 1] > 15 ならば：
        ループから抜ける
(a[i - 1] + 15) と 90 のうち小さい方を返す

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
    int i, a[100];
    int n = A.size();
    for (i = 1; i <= n; i++){
        a[i] = A[i - 1];
        if (a[i] - a[i - 1] > 15)
            break;
    }
    return min(a[i - 1] + 15, 90);
}
int main(){
    vector<int> A = { 7, 20, 88 };
    cout << solve(A) << endl;
}

入力

{ 7, 20, 88 }

出力

35

コードのポイント

配列の先頭 a[0] は初期値0（試合開始時点）として扱われます。そのため、最初の面白い瞬間が7分であれば、開始からの間隔は15分以内となり、問題なく視聴を続けられます。ループ途中で break が発生した場合、変数 i は15分を超える間隔が見つかった位置を指しているため、a[i - 1] が「最後の面白い瞬間」の時刻になります。そこへ15を加え、min 関数で90分との小さい方を選ぶことで、正しい視聴時間が求まります。計算量は O(n) と非常に効率的です。