Chris and Magic Square [Codeforces 369 : Div2 B]

問題

http://codeforces.com/contest/711/problem/B

n×nの魔法陣がある。
魔法陣の数は自然数だが、1つだけ0になっており不完全である。
0に何を入れれば魔法陣として完成するか。
完成が不可能なら-1を出力せよ

1 <= n <= 500

考察

1. 色々やり方がありそう
2. setを使う解法を提出した(落ちたけど)

3. 縦横斜めで和をとってsetに入れる -> count()
4. 完成させられない時はsetの中身が2個以外である
5. もし、setの中身が2つしかないなら、その2つの差が答えとなる
6. この答えを入れて、もう一度、setに入れて確認する
7. もし、setの中身が1つになったら、それが答え

実装

http://codeforces.com/contest/711/submission/20256986

typedef long long ll;
int N;
ll A[500][500];
//-----------------------------------------------------------------
set<ll> count() {
	set<ll> s;
	ll sm;

	rep(y, 0, N) {
		sm = 0;
		rep(x, 0, N) sm += A[y][x];
		s.insert(sm);
	}

	rep(x, 0, N) {
		sm = 0;
		rep(y, 0, N) sm += A[y][x];
		s.insert(sm);
	}

	sm = 0;
	rep(y, 0, N) sm += A[y][y];
	s.insert(sm);

	sm = 0;
	rep(y, 0, N) sm += A[y][N - 1 - y];
	s.insert(sm);

	return s;
}
//-----------------------------------------------------------------
ll solve() {
	if (N == 1) return 1;

	set<ll> s = count();
	if (s.size() != 2) return -1;

	auto ite = s.begin();
	ll ans = *ite;
	ite++;
	ans = abs(ans - *ite);

	rep(y, 0, N) rep(x, 0, N) if (A[y][x] == 0) A[y][x] = ans;
	
	s = count();
	if (s.size() != 1) return -1;
	
	return ans;
}
//-----------------------------------------------------------------
int main() {
	cin >> N;
	rep(y, 0, N) rep(x, 0, N) scanf("%d", &A[y][x]);

	cout << solve() << endl;
}