C++で正N角形上の3人目の最適な立ち位置を求める方法

問題の概要

N辺の多角形を考えます。2人の子どもがそれぞれ頂点Aと頂点Bに立っているとき、もう1人が立つべき頂点番号を求めるのがこの問題の目的です。ただし、その人物が頂点Aと頂点Bの両方へ到達するために必要なジャンプ回数が最小になるような頂点を選ぶ必要があります。

ここで押さえておくべき条件は次の2つです。

• 多角形の頂点には時計回りに番号が付けられています。
• 答えが複数存在する場合は、常に最も番号の小さい頂点を採用します。

アルゴリズムの考え方

関数vertexPosition(int sides, int vertexA, int vertexB)は、多角形の辺の数と、頂点A・Bの位置を引数として受け取ります。forループは1から始まり、iが辺の数以下である間繰り返されます。iがvertexAともvertexBとも一致しない場合、iと頂点Aの距離（絶対差）、およびiと頂点Bの距離（絶対差）をそれぞれ計算し、変数xとyに格納します。

int vertexPosition(int N, int vertexA, int vertexB){
    int tempSum = INT_MAX;
    int sum = 0;
    int position = 0;
    for (int i = 1; i <= N; i++) {
        if (i != vertexA && i != vertexB){
            int x = abs(i - vertexA);
            int y = abs(i - vertexB);

続いて、xとyの合計をsum変数に保存し、その値がtempSumより小さいかどうかを判定します。小さい場合は、現在のsumの値をtempSumに代入し、あわせて現在のインデックス値をposition変数に代入します。このif文によるチェックによって、「新しく得られたsumが、これまでtempSumに保持していた値よりも小さいか」が確認され、結果として頂点AとBの両方に最も近い位置を返せる仕組みになっています。ループがすべて終わった時点で、positionを返します。

            sum = x + y;
            if (sum < tempSum){
                tempSum = sum;
                position = i;
            }
        }
    }
    return position;
}

このアルゴリズムの計算量はO(N)であり、頂点数に比例して処理時間が増加しますが、非常にシンプルで理解しやすい手法です。

実装例

それでは、正N角形上の3人目の位置を決定する実際の実装を見てみましょう。

#include <iostream>
using namespace std;
int vertexPosition(int N, int vertexA, int vertexB){
    int tempSum = INT_MAX;
    int sum = 0;
    int position = 0;
    for (int i = 1; i <= N; i++) {
        if (i != vertexA && i != vertexB){
            int x = abs(i - vertexA);
            int y = abs(i - vertexB);
            sum = x + y;
            if (sum < tempSum){
                tempSum = sum;
                position = i;
            }
        }
    }
    return position;
}
int main(){
    int N = 6, vertexA = 2, vertexB = 4;
    cout << "The vertex on which N should stand = " << vertexPosition(N, vertexA, vertexB);
    return 0;
}

出力

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

The vertex on which N should stand = 6

この例では、6つの頂点を持つ正六角形の頂点2と頂点4に2人の子どもが立っており、関数が返した頂点が3人目の立ち位置となります。同様の手順で、任意の頂点数・任意の開始位置に対して3人目の最適な頂点を求めることができます。