文字を固定したり、数式処理したりなど、総合力が問われる問題！

問題へのリンク

問題概要

正の整数 $D$ が与えられる。非負整数 $x, y$ をすべて考えたときの、

$|x^{2} + y^{2} - D|$

の最小値を求めよ。

制約

$1 \le D \le 2 \times 10^{12}$

まず、問題の理解

数学に慣れていないと、何がしたいのかわかりづらいと感じるかもしれない。

$x^{2} + y^{2} = D$

は、原点を中心とした半径 $\sqrt{D}$ の円を表している。したがって、 $|x^{2} + y^{2} - D|$ の値を最小化したいというのは、原点を中心とした半径 $\sqrt{D}$ の円周から最も距離が近い格子点を求めたいということだ (下図は evima さんのユーザ解説より)。

まず、全探索を考える

さて、この問題に対して、まず「 $x, y$ を全探索できないか」を考えたくなる。その際には $x, y$ の上限をどこまで調べればいいかを見積もることが必要となる。ここで重要な考察として、

$x^{2}$ の値が $D$ を超えたら、もうそれ以上 $x$ を大きくする必要がない
$y^{2}$ の値が $D$ を超えたら、もうそれ以上 $y$ を大きくする必要がない

ということが言える。

今回は $D \le 2 \times 10^{12}$ という制約があるので、せいぜい $x, y \le 1500000$ 程度まで調べれば十分だ。しかし、これを調べると間に合わない。

$x$ を固定する

こういう時に有効なアプローチとして、「変数を 1 つ固定する」というのがある。今回は $x$ を固定してみよう。このとき、 $y^{2}$ と $D - x^{2}$ の値が最小となる $y$ を求めたいということになる。

もし、 $D - x^{2} \le 0$ であれば $y = 0$ とすればよい。 $D - x^{2} \gt 0$ であれば、つまり、 $y$ と $\sqrt{D - x^{2}}$ の差が最小である $y$ を求めたいということになる。

ここまで来れば簡単だ。

$Y$ を $\sqrt{D - x^{2}}$ の整数部分とする
このとき、 $Y \le \sqrt{D - x^{2}} \le Y + 1$ という関係が成り立つ
よって、 $Y. Y+1$ のうち、より $\sqrt{D - x^{2}}$ に近い値が答え

となる。

以上より、 $x$ を固定したときの最適な $y$ の値は $O(1)$ の計算量で求められるため、全体の計算量は $O(\sqrt{N})$ となる。

コード

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

int main() {
    long long D;
    cin >> D;
    
    long long res = D;
    for (long long x = 0; x <= 2000000; ++x) {
        if (x * x >= D) {
            res = min(res, x * x - D);
        } else {
            long long y = sqrt(D - x * x);
            res = min(res, abs(x * x + y * y - D));
            res = min(res, abs(x * x + (y+1) * (y+1) - D));
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 330 C - Minimize Abs 2 (3Q, 茶色, 300 点)

問題概要

制約

まず、問題の理解

まず、全探索を考える

$x$ を固定する

コード