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

はじめに

このチュートリアルでは、信号が文字列内のすべての位置に到達するまでにかかる時間を求めるプログラムについて解説します。

問題の概要

'x' と 'o' で構成された文字列が与えられます。信号は 'x' の位置から発生し、左右の両方向へ伝播していき、1単位時間ごとに隣接する 'o' を 1 つずつ 'x' へと変えていきます。ここでの課題は、文字列全体がすべて 'x' で埋め尽くされるまでに必要な合計時間を計算することです。

アルゴリズムの考え方

この問題は、連続する 'o' のブロック(区間)に着目することで効率的に解くことができます。手順は以下の通りです。

1. 文字列を先頭から走査し、連続した 'o' のブロックごとに長さをカウントします。
2. 各ブロックの左隣・右隣に 'x' が存在するかどうかを確認します。
3. ブロックの両側に 'x' がある場合、信号は両方向から同時に進むため、所要時間は「ブロックの長さ ÷ 2」を切り上げた値(ceil)になります。
4. 片側にしか 'x' がない場合や、ブロックが文字列の端にある場合は、所要時間はブロックの長さそのものになります。
5. すべてのブロックの中で最大の所要時間が、文字列全体を 'x' に変換するために必要な時間となります。

C++による実装例

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

// 合計所要時間を計算する関数
int findMaximumDuration(string s, int n) {
    int right = 0, left = 0;
    int count = 0, maximumLength = INT_MIN;
    s = s + '1'; // 番兵として末尾に 'o' 以外の文字を追加
    for (int i = 0; i <= n; i++) {
        if (s[i] == 'o')
            count++;
        else {
            if (count > maximumLength) {
                right = 0;
                left = 0;
                if (s[i] == 'x')
                    right = 1; // 右側に 'x' がある
                if (((i - count) > 0) && (s[i - count - 1] == 'x'))
                    left = 1; // 左側に 'x' がある
                count = ceil((double)count / (right + left));
                maximumLength = max(maximumLength, count);
            }
            count = 0;
        }
    }
    return maximumLength;
}

int main() {
    string str = "xooxoooxxoooxoooxooxooox";
    int length = str.size();
    cout << findMaximumDuration(str, length);
    return 0;
}

出力結果

2

コードの解説

このプログラムでは、入力文字列 "xooxoooxxoooxoooxooxooox" を例に処理を行っています。

• 番兵の追加: 文字列の末尾に '1'('o' 以外の文字)を追加することで、最後の 'o' ブロックも確実に処理できるようにしています。
• ブロックの検出: 連続する 'o' をカウントし、'o' 以外の文字に到達した時点で、そのブロックの両隣に 'x' が存在するかを判定します。
• 所要時間の計算: 両側に 'x' があれば ceil(count / 2)、片側のみなら count を所要時間とし、これまでの最大値と比較して更新します。

例えば "xoox" のようなパターンでは、2つの 'o' が左右の 'x' に挟まれているため、信号は両側から同時に進み 1 単位時間で変換が完了します。一方、"xoooxxooox" のように 3 つ連続する 'o' が挟まれている場合は、ceil(3 / 2) = 2 単位時間が必要です。サンプル入力では最大所要時間を持つブロックが複数存在するため、出力は 2 となります。

なお、入力文字列に 'o' が一切含まれない場合、maximumLength は初期値 INT_MIN のまま返される点には注意してください。実際の運用では、そのようなケースに対するガード処理を追加しておくと、より堅牢な実装になります。