C++で文字列内のすべての位置に信号が到達するまでの時間を求める方法

はじめに

このチュートリアルでは、文字列内のすべての位置に信号が到達するまでにかかる時間を計算するプログラムを作成します。まず、具体例を使って問題を説明しましょう。

扱う文字列には s と p の2種類の文字のみが含まれています。s は信号(signal)を、p は文字列内の位置(position)を表します。信号は s の地点から発生し、左右の両方向へ同時に伝わっていきます。隣の位置へ移動するのに1単位の時間がかかるものとします。私たちの課題は、すべての位置(p)を信号(s)に変換するために必要な時間を求めることです。

入出力例

• 入力: pppppspss → 出力: 5(先頭の5つのpは右側からしか信号が届かないため、5単位の時間が必要)
• 入力: pspspsps → 出力: 1(すべてのpがsに隣接しているため、1単位で済む)
• 入力: ssssss → 出力: 0(すべてがすでに信号なので、時間は不要)

解法のアプローチ

この問題は、連続する p のブロックごとに考えれば効率的に解けます。手順は以下の通りです。

1. 文字列と経過時間(初期値0)を初期化します。
2. 文字列を先頭から順に走査します。
   • 連続する p の文字数を数え、変数に保持します。
   • 現在の文字が s であり、かつ p の連続数がこれまでの最大時間より大きい場合、そのブロックの左側にも s が存在するかどうかを確認します。
   • 両側に s が存在する場合、信号は両方向から伝わるため、必要な時間は連続数の半分(切り上げ)になります。
   • 左側に s がない場合は、右側からの伝播のみとなるため、連続数がそのまま必要時間になります。
   • 各ブロックの処理後、p のカウントをリセットします。
3. 最終的に、すべてのブロックの中で最大の必要時間が答えとなります。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int timeToConvertToSignalString(string sample_string, int string_len) {
    int p_count = 0, time = 0;
    for (int i = 0; i <= string_len; i++) {
        if (sample_string[i] == 'p') {
            p_count++;
        }
        else {
            if (p_count > time) {
                bool is_present_left_side = false;
                if (((i - p_count) > 0) && (sample_string[i - p_count - 1] == 's')) {
                    is_present_left_side = 1;
                }
                if (is_present_left_side) {
                    p_count = ceil((double)p_count / 2);
                }
                time = max(time, p_count);
            }
            p_count = 0;
        }
    }
    return time;
}
int main() {
    string sample_string = "pppppspss";
    int n = sample_string.size();
    cout << timeToConvertToSignalString(sample_string, n) << endl;
    return 0;
}

実行結果

上記のプログラムを実行すると、次の出力が得られます。

5

このアルゴリズムは文字列を一度だけ走査するため、計算量は O(n)、空間計算量は O(1) となり、非常に効率的です。別の入力ケースでもプログラムを実行して、動作を確認してみてください。

まとめ

本記事では、文字列内の信号がすべての位置に到達するまでの時間を求めるアルゴリズムを学びました。ポイントは、連続するpのブロックごとに「片側だけ信号源があるか」「両側にあるか」を判定し、両側ある場合は所要時間を半分にすることです。このチュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。