TopCoderOpen 2020 Round2A : Easy GridSpiral

Round2ってDiv1相当？
https://community.topcoder.com/stat?c=problem_statement&pm=16142&rd=18068

問題

無限のサイズのグリッド上に、0,1,2...と渦巻き状に連番を埋めて行く。
隣接マスとの数値の差がDとなる最小の数値はいくつか。

解法

隣接マスとは偶奇が異なるので、差は偶数にはならない。
よって以後差が奇数のケースのみ考える。
差の最大値を更新するのは、渦巻き状に数値を埋める際に向きを変えるタイミングなので、そのタイミングを総当たりするとよい。

class GridSpiral {
	public:
	long long findCell(int D) {
		if(D%2==0) return -1;
		if(D<=7) return 0;
		ll cur=7;
		int len=1;
		ll nex=0;
		while(1) {
			if(D<cur+4) {
				if(D==cur) return nex;
				if(D==cur+2) return nex+len;
			}
			nex+=len*2;
			len++;
			cur+=4;
		}
		
	}
}

まとめ

O(D)で通るのか…。