新しく怒り出す学生がいなくなるまでの最短時間を求める C++ プログラム

問題概要

長さ n の文字列 S があり、'A' または 'P' の 2 種類の文字のみで構成されているものとします。一列に並んだ n 人の学生がおり、S[i] = 'A' ならば i 番目の学生は「怒っている」状態、'P' ならば「忍耐強い」状態を表します。

インデックス i にいる怒った学生は、毎分インデックス i+1 にいる忍耐強い学生を叩きます。ただし、最後の学生は、たとえ怒っていても誰も叩くことができません。また、忍耐強い学生は叩かれた瞬間から、自分自身も怒り出します。このとき、「新しく怒り出す学生がいなくなるまで」にかかる最小の時間(分)を求めるのが本問題です。

例えば、入力が S = "PPAPP" の場合、出力は 2 になります。1 分後には文字列は "PPAAP" となり、さらに 2 分後には "PPAAA" となります。これ以降、新しく怒り出す学生はいないため、答えは 2 分です。

解法の手順

この問題は、以下の手順に従うことで効率的に解けます。

• 文字列を右から左へ走査します。
• 'P' に遭遇した場合は、カウンタ cnt を 1 増やします。
• 'A' に遭遇した場合は、現在の cnt とこれまでの ans の最大値を ans として更新し、cnt を 0 にリセットします。
• 走査が終わった時点の ans が答えになります。

このアルゴリズムが成り立つ理由は、ある怒った学生から怒りが右方向へ伝播していくのにかかる時間が、その直後に続く連続した 'P' の個数と等しいという性質があるためです。したがって、各 'A' の右側にある連続する 'P' の数をすべて調べ、その最大値を取ればよいことになります。

n := S のサイズ
ans := 0, cnt := 0
i := n - 1 で初期化し、i >= 0 の間、i を 1 ずつ減らしながら繰り返す:
    もし S[i] が 'P' なら:
        cnt を 1 増やす
    そうでなければ:
        ans := ans と cnt の最大値
        cnt := 0
ans を返す

C++ 実装例

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

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

int solve(string S) {
    int n = S.size();
    int ans = 0, cnt = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (S[i] == 'P') {
            cnt++;
        } else {
            ans = max(ans, cnt);
            cnt = 0;
        }
    }
    return ans;
}

int main() {
    string S = "PPAPP";
    cout << solve(S) << endl;
}

入力

PPAPP

出力

2

計算量

このアルゴリズムは文字列を一度だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) であり、非常に効率的です。