前回の ABC に続いて、D 問題が数学っぽい。でも実際には今回は探索問題ですね。
問題概要
非負整数 を用いて
と表せる整数 を「特別数」と呼ぶことにします。
非負整数 が与えられますので、
以上である最小の「特別数」を求めてください。
制約
変数が複数あるときは 1 つを固定する
見た目は確かに数学色の強い問題だけど、考えるべき基礎は決して特別なものではない。
このように という 2 つの変数が絡む問題で考えるべきことは、1 つの変数を固定して考えるというもの。
ここでは を固定してみよう。たとえば
としたとしてみよう。このとき、
となる。これが 以上となるような最小の
を求めたいと思ったら、それはまさに二分探索法がどんぴしゃだ！！
つまり次のように求められる。
// 式計算 long long func(long long a, long long b) { return a*a*a + a*a*b + a*b*b + b*b*b; } // a を固定したときの N 以上の最小の特別数を求める long long solve(long long a) { long long low = -1, high = (十分大きな値); while (high - low > 1) { long long b = (low + high) / 2; if (func(a, b) >= N) high = b; else low = b; } return func(a, high); }
変数の範囲を考える
最後に検討すべきことは以下の 2 点だ
- 変数
の調べるべき範囲
- 変数
これを考える前に、 が「特別数」であることを確認しよう。具体的には
,
としたとき
となるのだ。よって という制約を考えると、
以上の最小の特別数が
より大きくなる可能性は考えなくて良いのだ！！！
そのことから、 の範囲を調べる必要がないことが言える。なぜなら
とすると
となるためだ。 より大きくなる範囲は考慮不要なので、
は考えなくてよい。
同様に を固定したとき、
が
以上となる最小の
を求めるための二分探索法の上限値も、
より大きく取る必要はない！！
以上より、次の結論が言える
- 変数
まで調べれば十分
- 変数
とすればよい
計算時間的にも十分に間に合う。一応計算量をちゃんと書くと、 と評価できる。
コード
#include <bits/stdc++.h> using namespace std; long long func(long long a, long long b) { return a*a*a + a*a*b + a*b*b + b*b*b; } long long solve(long long N, long long a) { long long low = -1, high = 1000000; while (high - low > 1) { long long b = (low + high) / 2; if (func(a, b) >= N) high = b; else low = b; } return func(a, high); } int main() { long long N; cin >> N; long long res = 1000000000000000000LL; // 10^18 が上限値 for (long long a = 0; a <= 1000000; ++a) { res = min(res, solve(N, a)); } cout << res << endl; }
別解：尺取り法
上述の「変数固定 + 二分探索」が比較的思いつきやすいと思う。一方そのような問題の多くは、尺取り法でも解けることが多いと思う。
そうすると計算量は に落ちる。注目することは
が
以上となるような最小の
は単調減少していく
ということだ。よって、 を増やしながら、
を減らしていくという「尺取り法」で十分高速に解ける。詳しくは公式解説へ！！
