C++で部分列の幅の総和を効率的に求める方法

問題の概要

整数の配列 A が与えられたとき、A のすべての空でない部分列を考えます。任意の列 S に対して、その「幅」は S に含まれる要素の最大値と最小値の差として定義されます。このとき、配列 A のすべての部分列の幅の総和を求めるのが課題です。答えは非常に大きな値になる可能性があるため、10⁹ + 7 で割った余りを返します。

たとえば入力が [3, 1, 2] の場合、出力は 6 になります。部分列は [1]、[2]、[3]、[2,1]、[2,3]、[1,3]、[2,1,3] の7通りであり、それぞれの幅は 0、0、0、1、1、2、2 となります。これらを合計すると 6 になるためです。

解法のポイント：各要素の寄与に分解する

すべての部分列を実際に生成して幅を計算すると、部分列の数は 2ⁿ − 1 個に達するため、n が大きい場合には現実的ではありません。そこで、各要素が「最大値」として寄与する回数と「最小値」として寄与する回数に着目します。

配列をあらかじめ昇順にソートしておけば、インデックス i の要素 a[i] より小さい要素はちょうど i 個あります。したがって、a[i] が部分列の最大値になるのは、自分自身とそれより前の要素から任意の部分集合を選ぶ場合で、合計 2ⁱ 通りです。同様に、a[i] が最小値になるのは 2^(n−1−i) 通りです。

この性質を利用すると、答えは次のように表せます。

Σ ( a[i] × 2ⁱ − a[i] × 2^(n−1−i) )

実装では、これを (a[i] − a[n−1−i]) × (2ⁱ − 1) の形に変形して計算しています（両者は数学的に等価です）。ループごとに変数 rcnt を2倍していき、i 回目の時点で rcnt = 2ⁱ となるようにすることで、べき乗の計算を効率的に行っています。

アルゴリズムの手順

• 関数 add(a, b) を定義する：((a mod m) + (b mod m)) mod m を返す

• 関数 sub(a, b) を定義する：(((a mod m) − (b mod m)) + m) mod m を返す（結果が負にならないよう m を加算）

• 関数 mul(a, b) を定義する：((a mod m) × (b mod m)) mod m を返す

• メインの処理は以下のとおり：

  • 配列 a をソートする

  • ans := 0、n := a のサイズ、rcnt := 1 で初期化する

  • i = 0 から n − 1 まで、i を1ずつ増やしながら繰り返す：

    • x = mul(a[i], sub(rcnt, 1))

    • y = mul(a[n−1−i], sub(rcnt, 1))

    • ans = add(ans, sub(x, y))

    • rcnt を2倍し、m で剰余を取る

  • ans を返す

C++による実装例

以下のコードでは、64ビット整数型 lli（long long int）を使用することで、剰余演算前の乗算でオーバーフローが発生しないようにしています。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
   public:
   lli add(lli a, lli b){
      return ( (a % m) + (b % m) ) % m;
   }
   lli sub(lli a, lli b){
      return ( ( (a % m) - (b % m) ) + m ) % m;
   }
   lli mul(lli a, lli b){
      return ( (a % m) * (b % m) ) % m;
   }
   int sumSubseqWidths(vector<int>& a) {
      sort(a.begin(), a.end());
      int ans = 0;
      int n = a.size();
      lli rcnt = 1;
      for(int i = 0 ; i < n; i++){
         ans = add (ans, sub(mul(a[i] , sub(rcnt , 1)), mul(a[n-1-i], sub(rcnt,1))));
         rcnt <<=1;
         rcnt %= m;
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,1,2};
   cout << (ob.sumSubseqWidths(v));
}

入力

{3,1,2}

出力

6

計算量について

この手法では、ソートに O(n log n)、各要素の寄与を集計するループに O(n) の計算量しかかかりません。部分列を全列挙する O(n × 2ⁿ) の素朴な方法と比べ、配列サイズが大きくなっても高速に動作する、非常に効率的な解法といえます。