C++で円を2つの部分に分割したときの角度差の最小値を求めるプログラム

この記事では、円を構成する各部分（扇形）の角度が格納された配列が与えられたとき、それらを連続的につなぎ合わせて2つの部分に分割した場合の角度差の最小値を求めるC++プログラムを解説します。

問題の概要

円全体（360度）を構成するすべての部分の角度が配列として与えられます。これらの部分を連続する範囲ごとに結合して2つのグループを作り、それぞれのグループの角度の合計の差が最小になるようにします。重要なのは、離れた位置にある部分（例えば最初の部分と3番目の部分など）を一緒にすることはできないという点です。

入力例で理解しましょう

入力

ang[] = {90, 45, 90, 135}

出力

90

説明

1つ目と2つ目の部分をまとめると、90 + 45 = 135度になります。

3つ目と4つ目の部分をまとめると、90 + 135 = 225度になります。

したがって、差は 225 − 135 = 90 となり、これが最小値です。

解法アプローチ

まず、片方の部分の角度の合計を A とします。円の合計は360度なので、もう一方の部分の角度は必然的に「360 − A」になります。

このとき、2つの部分の差は次のように表せます。

|A − (360 − A)|

角度は常に正であるため、絶対値を取ります。この式を整理すると、

2 × |A − 180|

となります。つまり、A が180度にできるだけ近づくように部分を分割すればよいことになります。そこで、スライディングウィンドウ（尺取り法）を使って、すべての連続する部分の組み合わせについて A を求め、「2 × |A − 180|」の最小値を計算します。

この手法により、全組み合わせを総当たりする O(n²) ではなく、O(n) の時間計算量で効率的に答えを得られます。空間計算量は O(1) です。

C++での実装例

#include <iostream>
#include <math.h>
using namespace std;

int CalcSmallDiffAng(int ang[], int n) {
    int Left = 0, A = 0, minDiff = 360;
    for (int i = 0; i < n; i++) {
        A += ang[i];
        while (A >= 180) {
            minDiff = min(minDiff, 2 * abs(180 - A));
            A -= ang[Left];
            Left++;
        }
        minDiff = min(minDiff, 2 * abs(180 - A));
    }
    return minDiff;
}

int main() {
    int ang[] = { 90, 45, 90, 135 };
    int n = sizeof(ang) / sizeof(ang[0]);
    cout << "与えられた円の2つの部分の角度差の最小値は "
         << CalcSmallDiffAng(ang, n);
    return 0;
}

出力

与えられた円の2つの部分の角度差の最小値は 90

コードのポイント

変数 Left はウィンドウの左端を管理し、A は現在のウィンドウ内の角度の合計を表します。A が180以上になったタイミングで、左端の要素を順に取り除きながら最小差を更新していきます。これにより、180度をまたぐ境界付近のすべての分割パターンを漏れなくチェックできます。