【C++】与えられた長さの線分で作成できる平行四辺形の最大数を求める方法

問題概要

N本の線分が与えられたとき、各線分は高々1つの平行四辺形にしか使用できないという条件のもとで、作成できる平行四辺形の最大数を求めるのがこの記事のテーマです。平行四辺形は「同じ長さの辺2本ずつ」で構成されるため、各長さの出現回数をどのように組み合わせるかが鍵となります。

まず、具体例を使って問題を確認しましょう。

入力: Arr[] = {8, 3, 1, 3, 8, 7, 1, 3, 5, 3}

出力: 2

説明: 上記の線分から作成できる2つの平行四辺形は、それぞれ「8, 1, 8, 1」と「3, 3, 3, 3」を辺とするものです。

入力: Arr[] = {7, 9, 9, 7}

出力: 1

アルゴリズムの考え方

• 作成できる平行四辺形の最大数は、「4本すべて同じ長さの辺で作れる平行四辺形の数」と「同じ長さの辺2本ずつで作れる平行四辺形の数」の合計になります。
• 関数MaxParr()では、まず変数L = Arr[0]を初期化します。これは線分の長さごとの出現頻度を格納する配列のサイズとして使用します。
• i=1からi<Nまでループし、Arr[i] > LであればL = Arr[i]と更新します。ループ終了後、Lに1を加えます。
• 続いて、頻度配列int Freq[L] = {0}を初期化し、i=0からi<Nまでループして各線分の出現回数を1ずつカウントアップします。
• 平行四辺形の総数を格納するため、int型のcount = 0を初期化します。
• i=0からi<Lまでループし、4本とも同じ長さの辺で作れる平行四辺形をチェックし、見つかった場合はcountを加算していきます。
• 同じ長さの辺2本ずつで作成できる平行四辺形の候補数を格納するため、int型のleft = 0を初期化します。
• 最後に、i=0からi<Lまでループし、Freq[i] >= 2であればleftに1を加算します。
• count += left / 2 を計算し、その結果を返します。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int MaxParr(int N, int Arr[]){
    // 頻度配列の長さを求める
    int L = Arr[0];
    for (int i = 1; i < N; i++){
        if (Arr[i] > L)
            L = Arr[i];
    }
    L = L + 1;
    int Freq[L] = {0};
    for (int i = 0; i < N; i++){
        // 各線分の出現回数をカウント
        Freq[Arr[i]] += 1;
    }
    // 平行四辺形の数を格納する変数
    int count = 0;
    for (int i = 0; i < L; i++){
        /* 4本とも同じ長さの辺で作れる平行四辺形 */
        count += int(Freq[i] / 4);
        Freq[i] = Freq[i] % 4;
    }
    int left = 0;
    for (int i = 0; i < L; i++){
        // 残り2回以上出現する線分をカウント
        if (Freq[i] >= 2)
            left += 1;
    }
    /* 同じ長さの辺2本ずつで作れる平行四辺形を合計に加算 */
    count += left / 2;
    return count;
}
int main(){
    int N = 10;
    int Arr[] = { 8, 3, 1, 3, 8, 7, 1, 3, 5, 3};
    cout<< MaxParr(N, Arr);
}

実行結果

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

2

まとめ

このアルゴリズムでは、各長さの出現回数を頻度配列で管理することで、O(N + L)の計算量で答えを求められます。まず4本組を優先的に平行四辺形として消費し、その余り(2本または3本残るケース)をペアとして集計し、2ペアで1つの平行四辺形を作ることで、全体の最大化を実現しています。