C++で解く：クレイジーワードプロセッサの問題――n文字入力後に画面へ残る文字数を求める

要素数 n の配列 A と、もう一つの値 c が与えられているとします。システムには「クレイジーなワードプロセッサ」が存在し、文字を入力することはできますが、連続して c 秒間入力を行わないと、それまでに書いたすべての文字が消去されてしまいます。A[i] は i 番目の文字を入力した時刻を表します。このとき、n 文字すべてを入力し終えた後、画面に残る文字数の合計を求める必要があります。

例えば、入力が A = [1, 3, 8, 14, 19, 20]、c = 5 の場合、出力は 3 になります。時刻 8 の時点では画面上に 3 文字が表示されていますが、その後時刻 13 ですべての文字が消去されます。続いて時刻 14 と 19 にさらに 2 文字が入力され、最後に時刻 20 にもう 1 文字が入力されるため、結果として画面には合計 3 文字が残ることになります。

解法の手順

この問題を解くために、以下の手順に従います。

s := 1
n := 配列 A のサイズ
i := 1 で初期化し、i < n の間、i を 1 ずつ増やしながら繰り返す:
    もし (A[i] - A[i - 1]) <= c ならば:
        s を 1 増やす
    そうでなければ:
        s := 1
s を返す

このアルゴリズムの考え方は非常にシンプルです。隣接する入力時刻の差が c 秒以内であればカウントを継続し、c 秒を超えると画面がクリアされてカウントが 1 に戻ります。配列を一度走査するだけで答えが求まるため、計算量は O(n)、空間計算量は O(1) と非常に効率的です。

実装例

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

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A, int c) {
    int s = 1;
    int n = A.size();
    for (int i = 1; i < n; i++) {
        if ((A[i] - A[i - 1]) <= c) {
            s++;
        } else {
            s = 1;
        }
    }
    return s;
}
int main() {
    vector<int> A = { 1, 3, 8, 14, 19, 20 };
    int c = 5;
    cout << solve(A, c) << endl;
}

入力

{ 1, 3, 8, 14, 19, 20 }, 5

出力

3