ARC083 C : Sugar Water(300)
作成日：2017.09.17
最終更新日：2017.09.17
問題概要
空のビーカーに水と砂糖を入れ、できるだけ濃度の高い砂糖水を作る。
行える操作は水を$100A[g]$または$100B[g]$入れることと砂糖を$C[g]$または$D[g]$入れることである。
水$100[g]$には砂糖は$E[g]$溶け、ビーカーには水と砂糖合わせて$F[g]$まで入れられる。
ビーカーに溶け残った砂糖がない時、条件を満たす砂糖水の質量と溶けている砂糖の質量を出力せよ。
答えが複数ある場合はいずれでも良い。
制約
$1 \leq A < B \leq 30$
$1 \leq C < D \leq 30$
$1 \leq E \leq 100$
$100A \leq F \leq 3000$
$A,B,C,D,E,F$は整数
考え方
ある決まった量の水または砂糖を入れることができるかは、少ない量から考えることで$O(F)$で求められる。
ビーカーに入れる水の量を決めれば、ビーカーから溢れず水に溶けきる最大の砂糖の量も$E,F$によって決められる。
また、その量以下で入れることができる最大の量の砂糖を入れることが最善であることは明らかである。
つまり、あり得る水の量をすべて試すことで求める解が得られる。
ソースコード
マクロ等はこちら
const int MC = 3010;
int A,B,C,D,E,F;
bool W[31];
int S[MC];
int ansW,ansS;
int main(){
cin >> A >> B >> C >> D >> E >> F;
fill(S,S+MC,-1);
S[0] = 0;
repp(i,0,MC){
if(S[i] < 0){
S[i] = S[i-1];
continue;
}
if(i+C<MC) S[i+C] = i+C;
if(i+D<MC) S[i+D] = i+D;
}
W[0] = 1;
ansW = A;
repp(i,0,31){
if(!W[i]) continue;
if(i+A<31) W[i+A] = 1;
if(i+B<31) W[i+B] = 1;
if(i==0) continue;
if(100*i > F) break;
int tmp = min(S[E*i],F-100*i);
if(ansS * (100*i+tmp) < tmp * (100*ansW + ansS)){
ansW = i;
ansS = tmp;
}
}
cout << 100*ansW+ansS << ' ' << ansS << endl;
return 0;
}解法まとめ
ある量以下で入れることができる最大の砂糖の量を求める。(10-18行)
水の量を決めれば最適な砂糖の入れ方は一意に定まる。
入れることができる水の量をすべて試し、そのうち濃度が最大となるものが解である。(19-33行)