diverta 2019 B - RGB Boxes (茶色, 200 点)

これと大体一緒かな。
むしろ合計枚数に関する制約がない分、やや難しくなっているかもしれない。

問題概要

を正の整数とする。

• 

を満たすような 0 以上の整数 の組が何通りあるか求めよ。

制約

• 

考えたこと

愚直に探索しようと思うと

int res = 0;
for (int r = 0; r <= N/R; ++r) {
  for (int g = 0; g <= N/G; ++g) {
    for (int b = 0; b <= N/B; ++b) {
     if (R * r + G * g + B * b == N) ++res;
    }
  }
}

という風にやりたくなる。が、これでは最悪 の計算量がかかってしまうので間に合わない。そこで、

• を決めると、 がどうなるべきかが決まる

ということに着目する。具体的には

• だったらそもそもアウト
• が の倍数じゃなかったらアウトで、 の倍数だったら、 であることが確定する

という感じになる。これであれば の計算量で解くことができる。

#include <iostream>
using namespace std;

int main() {
    long long R, G, B, N;
    cin >> R >> G >> B >> N;
    long long res = 0;
    for (long long r = 0; r <= N/R; ++r) {
        for (long long g = 0; g <= N/G; ++g) {
            if (r * R + g * G > N) continue;
            long long rem = N - r*R - g*G;
            if (rem % B != 0) continue;
            ++res;
        }
    }
    cout << res << endl;
}