配列Bを並べ替えてA[i]+B[i]がx以下になるか判定するC++コード

問題概要

サイズnの2つの配列AとB、および整数xが与えられます。このとき、配列Bの要素を並べ替えることで、0以上n-1以下のすべてのiについて「A[i] + B[i] ≤ x」が成り立つようにできるかどうかを判定するのが目的です。

たとえば、入力が A = [1, 2, 3]、B = [1, 1, 2]、x = 4 の場合、出力は True(真)になります。B を [1, 2, 1] のように並べ替えれば、各ペアの合計は 1 + 1 ≤ 4、2 + 2 ≤ 4、3 + 1 ≤ 4 となり、条件をすべて満たすためです。

解法のアプローチ

この問題は貪欲法(グリーディ法)の考え方で効率よく解けます。片方の配列の小さい要素ともう片方の大きい要素を組み合わせることで、合計値が偏りにくくなり、条件を満たしやすくなります。

具体的な判定手順は以下の通りです。

1. Aのサイズをnとする。
2. フラグ変数ansを1(成功)で初期化する。
3. iを0からn-1まで動かしながら、A[i]とB[n - i - 1](後ろ側の要素)の合計を求める。
4. 合計がxを超えた場合は、ansを0(失敗)に更新する。
5. ループ終了後、ansが0以外ならtrue、0ならfalseを返す。

上記の手順を擬似コードで表すと、次のようになります。

n := Aのサイズ
ans := 1
sum := 0
i := 0 から n-1 まで繰り返し:
    sum := A[i] + B[n - i - 1]
    もし sum > x ならば:
        ans := 0
もし ans が 0 以外ならば:
    true を返す
そうでなければ:
    false を返す

C++での実装例

理解を深めるために、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A, vector<int> B, int x){
   int n = A.size();
   int ans = 1;
   int sum = 0;
   for (int i = 0; i < n; ++i){
      sum = A[i] + B[n - i - 1];
      if (sum > x)
      ans = 0;
   }
   if (ans)
      return true;
   else
      return false;
}
int main(){
   vector<int> A = { 1, 2, 3 };
   vector<int> B = { 1, 1, 2 };
   int x = 4;
   cout << solve(A, B, x) << endl;
}

入力

{ 1, 2, 3 }, { 1, 1, 2 }, 4

出力

1

出力が「1」、つまり true となっており、Bを適切に並べ替えることで条件を満たせることが確認できます。このアルゴリズムの計算量はO(n)であり、配列のサイズが大きくなっても高速に動作する点が魅力です。