Google Code Jam 2022 Round 2 : B. Pixelated Circle

落ち着いて考えるとそこまで難しくないんだけどね。
https://codingcompetitions.withgoogle.com/codejam/round/00000000008778ec/0000000000b158f7

問題

正整数Rが与えられる。
白マスからなるグリッド上に、半径Rの黒い塗りつぶし円を描く。その時以下の2つのアルゴリズムを考える。（厳密な定義は問題文参照）

• 原点となるセルから、半径R以下にある全セルを黒く塗る。
• 半径1,2,3....,Rの円周上のセルを塗る。

両者で塗られるセル数に差が生じうる。その差を求めよ。

解法

原点から右上方向にある1/4の領域のみにおいて、両アルゴリズムで塗られるセルの総和を考えよう。
前者は尺取り法の要領で、X座標を変化させながら円内に収まるY座標の最大値を見ればO(N)で計算できる。
後者で重要なのは、以下の2点。

• 異なる半径の円周上のセルは重ならない。よって、半径毎に塗られるセル数を数えて総和を取ればよい。
• 2次元座標で見て偏角が45度以内となる、円の1/8の領域を考える。この範囲では、Y座標毎に1つずつセルが塗られる。

あとは各半径毎に塗られるセル数を数えよう。原点からちょうど45度にあるセルが、どの半径の時に塗られるか注意すること。

int R;
int D[101010];

void solve(int _loop) {
	int f,i,j,k,l,x,y,r;
	
	cin>>R;
	
	ll fill=2*R+1;
	ZERO(S);
	for(x=1,y=R;x<=R;x++) {
		while(round(hypot(x,y))>R) y--;
		fill+=y;
	}
	
	ll sum=1;
	for(i=1;i<=R;i++) {
		D[i]=D[i-1];
		while(round(hypot(D[i]+1,D[i]+1))<=i) D[i]++;
		if(round(sqrt(1LL*i*i-1LL*D[i]*D[i]))==D[i]) {
			sum++;
			sum+=2*D[i];
		}
		else {
			sum+=2*D[i];
			if(round(hypot(D[i]+1,D[i]))==i) sum+=2;
		}
		
	}
	cout<<"Case #"<<_loop<<": "<<(fill-sum)*4<<endl;
}

まとめ

「異なる半径の円周上のセルは重ならない」が最重要かな。