C++で解く回転ドア問題：通過順序を求めるアルゴリズムと実装

問題の概要

時刻 t にドアの前へ到着した人物が、建物の内側に入りたい(1)のか、外側に出たい(0)のかを表すリクエスト requests[i] = [t, d] のリストが与えられます。

ドアは1つだけで、1人の通過に1単位時間かかります。このとき、次のルールに従う必要があります。

• ドアの初期状態：「内側方向(in)」から始まり、以降は最後に使用した人物の方向にセットされます。
• 1人だけの場合：ある時刻 t にドアの前にいるのが1人だけであれば、その人はすぐにドアを利用できます。
• 複数人がいる場合：2人以上が同時に並んでいるときは、より早く到着した人物が先に通り、その後は直前に使用された方向が優先されます。
• 初期状態への復帰：ドアが1単位時間の間、誰にも使われなかった場合は初期状態に戻ります。

求めるのは、各人物が実際にドアを通過した時刻と方向 [t, d] を要素とする、ソート済みのリストです。

たとえば入力が [[2,0],[3,1],[6,0],[6,1],[3,0]] の場合、出力は [[2,0],[3,0],[4,1],[6,1],[7,0]] となります。

解法の考え方

この問題は、同じ時刻に到着した人々をグループ化し、ドアの向きのルールに従って順番に通過させるシミュレーションとして解けます。手順は以下のとおりです。

1. 配列 v をソートします。
2. 結果を格納するリスト ret を作成します。
3. curr := 1、i := 0、j := 0 と初期化し、n := v のサイズとします。
4. i < n の間、次の処理を繰り返します。
   • ret が空でなく、v[i][0] と ret の最後の要素の時刻の差が 1 より大きい場合、curr := 1 にリセットします(ドアが初期状態へ戻るため)。
   • j := i + 1 とし、サイズ 2 の配列 arr を用意します。
   • arr[v[i][1]] を 1 増やし、さらに j < n かつ v[j][0] == v[i][0] の間、arr[v[j][1]] を増やしながら j を進めます(同一時刻の到着者を方向別にカウント)。
   • t := max(ret が空なら 0、それ以外は ret の最後の要素の時刻 + 1, v[i][0]) とします。
   • arr[1] と arr[0] がどちらも非ゼロの場合:
     • arr[curr] が非ゼロである限り、{t, curr} を ret の末尾に追加しながら t を 1 ずつ増やします。
     • curr を XOR 1 で反転し、残った方向についても同様の処理を行います。
   • 片方の方向にしか待ち人がいない場合は、curr := v[i][1] として、その方向の人をすべて通過させます。
   • curr := ret の最後の要素の方向とし、i := j として次のグループへ進みます。
5. 最後に ret を返します。

C++実装例

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> v) {
   cout << "[";
   for (int i = 0; i < v.size(); i++) {
      cout << "[";
      for (int j = 0; j < v[i].size(); j++) {
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]" << endl;
}
class Solution {
   public:
   vector<vector<int>> solve(vector<vector<int>>& v) {
      sort(v.begin(), v.end());
      vector < vector <int > > ret;
      int curr = 1;
      int i = 0;
      int j = 0;
      int n = v.size();
      while(i < n){
         if(!ret.empty() && v[i][0] - ret.back()[0] > 1){
            curr = 1;
         }
         j = i + 1;
         vector <int> arr(2);
         arr[v[i][1]]++;
         while(j < n && v[j][0] == v[i][0]){
            arr[v[j][1]]++;
            j++;
         }
         int t = max((ret.empty()? 0 : ret.back()[0] + 1), v[i][0]);
         if(arr[1] && arr[0]){
            while(arr[curr]--){
               ret.push_back({t, curr});
               t++;
            }
            curr = curr ^ 1;
            while(arr[curr]--){
               ret.push_back({t, curr});
               t++;
            }
         }else{
            curr = v[i][1];
            while(arr[curr]--){
               ret.push_back({t, curr});
               t++;
            }
         }
         curr = ret.back()[1];
         i = j;
      }
      return ret;
   }
};
int main(){
   vector<vector<int>> v = {{2, 0},{3, 1},{6, 0},{6, 1},{3, 0}};
   Solution ob;
   print_vector(ob.solve(v));
}

入力

{{2, 0},{3, 1},{6, 0},{6, 1},{3, 0}}

出力

[[2, 0],[3, 0],[4, 1],[6, 1],[7, 0]]

実装のポイントと計算量

このアルゴリズムの核となるのは、次の3つのポイントです。

• 同一時刻のグループ化: 同じ時刻に到着した人は、内外それぞれの人数を配列 arr でカウントし、一括して処理します。
• 方向の優先制御: 内外の両方に待ち人がいる場合は「直前の使用方向」を優先して通過させ、その後 curr ^ 1 で反対方向へ切り替えることで、「直前の方向が優先される」というルールを実現しています。
• 初期状態への復帰: 前回の通過から1単位時間以上が経過している場合は curr を 1(内側)に戻すことで、「誰にも使われなければ初期状態へ戻る」というルールを再現しています。

計算量については、ソートに O(n log n)、その後のシミュレーションは各人物を一度ずつ処理するため O(n) となり、全体の計算量は O(n log n) です。