代表的な全探索問題!
問題概要
2 つの整数 が与えられます。
3 つの 以上 以下の整数 の組であって、 を満たすものが何通りあるか求めよ。
制約
全探索
一目見てすごく数学色強そうで怖そうなのだけど、とりあえず答えを出すコードを求めるだけなら、すべての場合を調べてしまえばよい!!!
具体的には
- 以上 以下の整数
- 以上 以下の整数
- 以上 以下の整数
の組合せを全パターンを試して、そのうち を満たすものをカウントします。
int count = 0; for (int x = 0; x <= K; ++x) { for (int y = 0; y <= K; ++y) { for (int z = 0; z <= K; ++z) { if (x + y + z == S) { ++count; } } } }
しかし...
B 問題, 200 点問題だったら、これで通って欲しい。。。でもこれだと TLE (実行時間超過, Time Limit Exceeded) してしまう。
理由は以下の記事の 8 問目 - Otoshidama の解説に書いたのと同じなのだけど、for 文を三重にしているので、計算量は になっている。ここで最大ケースの を代入してみると が大体 くらいになる。しかし実行時間制限は くらいが限界なのだ。
改良
実は for 文を三重から二重に減らすことができます。例えば
- で
- , の場合を考えると
- は になるしかない
ということが見て取れます。つまり の値が決まった時点で、 のとるべき値は決まってしまうのです。そしてそれが実際に 以上 以下になっているかどうかを確かめてあげて、それを満たしていたらカウントするようにすればよいです。
これによって、z のループが消えて、for 文が二重になりました。計算量は に下がります!!!!!
今度こそ通ります!!!
#include <iostream> using namespace std; int main() { int K, S; cin >> K >> S; int count = 0; for (int x = 0; x <= K; ++x) { for (int y = 0; y <= K; ++y) { int z = S - x - y; if (z >= 0 && z <= K) { ++count; } } } cout << count << endl; }