C++で順列（Permutation）に対するクエリを処理する方法

1からmまでの正整数を要素とする配列queriesが与えられたとき、すべてのクエリqueries[i]（iは0からn-1まで、nはqueriesのサイズ）を以下のルールに従って処理することを考えます。

• 初期状態では、順列はP=[1,2,3,...,m]となっています。

• 現在のiに対して、順列Pの中でqueries[i]が存在する位置（インデックスは0始まり）を探し、その要素を順列Pの先頭へ移動させます。

そして、与えられたすべてのクエリに対する結果を格納した配列を返す必要があります。

具体例で確認する

たとえば、入力がqueries = [3,1,2,1]、m = 5である場合、出力は[2,1,2,1]になります。これは、クエリが次のように処理されるためです。

• i = 0のとき：queries[i]=3、P=[1,2,3,4,5]。Pの中で3の位置は2なので、3を先頭へ移動するとP=[3,1,2,4,5]となります。

• i = 1のとき：queries[i]=1、P=[3,1,2,4,5]。Pの中で1の位置は1なので、1を先頭へ移動するとP=[1,3,2,4,5]となります。

• i = 2のとき：queries[i]=2、P=[1,3,2,4,5]。Pの中で2の位置は2なので、2を先頭へ移動するとP=[2,1,3,4,5]となります。

• i = 3のとき：queries[i]=1、P=[2,1,3,4,5]。Pの中で1の位置は1なので、1を先頭へ移動するとP=[1,2,3,4,5]となります。

• 最終的に、結果を格納した配列は[2,1,2,1]となります。

解法のアプローチ

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

• 結果を格納するための配列retを定義します。

• 順列を保持するための配列vを定義します。

• i := 0から始めて、iがm未満である間、iを1ずつ増やしながら次の処理を繰り返します。

  • vの末尾にi + 1を挿入します。

• q内の各値xに対して、次の処理を実行します。

  • pos := -1で初期化します。

  • 一時配列tempを定義します。

  • i := 0から始めて、iがvのサイズ未満である間、iを1ずつ増やしながら次の処理を繰り返します。

    • v[i]がxと一致する場合、pos := iを設定し、ループを抜けます。

  • tempの先頭にv[pos]を挿入します。

  • i := 0から始めて、iがvのサイズ未満である間、iを1ずつ増やしながら次の処理を繰り返します。

    • iがposと一致する場合はその要素をスキップし、それ以外の場合はtempの末尾にv[i]を挿入します。

  • v := tempと更新します。

  • retの末尾にposを挿入します。

• retを返します。

計算量について

この実装では、各クエリごとに順列全体を線形走査して目的の値の位置を探すため、時間計算量はO(n×m)となります。mやnが大きくなるケースでは、Fenwick木（Binary Indexed Tree）や平衡二分探索木を活用することで、O((n+m) log m)程度まで高速化できる点も覚えておくとよいでしょう。

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> processQueries(vector<int>& q, int m) {
      vector<int> ret;
      vector<int> v;
      for (int i = 0; i < m; i++)
         v.push_back(i + 1);
      for (int x : q) {
         int pos = -1;
         vector<int> temp;
         for (int i = 0; i < v.size(); i++) {
            if (v[i] == x) {
               pos = i;
               break;
            }
         }
         temp.insert(temp.begin(), v[pos]);
         for (int i = 0; i < v.size(); i++) {
            if (i == pos)
               continue;
            temp.push_back(v[i]);
         }
         v = temp;
         ret.push_back(pos);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,1,2,1};
   print_vector(ob.processQueries(v, 5));
}

入力

{3,1,2,1}, 5

出力

[2, 1, 2, 1]