https://products.sint.co.jp/hubfs/resource/topsic/pgb/2-2.pdf
解説
入力例で正しいことしか確認できていません!落ちる可能性ありますので、ご注意ください
まずO(N2)の解法はすぐに思いつく。
生物aがx匹、生物bがy匹、生物cがz匹とすると、xとyを全探索するとzは一意に定まるので、O(N2)で全探索可能。
しかし、これでは間に合わないので、工夫をする。
xを固定すると、
y+z=N-x
By+Cz=M-Ax
であり、各方程式の右辺は定数となるので、2次方程式となる。
S=N-x, T=M-Axとすると、
y+z=S
By+Cz=T
By+Bz=BS
By+Cz=T
(B-C)z=BS-T
z=(BS-T)/(B-C)
これでzが求まるので、yも求まる。
zが有効な値(整数値で0≦z≦N-x)であればそれが答え。
B-C=0のときが注意。
B=Cということなので、
y+z=S
By+Bz=T
By+Bz=BS
By+Bz=T
0=BS-T
これを満たす必要がある。
これを満たしていれば、適当なy,zで条件を満たす。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) #define fore(i,a) for(auto &i:a) #define all(x) (x).begin(),(x).end() //#pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60; template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } //--------------------------------------------------------------------------------------------------- /*--------------------------------------------------------------------------------------------------- ∧_∧ ∧_∧ (´<_` ) Welcome to My Coding Space! ( ´_ゝ`) / ⌒i @hamayanhamayan / \ | | / / ̄ ̄ ̄ ̄/ | __(__ニつ/ _/ .| .|____ \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ ll N, M, A, B, C; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M >> A >> B >> C; rep(x, 0, N + 1) { ll S = N - x; ll T = M - A * x; ll up = B * S - T; ll dwn = B - C; if (dwn == 0) { if (up == 0) { ll z = 0; ll y = N - x - z; printf("%d %lld %lld\n", x, y, z); return; } continue; } if (up % dwn != 0) continue; ll z = up / dwn; if (0 <= z and z <= N - x) { ll y = N - x - z; printf("%d %lld %lld\n", x, y, z); return; } } printf("-1 -1 -1\n"); }