C++で行がソートされた行列からK番目に小さい配列の合計を求める方法

問題概要

m × n の行列 mat と整数 k が与えられます。mat の各行は非減少順(昇順)にソートされているものとします。各行からちょうど1つの要素を選んで配列を構成するとき、考えられるすべての組み合わせの中から、K番目に小さい配列の合計を求めるのが目的です。

たとえば、次のような行列が入力されたとしましょう。

ここで k = 5 のとき、出力は 7 になります。各行から1要素ずつ選んだとき、合計が小さい順に並べると [1,2]、[1,4]、[3,2]、[3,4]、[1,6] となり、5番目の合計値が 7 だからです。

解法の考え方

すべての組み合わせを総当たりで生成すると組み合わせの数が指数的に増えてしまうため、ここでは優先度付きキュー(最小ヒープ)を使って、合計値が小さい順に状態を段階的に展開していく手法を採用します。

基本となるアイデアは次のとおりです。

• 各行の先頭要素(=各行の最小値)の合計が「全体で最小の合計」になります。これを初期状態としてヒープに投入します。
• ヒープから最小の状態を取り出すたびに、「いずれか1行だけ選択位置を1つ進めた状態」(隣接状態)をすべて生成してヒープに戻します。
• 一度展開した状態は集合 s で記録し、同じ状態がヒープに重複して入らないようにします。
• この操作を k 回繰り返せば、k 回目に取り出した合計値が求める「K番目に小さい合計」となります。

アルゴリズムの手順

1. 優先度付きキュー pq を用意します(合計値を先頭に持つベクトルを最小ヒープとして管理します)。
2. 入力行列を保持する2次元配列 m を用意します。

3. 補助関数 update(v, i, ok=false) を次のように定義します。

   • i が v のサイズ(行数)に達した場合、ok が false なら何もせず戻ります。ok が true の場合は、各行 j について m[j][v[j]] の合計 sum を計算し、先頭に sum を付けた配列 temp を作成して pq に push してから戻ります。
   • v[i] を1増やします(現在の行で次の要素を選択)。
   • ok が false かつ v[i] < z(列数)のとき、update(v, i + 1, true) を再帰呼び出しします(この行の要素を変更した状態を展開)。
   • v[i] を元に戻し、update(v, i + 1, ok) を再帰呼び出しします(この行を変更しない分岐も展開)。

4. 本体の処理では以下を行います。

   • m に入力行列を格納し、ret = 0、n = 行数、z = 列数とします。
   • 各行について ret += m[i][0] とし、各行の先頭要素の合計(最小の合計)を求めます。
   • サイズ n の配列 temp を作成し、先頭に ret を挿入して pq に push します。
   • 訪問済みの状態を管理するための集合 s を用意します。
   • k が 0 になるまで次を繰り返します。
     • pq の先頭要素 temp を取り出し(pop)、s に挿入します。
     • ret = temp[0] とします(現在の K 番目の候補)。
     • temp から先頭の合計値を削除し、update(temp, 0) を呼び出して隣接する状態をすべて pq に push します。
     • pq が空でなく、先頭要素が s に含まれている間は pq から pop して除去します(重複状態の排除)。
5. 最後に ret を返します。

計算量について

この手法では、K番目に到達するために必要な状態だけを段階的に展開するため、全組み合わせ(最大で列数^行数 個)を一括生成する総当たり法よりも大幅に効率的です。ただし、1回の展開で最大 2^n 個程度の状態が生成されうる点は留意してください。

C++による実装例

それでは、理解を深めるために実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
struct Cmp{
   bool operator()(vector<int>& a, vector<int>& b) {
      return !(a[0] < b[0]);
   }
};
class Solution {
   public:
   priority_queue<vector<int>, vector<vector<int> >, Cmp> pq;
   vector<vector<int> > m;
   int z;
   void update(vector<int>& v, int i, bool ok = false){
      if (i == v.size()) {
         if (!ok)
         return;
         int sum = 0;
         for (int j = 0; j < v.size(); j++) {
            sum += m[j][v[j]];
         }
         vector<int> temp(v.begin(), v.end());
         temp.insert(temp.begin(), sum);
         pq.push(temp);
         return;
      }
      v[i]++;
      if (!ok && v[i] < z)
      update(v, i + 1, true);
      v[i]--;
      update(v, i + 1, ok);
   }
   int kthSmallest(vector<vector<int> >& m, int k){
      this->m = m;
      int ret = 0;
      int n = m.size();
      z = m[0].size();
      for (int i = 0; i < n; i++) {
         ret += m[i][0];
      }
      vector<int> temp(n);
      temp.insert(temp.begin(), ret);
      pq.push(temp);
      set<vector<int> > s;
      while (k--) {
         vector<int> temp = pq.top();
         pq.pop();
         s.insert(temp);
         ret = temp[0];
         temp.erase(temp.begin());
         update(temp, 0);
         while (!pq.empty() && s.count(pq.top())) {
            pq.pop();
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,3,11},{2,4,6}};
   cout << (ob.kthSmallest(v, 5));
}

入力

{{1,3,11},{2,4,6}}

出力

7