C++で指定時間後のキューの並びを求める方法

問題概要

この問題では、「M」と「F」の2種類の文字のみで構成される文字列と、時間 t が与えられます。指定された時刻におけるキュー（待ち行列）の並びを求めることが課題です。

この文字列は、バスに乗り込むために一列に並んだ人々を表しています。列の中の男性はみな紳士的で、自分の後ろに女性が並んでいることに気づくと、すぐにその女性と順番を交換します。バスの発車まであと t 単位時間があり、1回の交換につき1単位時間がかかります。つまり、バスが到着したときの列の状態をシミュレーションによって求める必要があるのです。

具体例で理解しよう

入力 : queue = "MFMMFF" , t = 3
出力 : FFMFMM

解説 −

T = 0 → 1 の間に、位置1の「M」が位置2の「F」と入れ替わり、位置4の「M」が位置5の「F」と入れ替わります。キューは "FMMFMF" になります。
T = 1 → 2 の間に、位置3の「M」が位置4の「F」と入れ替わり、位置5の「M」が位置6の「F」と入れ替わります。キューは "FMFMFM" になります。
T = 2 → 3 の間に、位置2の「M」が位置3の「F」と入れ替わり、位置4の「M」が位置5の「F」と入れ替わります。キューは "FFMFMM" になります。

解法のアプローチ

この問題に対するシンプルな解法は、キューを表す文字列を t 回走査することです。各走査の際に「MF」という隣接ペアを見つけたら、M と F の位置を交換します。これを指定回数だけ繰り返し、最終的な文字列を返します。

ここで注意すべき点は、同じ単位時間内に交換済みのペアを再度処理しないことです。1人の人が1単位時間に複数回移動することはできないためです。実装では、交換を行った後にインデックスを1つ余分に進めることで、この条件を正しく満たしています。

実装例

以下は、上記の解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;
string rearrageQueue(int n, int t, string queue) {
    for (int i = 0; i < t; i++)
        for (int j = 0; j < n - 1; j++)
            if (queue[j] == 'M' && queue[j + 1] == 'F') {
                queue[j] = 'F';
                queue[j + 1] = 'M';
                j++;
            }
   return queue;
}
int main() {
   int n = 6, t = 3;
   string queue = "MFMMFF";
   cout<<"時間経過後のキュー : "<<rearrageQueue(n, t, queue);
   return 0;
}

出力

時間経過後のキュー : FFMFMM

計算量の分析

• 時間計算量： O(t × n) — 文字列全体を t 回走査するためです。
• 空間計算量： O(1) — 入力文字列を直接書き換えるため、追加のメモリは不要です。

まとめ

この記事では、男性と女性が並ぶキューが指定時間の経過後にどのような並びになるかを求める問題を扱いました。「MF」ペアを検出して交換するというシンプルなシミュレーションにより、効率的に解答できることを確認しました。同様のパターンは、セル・オートマトンや状態遷移系のシミュレーション問題にも応用できます。