C++でKで割り切れる合計ペアの最大数を求める方法

N個の整数を含む配列 arr[] が与えられたとき、Kで割り切れる arr[i] + arr[j] のペアの最大数を求めることを考えます。ただし、同じインデックスを複数のペアに使用することはできないという条件が付きます。

入力

arr[]={1, 2, 5, 8, 3}, K=2

出力

2

説明

条件を満たすのは (0,2) と (1,3) のペアです。1+5=6、2+8=10 となり、いずれも2で割り切れます。

ほかに (0,4) と (1,3)、あるいは (2,4) と (1,3) という選び方も考えられますが、答えは同じく2になります。

入力

arr[]={1, 3, 5, 2, 3, 4}, K=3

出力

3

プログラムで使用するアプローチ

• int型の変数 n に配列のサイズを格納します。
• MaxPairs() 関数内では unordered_map を使用し、配列の各要素について um[arr[i]%K] の値を1ずつ増やしていきます。
• 反復処理により、マップ上のすべての余りの値を取得します。
• 余りが0の要素は同士でしかペアを作れないため、ペア数は um[0]/2 となります。
• それ以外の余り a については、(um[a], um[K−a]) の小さい方を採用することでペアを形成できます。
• 最後に、使用済みのペア数をマップの値から差し引きます。

コード例

#include <bits/stdc++.h>
using namespace std;
int MaxPairs(int arr[], int size, int K){
    unordered_map<int, int> um;
    for (int i = 0; i < size; i++){
        um[arr[i] % K]++;
    }
    int count = 0;
    /* マップ上のすべての余りの値を反復処理 */
    for (auto it : um){
        // 余りが0の場合
        if (it.first == 0){
            // 同じ数同士でペアを作るため半分を取る
            count += it.second / 2;
            if (it.first % 2 == 0){
                um[it.first] = 0;
            }
            else{
                um[it.first] = 1;
            }
        }
        else{
            int first = it.first;
            int second = K - it.first;
            // 出現回数が少ない方を確認
            if (um[first] < um[second]){
                // 少ない方を採用
                count += um[first];
                // 使用したペア分を差し引く
                um[second] -= um[first];
                um[first] = 0;
            }
            else if (um[first] > um[second]){
                // 少ない方を採用
                count += um[second];
                // 使用したペア分を差し引く
                um[first] -= um[second];
                um[second] = 0;
            }
            else{
                // 余りが同じかどうかを確認
                if (first == second){
                    // 同じ場合はペア数は半分になる
                    count += it.second / 2;
                    // 残りを確認
                    if (it.first % 2 == 0)
                        um[it.first] = 0;
                    else
                        um[it.first] = 1;
                }
                else{
                    // ペアの数を加算
                    count += um[first];
                    um[first] = 0;
                    um[second] = 0;
                }
            }
        }
    }
    return count;
}
// メイン関数
int main(){
    int arr[] = { 3, 6, 7, 9, 4, 4, 10 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int K = 2;
    cout << "Kで割り切れる合計ペアの最大数: " << MaxPairs(arr, size, K);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

Kで割り切れる合計ペアの最大数: 3

まとめ

このアルゴリズムでは、各要素をKで割った余りごとに分類することで、O(N) の計算量でペアの最大数を効率的に求められます。余り a のグループと余り K−a のグループを対応付けて組み合わせることで、「和がKの倍数」となるペアを取りこぼしなく数え上げられるのがポイントです。