ARC083 C : Sugar Water(300)
作成日：2017.09.17
最終更新日：2017.09.17
問題概要
空のビーカーに水と砂糖を入れ、できるだけ濃度の高い砂糖水を作る。
行える操作は水を100A[g]100A[g]または100B[g]入れることと砂糖をC[g]またはD[g]入れることである。
水100[g]には砂糖はE[g]溶け、ビーカーには水と砂糖合わせてF[g]まで入れられる。
ビーカーに溶け残った砂糖がない時、条件を満たす砂糖水の質量と溶けている砂糖の質量を出力せよ。
答えが複数ある場合はいずれでも良い。
制約
1≤A<B≤30
1≤C<D≤30
1≤E≤100
100A≤F≤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行)