srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

Codeforces Educational Codeforces Round 16 C. Magic Odd Square

問題

問題概要

nが与えられた時、1からn2まで使いn x nのますを縦横斜め全ての和が奇数になるように、埋めていく。

解法

縦横斜めの和が奇数になるのは、それらの一列に、奇数が奇数個ある時。この条件を満たすには、真ん中に十字形に奇数と配置し、4隅に階段状に奇数を配置すれば良いことになる。残りが偶数を配置すればいい。これは縦横斜めどのように線を引いても、十字架の部分で奇数が1つ、他の部分で奇数が偶数個になるようにするため。4隅に点対称になるように置くことで、必ず、十字架以外の部分で、奇数が偶数個になる。またこれらの条件は魔法陣が満たしている。
下の図はn=9の時

ミス

綺麗な実装できない。

コード

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int b[60][60];
int main(void){
    rep(i, 60)rep(j, 60) b[i][j] = 0;
    int n; cin >> n;

    int kado = sqrt((n * n - (n*2 - 1)) / 4) - 1;
    int kisuu = 1;
    int guusu = 2;
    rep(i, n){
        b[i][n / 2] = kisuu; kisuu += 2;
    }
    rep(i, n){
        if(i == n / 2) continue;
        b[n / 2][i] = kisuu; kisuu += 2;
    }

    int now = kado;
    rep(i, kado){
        rep(j, now){
            b[i][j] = kisuu; kisuu += 2;
        }
        now--;
    }

    now = kado;
    for (int i = n - 1; i > n - 1 - kado ; --i){
        rep(j, now){
            b[i][j] = kisuu; kisuu += 2;
        }
        now--;
    }

    now = kado;
    rep(i, kado){
        for (int j = n - 1; j > n - 1 - now ; --j){
            b[i][j] = kisuu; kisuu += 2;
        }
        now--;
    }

    now = kado;
    for (int i = n - 1; i > n - 1 - kado ; --i){
        for (int j = n - 1; j > n - 1 - now ; --j){
            b[i][j] = kisuu; kisuu += 2;
        }
        now--;
    }

    rep(i, n)rep(j, n){
        if(b[i][j] == 0){
            b[i][j] = guusu;
            guusu += 2;
        }
    }

    rep(i, n){
        rep(j, n){
            printf("%d ", b[i][j]);
        }
        printf("\n");
    }
    return 0;
}