How many? [AtCoder Beginner Contest 214 B]

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重ループを書くので、全部で10⁹通りの組み合わせを確かめていく。
競プロでは組み合わせは多くても10⁷通りくらいしか探索できないので、これでは間に合わない。
別の良い方をすると計算量がO(S³)となるので間に合わない。

「枝刈り」

ある一定のルールで探索をストップすることにする。
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;
}