Codeforces #156 Div1 B (256 B) Mr. Bender and Square

問題

n x nの行列がある。
それぞれの成分はスイッチで、ONかOFFの状態をとる。

1秒ごとに、ONに隣接するOFFのスイッチはONになる。
最初、(x, y)のスイッチだけがONのとき、オンになっているスイッチがc個以上になるには何秒かかるか、求めよ。

制約条件

n≦10^9
1≦x, y≦n
c≦min(n^2, 10^9)

方針

t秒後にONになっているスイッチの数は比較的簡単に求められる。
これは、単調増加するため、二分探索で答えを見つければよい。

t秒後にONになっているスイッチは、頑張って数えるのだが、
(x, y)の(0,0)側の1/4だけを数え、あとの部分は対称性を利用して、同じ関数で求めればよい。

ソースコード

ll n, x, y, c;
ll calc2(ll t, ll x, ll y){
	if(x + y <= t) return (x + 1) * (y + 1);
	ll res = (t + 1) * (t + 2) / 2;
	ll a = -(x - t), b = -(y - t);
	
	if(a > 0) res -= a * (a + 1) / 2;
	if(b > 0) res -= b * (b + 1) / 2;
	return res;
	
}
ll calc(ll t, ll x, ll y){
	ll res = -3;
	res -= min(t, x);
	res -= min(t, y);
	res -= min(t, max(0ll, n - 1 - y));
	res -= min(t, max(0ll, n - 1 - x));
	
	rep(i, 2) rep(j, 2){
		res += calc2(t, i ? x : n - 1 - x, j ? y : n - 1 - y);
	}
	return res;
}

int main(){
	cin >> n >> x >> y >> c;
	x--; y--;
	
	int lo = -1, hi = 2 * n, mid;
	while(lo + 1 < hi){
		mid = ll(lo + hi) / 2;
		if(calc(mid, x, y) >= c) hi = mid;
		else lo = mid;
	}
	cout << hi << endl;
	
	return 0;
}