宿客の出入り記録からホテルの部屋の状態を復元するC++プログラム

問題概要

「L」「R」および 0〜9 の数字で構成される文字列 S が与えられます。ここでは、左から右へ向かって 0 から 9 までの番号が振られた 10 部屋を持つホテルを考えます。このホテルには左右 2 つの入口があります。

• お客様が左側の入口から到着した場合、左側の入口に最も近い空き部屋に案内されます。
• お客様が右側の入口から到着した場合、右側の入口に最も近い空き部屋に案内されます。

残念ながら部屋割りのリストは紛失してしまいましたが、すべてのお客様について「いつ到着したか」「どちらの入口から入ったか」「いつ退去したか」という記録は残っています。ホテルは当初すべて空室でした。これらの記録をもとに、部屋割りの状況を復元する必要があります。

文字列 S において、「L」は左側の入口から来たことを、「R」は右側の入口から来たことを意味します。また、数字 d は「d 番の部屋のお客様が退去した」ことを示します。最終的な部屋の状態を、長さ 10 の文字列として返してください。「0」は空室を、それ以外(「1」)は使用中を表します。

シミュレーション例

たとえば、入力が S = "LLRL1RL1" の場合、出力は "1010000011" になります。処理の流れは以下のとおりです。

• 初期状態:すべての部屋が空室 → 0000000000
• L:左側の入口から到着 → 1000000000
• L:左側の入口から到着 → 1100000000
• R:右側の入口から到着 → 1100000001
• L:左側の入口から到着 → 1110000001
• 1:1番の部屋のお客様が退去 → 1010000001
• R:右側の入口から到着 → 1010000011
• L:左側の入口から到着 → 1110000011
• 1:1番の部屋のお客様が退去 → 1010000011

解法の手順

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

n := S の長さ
a := "0000000000"
i := 0 から n 未満の間、1 ずつ増やしながら繰り返す:
   もし S[i] が 'L' なら:
      a 内で最も左にある '0' を '1' にする
   もし S[i] が 'R' なら:
      a 内で最も右にある '0' を '1' にする
   それ以外の場合:
      a の S[i] 番目を '0' にする
a を返す

C++ 実装例

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

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

string solve(string S) {
    int n = S.size();
    string a = "0000000000";
    for (int i = 0; i < n; i++) {
        if (S[i] == 'L')
            a[a.find('0')] = '1';
        else if (S[i] == 'R')
            a[a.rfind('0')] = '1';
        else
            a[S[i] - '0'] = '0';
    }
    return a;
}

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

コードのポイント

• a.find('0'):文字列内で最初に現れる「0」(= 左端の空き部屋)の位置を返します。左側の入口からの到着処理に使います。
• a.rfind('0'):文字列内で最後に現れる「0」(= 右端の空き部屋)の位置を返します。右側の入口からの到着処理に使います。
• 数字が与えられた場合は、S[i] - '0' で数値に変換し、該当する部屋を空室('0')に戻します。
• 条件分岐には else if を使用することで、「L」や「R」が入力されたときに誤って退去処理が実行されるのを防いでいます。

入出力

入力:

"LLRL1RL1"

出力:

1010000011