C++でチェス盤に含まれる奇数の辺の長さを持つ正方形を数える方法

一辺の長さ size が与えられ、size × size のチェス盤（正方形のマス目）を考えます。このとき、盤面の中に作ることができる奇数の辺の長さを持つ正方形の総数を求めるのが本記事の目的です。

入力例と出力例

例1

入力:

size=3

出力:

Count of squares with odd side length in Chessboard are: 10

説明:

3×3 の盤面には、1×1 の小さな正方形が9個、2×2 の正方形が4個、そして盤全体の 3×3 の正方形が1個存在します。このうち辺の長さが奇数となるのは、1×1 の9個と 3×3 の1個、合計 10個 です。

例2

入力:

size=4

出力:

Count of squares with odd side length in Chessboard are: 20

説明:

4×4 の盤面には、1×1 の正方形が16個、3×3 の正方形が4個含まれます。したがって、奇数の辺の長さを持つ正方形は合計 20個 となります。

アルゴリズムのアプローチ

この問題は、次のようなシンプルな方法で解くことができます。

辺の長さを 1 から size まで順番に走査し、各奇数の長さ i に対して、その大きさの正方形が盤面内に何箇所に配置できるかを計算します。具体的には、(size − i + 1)² を答えに加算していきます。

手順

• チェス盤の一辺の長さとして整数 size を入力として受け取ります。

• 関数 square_odd_length(int size) が size を受け取り、奇数の辺の長さを持つ正方形の個数を返します。

• カウント用の変数 count を 0 で初期化します。

• i = 1 から i = size まで、i を 2 ずつ増やしながらループを回し、奇数の i のみを処理します。

• 各 i について、temp = size − i + 1 を計算します。

• temp × temp を count に加算します。

• ループ終了後、count を結果として返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int square_odd_length(int size){
    int count = 0;
    for (int i = 1; i <= size; i = i + 2){
        int temp = size − i + 1;
        count = count + (temp * temp);
    }
    return count;
}
int main(){
    int size = 6;
    cout<<"Count squares with odd side length in Chessboard are: "<<square_odd_length(size);
    return 0;
}

実行結果

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

Count squares with odd side length in Chessboard are: 56

まとめ

このように、奇数の辺の長さごとに配置可能な位置の数を二乗で求めて足し合わせることで、効率的に正方形の総数を計算できます。計算量は O(size/2) となり、非常にシンプルかつ高速なアルゴリズムです。