ABC389 D問題（Squares in Circle）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）389 D問題をC++とPythonで解いてみました。ABC389は、2025年1月18日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Squares in Circle（Difficulty : 749）

問題の詳細は、リンク先をご覧ください。

ABC389 D問題 Squares in Circle

しゃくとり法によって求めます。AtCoder Problems による Difficulty は 749 でした。

解答案

C++ プログラム例（ABC389D）

正方形の中心座標は整数となります。$i =0$ または $j = 0$ となる含まれる正方形は、半径 $R$ に対して、$(R-1) \times 4+1$ 個となります（20行目）。最後に1個加えている正方形は、原点を中心とする正方形です。

それ以外の場所は、$i>0$ かつ $j>0$ の領域で求めた個数を4倍します。

$i$ 軸方向の中心は、$1 \leqq x \leqq (R-1) $ の値について調べます。この値について $j$ 方向に正方形がいくつあるかカウントします。$i$ を増やしていくと含まれる正方形の個数（$y$）の初期値を $R-1$ 個として、減らしていきます。

13行目から18行目のループは2重ループになっているように見えますが、$y$ の値は減っていくだけであるため $R^2$ 回評価されるわけではありません。しゃくとり法と呼ばれる処理です。

以下が、C++プログラムです。

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

int main()
{
	ll r;
	cin >> r;

	ll result = 0;
	int y = r - 1;
	for (int x = 1; x < r; ++x) {
		while ((x + 0.5) * (x + 0.5) + (y + 0.5) * (y + 0.5) > r * r) {
			--y;
		}
		result += y;
	}

	result = result * 4 + (r - 1) * 4 + 1;
	cout << result << endl;

	return 0;
}

14行目は浮動小数点で計算しました。この式を4倍すれば整数の演算として計算できます(2－4行目)。この計算では、浮動小数点数による演算誤差はありません。コード差分は以下となります。

	for (int x = 1; x < r; ++x) {
		while ((2LL * x + 1LL) * (2LL * x + 1LL) +
				   (2LL * y + 1LL) * (2LL * y + 1LL) >
			   4LL * r * r) {
			--y;
		}
		result += y;
	}

どちらも AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC389D）

Python版も基本的な考え方は同じです。整数版を移植しました。以下がプログラムです。

"""AtCoder Beginner Contest 389 D"""
r = int(input())

result = 0
y = r - 1
for x in range(1, r):
    while (2 * x + 1) ** 2 + (2 * y + 1) ** 2 > 4 * r * r:
        y -= 1
    result += y

result = result * 4 + (r - 1) * 4 + 1
print(result)

こちらも「AC」と判定されました。

最後に

今回のコンテストはD問題（Difficulty : 749）に対して、E問題以降は少なくとも青色レートとなり難易度の差が大きく手がでませんでした。

引き続き ABC の問題を紹介していきます。