【AtCoder】ABC 389 D - Squares in Circle | 緑コーダーが解くAtCoder

atcoder.jp

配点: 400 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 749

問題概要
制約
考察
実装例
コメント

問題概要

二次元座標平面上に $1\times 1$ の正方形が無限に敷き詰められている。

ある正方形の中心を中心として、半径 $R$ の円を描いたとき、円に完全に内包される正方形は何個あるか求めよ。

より厳密には、整数組 $(i,j)$ であって、4点 $(i+0.5,j+0.5),(i+0.5,j-0.5),(i-0.5,j+0.5),(i-0.5,j-0.5)$ 全てが原点との距離が $R$ 以下であるものの個数を求めよ。

制約

$1\leq R\leq 10^{6}$
入力される数値は全て整数。

考察

円の中心を原点とする新たな座標系を考える。このとき、円に完全に内包される正方形は以下の3つのグループに分類される。

円の中心が含まれる正方形
軸上の正方形
それ以外の正方形

これらのうち、上の二つについてはすぐに計算できる。

円の中心が含まれる正方形 : 1個
軸上の正方形 : $4(R - 1)$ 個

それ以外の正方形については、円の対称性を利用して、「第1象限内のものを数えて4倍する」ことにする。

肝心の数え方だが、これは $i = 1, 2, \cdots R - 1$ と見ていって、

$\sqrt{(i + 0.5)^2 + (j + 0.5)^2} \leq R \: \Leftrightarrow \: (i + 0.5)^2 + (j + 0.5)^2 \leq R^2$

を満たすような $j$ を尺取り法によって決定し、そのような $j$ を答えに加算していけばよい。

これは、 $y = \sqrt{R^2 - x^2} \: (x, y \geq 0)$ のグラフの単調減少性を利用している。

なお、全体の計算量は $O(R)$ となり、本問の制約下で十分高速である。

実装時はオーバーフローに注意すること。

実装例

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

using ll = long long;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

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

    ll ans = (R - 1) * 4 + 1;

    ll j = R;
    ll cnt = 0;
    rep(i, 1, R)
    {
        while (!((i + 0.5) * (i + 0.5) + (j + 0.5) * (j + 0.5) <= R * R))
        {
            j--;
        }

        cnt += j;
    }

    ans += cnt * 4;

    cout << ans << endl;

    return 0;
}