C++で円上に立つ人の真向かいの位置を求めるアルゴリズム

問題概要

この問題では、2つの整数 N と M が与えられます。円の周りにはN人が等間隔で立っており、Mはそのうちのある一人の人の位置を表しています。私たちのタスクは、位置Mにいる人と正反対（直径を挟んで向かい合う）にいる人の位置を出力することです。

入出力例

入力： N = 6、M = 3

出力： 6

説明： 円の周りに6人が立っているとき、位置3にいる人と向かい合うのは位置6の人です。

解き方の考え方

円の中心を挟んで正反対の位置は、必ずちょうど半分（N/2）だけ離れた場所にあります。この性質を使うと、対象の人が円の前半にいるか後半にいるかによって、次の2つの場合に分けて考えることができます。

• ケース1： m > n/2 の場合（対象が円の後半にいるとき）、向かい合う人は前半にいるため、答えは m − (n / 2)
• ケース2： m ≤ n/2 の場合（対象が円の前半にいるとき）、向かい合う人は後半にいるため、答えは m + (n / 2)

このように場合分けを行うことで、ループを使わずにO(1)の計算量で答えを求めることができます。

C++での実装例

以下は、上記の考え方を実装したプログラムです。

#include <iostream>
using namespace std;

void printOppositePosition(int n, int m) {
    int pos;
    if (m > (n / 2))
        pos = (m - (n / 2));
    else
        pos = (m + (n / 2));
    cout << pos;
}

int main() {
    int N = 8, M = 4;
    cout << "位置" << M << "にいる人と向かい合う人の位置（" << N << "人が円上に立っている場合）は ";
    printOppositePosition(N, M);
    return 0;
}

実行結果

位置4にいる人と向かい合う人の位置（8人が円上に立っている場合）は 8

補足ポイント

・このアルゴリズムは条件分岐と四則演算のみで構成されているため、計算量はO(1)と非常に効率的です。
・n / 2 は整数除算として評価されるため、Nが偶数であることを前提としています。Nが奇数の場合は厳密に「正反対」の人が存在しないため、問題の制約を確認しておきましょう。