C++で制約条件を満たすN×N行列における1の最大数を求める方法

問題の概要

この記事では、以下の制約条件を満たすバイナリ行列(0と1のみで構成される行列)における、1の最大数を求める方法を解説します。

2つの整数 N と X(X ≤ N)が与えられます。バイナリ行列のサイズは N×N とし、すべての X×X サイズの部分行列には、少なくとも1つの 0 が含まれている必要があります。

具体例を使って、問題を理解しましょう。

入力: N=4, X=2

出力: 12

説明: 条件を満たす行列は以下のようになります。

1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

入力: N=7, X=3

出力: 45

解法のアプローチ

• 1の数を最大化するには、まず行列に必要な 0の最小個数 を求める必要があります。

  すべての行列に共通するパターンを観察すると、必要な0の個数は (N / X)² であることがわかります。これは、行列上で X 個おきに0を配置することで、どの X×X 部分行列にも必ず1つの0が含まれるようにできるためです。

  したがって、1の最大数 = 行列の全要素数 − 0の個数 という式で求められます。

• MaxOne() 関数内では、int型の変数 Z を作成し、必要な0の最小個数、すなわち (N / X)² を格納します。

• 次に、行列の全要素数を格納するための int型変数 total = N*N を初期化します。

• 最後に、最終的な答えを格納する int ans = total − Z を初期化し、ans を返します。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int MaxOne(int N, int X){
    // 必要な0の最小個数
    int Z = (N / X);
    Z = Z * Z;
    /* 行列の全要素数 = 行列サイズの2乗 */
    int total = N * N;
    // 最終的な答え
    int ans = total - Z;
    return ans;
}
int main(){
    int N = 4;
    int X = 2;
    cout << MaxOne(N, X);
    return 0;
}

出力

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

12

計算量について

このアルゴリズムは行列を実際に構築せず、整数演算のみで答えを求めるため、時間計算量は O(1)、空間計算量も O(1) となります。N が大きくなっても高速に動作する、非常に効率的な解法です。