Codeforces 255D Mr. Bender and Square

問題

nxnのグリッドがあり、(x, y)の点がt = 0において色がついている。
1秒ごとに、色のついているマスと辺を共有している色のついてないマスに色がつく。
全体でc個以上のマスに色がつくのにかかる時間を求めよ。

制約条件

n≦10^9

方針

時刻tで色のついたマスの個数をf(t)とすると、
f(t)は単調増加なので二分探索すればいい。

f(t)を上手く書けないと死ぬ系の問題。
4回、回転して分けて考えると実装が1通りですむ。
(x, y)の左下の部分だけを数える。

全体がはみ出る場合（斜めの線がグリッドの左下を超える場合）は、
数えるところは長方形になるので、x*(y+1)個。
そうでない場合は、t*(t+1)/2からy軸、x軸ではみでた部分をそれぞれ引けばいい。

ソースコード

ll n, x, y, c;
ll calc(ll t){
	ll res = 1;
	rep(it, 4){
		if(x + y < t) res += x * (y + 1);
		else{
			res += t * (t + 1) / 2;
			if(x < t) res -= (t - x) * (t - x + 1) / 2;
			if(y < t) res -= (t - y - 1) * (t - y) / 2;
		}
		swap(x, y);
		x = n - 1 - x;
	}
	return res;
}

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