https://atcoder.jp/contests/abc214/tasks/abc214_b
解説
https://atcoder.jp/contests/abc214/submissions/25065793
今回の問題は枝刈り全探索という方針を用いる。
全探索をしていくのだが、自明な「枝刈り」、つまり、探索を途中でストップすることで、
無駄な探索を大幅に省くことができて、高速化でき、ACできるということになる。
色々な場面でこのような方針は適用することができるが、その有効性を学ぶのによい問題であると思う。
全探索
枝刈りしない全探索を書く。
といっても既に一部枝刈り済みとも取れるが、a,b,cの範囲を雑に指定して探索していくことを考えてみよう。
a+b+cの総和がS以下である必要があるので、a,b,cは少なくとも0~Sの範囲になっているはずである。
よって、a,b,cを0~Sの範囲でループさせる3重ループを書くので、全部で109通りの組み合わせを確かめていく。
競プロでは組み合わせは多くても107通りくらいしか探索できないので、これでは間に合わない。
別の良い方をすると計算量がO(S3)となるので間に合わない。
「枝刈り」
ある一定のルールで探索をストップすることにする。
C++で言えばbreakを使ってループを途中で抜けることにする。
その一定のルールとは「a+b+c≦S」か「abc≦T」のどちらかが満たされなくなったら、即ループを抜けて終了する。
これだけで大幅に探索状態が削減されてTLE(計算時間超過)からACにすることができる。
気持ち沢山の探索範囲を減らせそうな感じはする。
特にabc≦Tという条件が割と厳しい。少し緩いab≦Tという条件で考えてみる。
T=100であるとき、a=1ならばb=1...100の100通りだが、a=2ならばb=1...50の50通りと半減してしまう。
aが大きくなれば使えるbはより急激に少なくなるし、abc≦Tならなおさらである。
より厳密な話
より厳密にこの枝刈りに正当性を与える知識をここに書いておく。
高度合成数 - Wikipedia
高度合成数という話があり、約数の個数は一般にかなり小さくなり、この小ささを利用してアルゴリズムを
作っていく問題も多くある。
abcの組はT以下の数の因数分解の結果となる。
Tの上限は10000であり、その場合の約数の個数の最大は72個なので、abcと3つの因数に分解する組合せも
かなり少なそうという仮定が立つ。
ここまで思考が進んでいれば、肌感でかなり間に合いそうな感じがする。
心配なら今回の問題ではS=100, T=10000で計算量が最大になるので、
これでコードテストを使ってストレステストしてもいい。
int S, T; //--------------------------------------------------------------------------------------------------- void _main() { cin >> S >> T; int ans = 0; rep(a, 0, S + 1) rep(b, 0, S + 1) rep(c, 0, S + 1) { if (S < a + b + c) break; if (T < a * b * c) break; ans++; } cout << ans << endl; }