文字を固定したり、数式処理したりなど、総合力が問われる問題!
問題概要
正の整数 が与えられる。非負整数 をすべて考えたときの、
の最小値を求めよ。
制約
まず、問題の理解
数学に慣れていないと、何がしたいのかわかりづらいと感じるかもしれない。
は、原点を中心とした半径 の円を表している。したがって、 の値を最小化したいというのは、原点を中心とした半径 の円周から最も距離が近い格子点を求めたいということだ (下図は evima さんのユーザ解説より)。
まず、全探索を考える
さて、この問題に対して、まず「 を全探索できないか」を考えたくなる。その際には の上限をどこまで調べればいいかを見積もることが必要となる。ここで重要な考察として、
- の値が を超えたら、もうそれ以上 を大きくする必要がない
- の値が を超えたら、もうそれ以上 を大きくする必要がない
ということが言える。
今回は という制約があるので、せいぜい 程度まで調べれば十分だ。しかし、これを調べると間に合わない。
を固定する
こういう時に有効なアプローチとして、「変数を 1 つ固定する」というのがある。今回は を固定してみよう。このとき、 と の値が最小となる を求めたいということになる。
もし、 であれば とすればよい。 であれば、つまり、 と の差が最小である を求めたいということになる。
ここまで来れば簡単だ。
- を の整数部分とする
- このとき、 という関係が成り立つ
- よって、 のうち、より に近い値が答え
となる。
以上より、 を固定したときの最適な の値は の計算量で求められるため、全体の計算量は となる。
コード
#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; }