POJ 2837 : Silver Matrix - 忘れても大丈夫

問題. Silver Matrix

自然数 $k$ が与えられたときに次を満たす Silver Matrix $M$ を1つ構成せよ．
　1. サイズ $n \times n$ の正方行列 ( $n = 2^k$ )
　2. $M$ の各要素 $m_{i j} \in \{1, 2, \ldots, 2n - 1\}$
　3. 各 $1 \le i \le n$ に対して，　 $\{m_{jk} \mid j = i \vee k = i\} = \{1, 2, \ldots, 2n - 1\}$

制約： $1 \le k \le 9$ 　（サイズが $2^k \times 2^k$ のときは解が存在することが保証される）

解法

サイズ $k \times k$ の Silver Matrix を $S(k)$ と表す．また，サイズ $k \times k$ の単位行列と，すべての要素が1の行列をそれぞれ $I, J$ とする．このとき，サイズ $k + 1$ の Silver Matrix $S(k + 1)$ は次のように帰納的に構成できる．
f:id:tatanaideyo:20181113203745p:plain:w350

左上と右下のブロックはサイズ $k \times k$ の Silver Matrix $S(k)$ であり，右下と右上のブロックは $S(k)$ の各要素に $2k - 1$ を加えた行列である．ただし，右上のブロックの対角成分はすべて $2 \times 2^{k + 1} - 1$ である．
まず，条件1と条件2は明らかに成り立つ（構成方法からこの Silver Matrix の対角成分はすべて1）．
条件3を考えると，左上と右下のブロックは互いに独立であり，これらの要素から各 $1 \le i \le 2^{k + 1}$ に対して $\{m_{jk} \mid j = i \vee k = i \} = \{1, \ldots, 2 \times 2^k - 1\}$ が成り立つ．また，左下と右上の各要素は $2^k$ 以上 $2 \times 2^{k + 1} - 1$ 以下であり，左上と右下のブロックとは互いに独立である．

計算時間： $O(n^2)$

ソースコードを表示

#include <iostream>
#include <vector>

int main() {
    std::cin.tie(0); std::ios::sync_with_stdio(false);

    int k;
    std::cin >> k;

    const int n = 1 << k;
    std::vector<std::vector<int> > m(n, std::vector<int>(n));

    m[0][0] = 1;
    for (int sz = 1; sz < n; sz <<= 1)
        for (int i = 0; i < sz; ++i)
            for (int j = 0; j < sz; ++j) {
                m[i + sz][j + sz] = m[i][j];
                m[i + sz][j] = m[i][j + sz] = m[i][j] + 2 * sz - 1;
                if (i == j) m[i][j + sz] = 4 * sz - 1;
            }

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            std::cout << m[i][j] << " \n"[j == n - 1];

    return 0;
}