【C++】指定されたセグメント長から中点を含むセグメントを検索する方法

問題概要

この問題では、線分の長さを格納したサイズ m の配列 arr[] が与えられます。

線分は「0 から arr[0] まで」「arr[0] から arr[1] まで」というように順番に連結され、全体として1本の長い線を構成しています。求めたいのは、全線分の中間点が含まれるセグメントの番号です。

入出力例

入力

arr[] = {5, 7, 13}

出力

3

説明

線分 : (0, 5)、(5, 12)、(12, 25)

全体の長さは 25 なので、中点の座標は 12.5 になります。この中点は3番目のセグメント (12, 25) に含まれるため、答えは 3 となります。

解法アプローチ

まず、配列要素の合計値 arrSum を求め、中点の座標を arrSum / 2 として計算します。その上で、次のように判定を行います。

• 中点がいずれかの線分の始点または終点(境界)と一致する場合は -1 を返す。
• それ以外の場合は、中点を含むセグメント番号を返す。

具体的には、先頭から累積和を順に更新していき、累積和が初めて中点を超えた時点のインデックス +1 が答えになります。計算量は O(m)、必要な追加メモリは O(1) と非常に効率的です。

実装例(C++)

#include <iostream>
using namespace std;

// 中点を含むセグメント番号を返す関数
int findSegmentWithMidPoint(int n, int m, int segment_length[]) {
    double centerPoint = (1.0 * n) / 2.0; // 全体の中点の座標
    int sum = 0;      // 累積和
    int segment = -1; // 結果(該当なしの場合は -1)
    for (int i = 0; i < m; i++) {
        sum += segment_length[i];
        // 中点が線分の境界と一致した場合
        if ((double)sum == centerPoint) {
            segment = -1;
            break;
        }
        // 中点が現在のセグメント内にある場合
        if (sum > centerPoint) {
            segment = i + 1;
            break;
        }
    }
    return segment;
}

int main() {
    int m = 3;
    int segment_length[] = { 5, 7, 13 };
    int arrSum = 0;
    for (int i = 0; i < m; i++)
        arrSum += segment_length[i]; // 全体の長さを計算
    int ans = findSegmentWithMidPoint(arrSum, m, segment_length);
    cout << "中点が含まれるセグメント番号は " << ans << " です";
    return 0;
}

出力

中点が含まれるセグメント番号は 3 です

まとめ

本記事では、連結された線分の長さから全体の中点が属するセグメントを検索する方法を紹介しました。累積和を活用することで、時間計算量 O(m)・空間計算量 O(1) で効率的に求解できます。中点がちょうど線分の境界に一致するケース(-1 を返す条件)の扱いにも注意して実装しましょう。