C++で正方行列の特別な要素の合計を求める方法

ここでは、n × n の正方行列が与えられた場合を考えます。この行列の中で、次に挙げる値を「特別な要素」と呼びます。

• 主対角線(左上から右下へ伸びる対角線)上にある値
• 副対角線(右上から左下へ伸びる対角線)上にある値
• 上にちょうど (n − 1) / 2 個の行があり、下にも同じ数の行が存在する中央の行に含まれる値
• 左と右にそれぞれ (n − 1) / 2 個の列が存在する中央の列に含まれる値

この記事の目的は、これらの特別な値すべての合計を求めることです。

たとえば、入力が n = 4、mat = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}} である場合、出力は 107 となります。

解法のアプローチ

この問題を解くために、次の手順に従います。まず結果を格納する変数を 0 で初期化し、行列のすべての要素 (i, j) を二重ループで走査します。そして、以下のいずれかの条件を満たす要素のみを合計に加算します。

• i == j:主対角線上の要素
• i == n / 2:中央の行に属する要素
• j == n / 2:中央の列に属する要素
• i + j == n - 1:副対角線上の要素

アルゴリズムの流れは以下の擬似コードのようになります。

res := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
    for initialize j := 0, when j < n, update (increase j by 1), do:
        if i is same as j or i is same as n / 2 or j is same as n / 2 or i + j is same as n - 1, then:
            res := res + mat[i, j]
print(res)

C++による実装例

理解を深めるために、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int n, vector<vector<int>> mat) {
    int res = 0;
    for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++){
        if (i == j || i == n / 2 || j == n / 2 || i + j == n - 1)
            res += mat[i][j];
    }
    cout << res << endl;
}
int main() {
    int n = 4;
    vector<vector<int>> mat = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
    solve(n, mat);
    return 0;
}

入力

4, {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}}

出力

107