C++でK番目に小さい素数の分数を求めるアルゴリズム｜優先度付きキューによる解法

ソート済みのリストがあり、その中には 1 と複数の素数が含まれているとします。リスト内のすべての組合せ p < q について分数 p/q を考え、そのうち k 番目に小さい分数を求めます。答えは配列として返却し、ans[0] には分子 p、ans[1] には分母 q を格納します。

たとえば、入力が [1, 3, 5, 7]、k = 2 の場合を考えてみましょう。生成される分数は 1/3、1/5、1/7、3/5、3/7、5/7 の6つで、2番目に小さいのは 1/5 です。したがって答えは 1/5 となります。

解法のアプローチ

この問題は優先度付きキュー（priority queue）を使うと効率的に解けます。ポイントは、各分母ごとに「分子を小さい方から順に」候補として管理することです。こうすると、n 個のソート済み列をマージする要領で、小さい方から順に分数を取り出せるようになります。

具体的な手順は以下のとおりです。

• 構造体 Data を定義する。メンバーとして a、b、および a/b の値を保持する。
• サイズ2の配列 ret を用意する。
• n := 配列 A のサイズとする。
• 優先度付きキュー pq を定義する。
• i := 0 から n-1 まで繰り返し、Data(A[0], A[i], 0) を pq に挿入する。
• カウンタ K を使い、以下を繰り返す。
  • pq の先頭要素を temp に取得し、pq からポップする。
  • これが K 回目の取り出し（K == 0）であれば、ret[0] := temp の a、ret[1] := temp の b として ret を返す。
  • temp.idx + 1 < n であれば、idx := temp.idx + 1 として Data(A[idx], temp.b, idx) を pq に挿入する。
• 最終的に ret を返す。

このアルゴリズムが機能する理由

最初にキューへ入れるのは「最小の分子 A[0] × 各分母」という組み合わせだけです。これは、各分母においてあり得る分数の中で最も小さいものに相当します。キューから最小の分数を取り出すたびに、同じ分母で次に大きい分子を持つ分数を補充していくため、常に全体で最小の分数がキューの先頭に現れます。これを K 回繰り返せば、目的の K 番目に小さい分数が得られます。

なお、Comparator 構造体で比較演算子を定義しているのは、標準の priority_queue（最大ヒープ）を最小ヒープとして動作させるためです。計算量は、初期構築に O(n log n)、以降の取り出し・挿入ごとに O(log n) 必要となるため、全体として約 O((n + k) log n) です。

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

サンプルコード（C++）

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
struct Data{
   double val, a, b;
   int idx;
   Data(double a, double b, int c){
      val = a / b;
      this->a = a;
      this->b = b;
      idx = c;
   }
};
struct Comparator{
   bool operator()(Data a, Data b){
      return !(a.val < b.val);
   }
};
class Solution {
public:
   vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
      vector <int> ret(2);
      int n = A.size();
      priority_queue <Data, vector <Data>, Comparator> pq;
      for(int i = 0; i < n; i++){
         pq.push(Data(double(A[0]), double(A[i]), 0));
      }
      while(K--){
         Data temp = pq.top();
         pq.pop();
         if(K == 0){
            ret[0] = temp.a;
            ret[1] = temp.b;
            return ret;
         }
         if(temp.idx + 1 < n){
            int idx = temp.idx + 1;
            pq.push(Data(double(A[idx]), double(temp.b), idx));
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,3,5,7};
   print_vector(ob.kthSmallestPrimeFraction(v, 2));
}

入力

{1,3,5,7}
2

出力

[1, 5]