けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

diverta 2019 B - RGB Boxes (200 点)

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

f:id:drken1215:20190511234824p:plain

問題概要

 R, G, B を正の整数とする。

  •  Rx + Gy + Bz = N

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

制約

  •  1 \le R, G, B \le 3000

考えたこと

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

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;
    }
  }
}

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

  •  r, g を決めると、 b がどうなるべきかが決まる

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

  •  Rr + Gg \gt N だったらそもそもアウト
  •  N - Rr - Gg B の倍数じゃなかったらアウトで、 B の倍数だったら、 b = \frac{N - Rr - Gg}{B} であることが確定する

という感じになる。これであれば  O(N^{2}) の計算量で解くことができる。

#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;
}