C - Sugar Water

競プロ

はじめに

競技プログラミング、AtCoder Beginner Contest 74
C - Sugar Water
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

すぬけ君はビーカーに砂糖水を作ろうとしています。 
最初ビーカーは空です。
すぬけ君は以下の4種類の操作をそれぞれ何回でも行うことができます。
一度も行わない操作があっても構いません。

・操作 1: ビーカーに水を100A[g] 入れる。
・操作 2: ビーカーに水を100B[g] 入れる。
・操作 3: ビーカーに砂糖をC[g] 入れる。
・操作 4: ビーカーに砂糖をD[g] 入れる。

すぬけ君の実験環境下では、水100[g] あたり砂糖はE[g] 溶けます。

すぬけ君はできるだけ濃度の高い砂糖水を作りたいと考えています。

ビーカーに入れられる物質の質量 (水の質量と砂糖の質量の合計)がF[g] 以下であり、
ビーカーの中に砂糖を溶け残らせてはいけないとき、 
すぬけ君が作る砂糖水の質量と、それに溶けている砂糖の質量を求めてください。 
答えが複数ある場合はどれを答えても構いません。

水a[g] と砂糖b[g] を混ぜた砂糖水の濃度は100ba+b[%]です。 
また、この問題では、砂糖が全く溶けていない水も濃度0[%] の砂糖水と考えることにします。

制約

・1≦A<B≦30
・1≦C<D≦30
・1≦E≦100
・100A≦F≦3,000
・A,B,C,D,E,Fはすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

A B C D E F

出力

整数を空白区切りで2つ出力せよ。 
1つ目は求める砂糖水の質量、
2つ目はそれに溶けている砂糖の質量とせよ。

解き方

以下を参考にしています。
https://img.atcoder.jp/arc083/editorial.pdf

考える要素が多いことと
「制約」を見るとどれも数が小さいので
どこから手を付けていいのか分からなくなりますが
この問題では
「砂糖水の量」と「ビーカーに入れられる物質の質量の上限（F）」に
注目すると解くことができます。

まず、
ビーカーに入れる水の量を式であらわすと以下のようになります。
ビーカーにAを入れる回数（操作１をする回数）を「i」とする
ビーカーにBを入れる回数（操作２をする回数）を「j」とする

(A*100)*i+(B*100)*j


また、
ビーカーに入れる砂糖の量を式であらわすと以下のようになります。
ビーカーにCを入れる回数（操作３をする回数）を「k」とする
ビーカーにDを入れる回数（操作４をする回数）を「l」とする

(C*100)*k+(D*100)*l


そして、
「ビーカーに入れる水の量」と「ビーカーに入れる砂糖の量」は
「ビーカーに入れられる物質の質量の上限（F）」を超えることはないので
以下の式が成り立ちます。

(A*100)*i+(B*100)*j+(C*100)*k+(D*100)*l<=F


この式を利用して４重のループを回します。
一番外側のループをA、
二番目のループをB、
三番目をC、
四番目をDとすると以下のようになります。

・A（ループのindexは「i」）
「i」が取り得る値は「０～( F / ( A×100 ))」

「( F / ( A×100 ))」は
ビーカーに入れられる物質の質量の中で
Aを最大まで入れようとした時の値


・B（ループのindexは「j」）
「j」が取り得る値は「０～( F - ( A × i × 100 )) / ( B × 100 )」

「(F - ( A × i × 100 )) / ( B × 100 )」は
ビーカーに入れられる物質の質量の中から
Aが入っている量を除いて
Bを最大まで入れようとした時の値


・C（ループのindexは「k」）
「k」が取り得る値は「０～( F - ( A × i × 100 + B × j × 100 )) / C」

「( F - ( A × i × 100 + B × j × 100 )) / C」は
ビーカーに入れられる物質の質量の中から
AとBが入っている量を除いて
Cを最大まで入れようとした時の値


・D（ループのindexは「l」）
「l」が取り得る値は「０～ ( F - ( A × i × 100 + B × j × 100 + C )) / D」

「( F - ( A × i × 100 + B × j × 100 + C )) / D」は
ビーカーに入れられる物質の質量の中から
AとBとCが入っている量を除いて
Dを最大まで入れようとした時の値

これをコードにすると以下のようになります。

//A
//AがFを上限として最大まで入れられる回数
var waterAmax = F / (A * 100);
for (int i = 0; i <= waterAmax; ++i)
{
     //B
     //BがFを上限として最大まで入れられる回数
    var bCount = (F - (A * i * 100)) / (B * 100);
    for (int j = 0; j <= bCount; ++j)
    {
        //水が入っていないことはあり得ない(砂糖が溶け残る場合はNG)ので「i」と「j」がどちらも０だった場合はcontinueする
        if (i == 0 && j == 0) continue;

        //C
        //CがFを上限として最大まで入れられる回数
        var cCount = (F - (A * i * 100 + B * j * 100)) / C;
        for (int k = 0; k <= cCount; ++k)
        {

            //D
            //DがFを上限として最大まで入れられる回数
            var dCount = (F - ((A * i * 100 + B * j * 100) + C * k)) / D;
            for (int l = 0; l <= dCount; ++l)
            {
                //処理
            }
        }
    }
}

Bのループの中で
Aのループのindexである「i」と
Bのループのindexである「j」が
どちらも「０」だった場合に
continueをしています。

これは、
問題文から
砂糖を溶け残るパターンは省かなければいけないからです。
（水がなければ必ず砂糖だけになってしまう）

コードの中の「//処理」の部分に到達するものは
「ビーカーの中の物質の質量」がF以下のものなので
この中からさらに
砂糖が溶け残るパターンを除いて、
濃度を出し
保存していた濃度よりも高ければ
値を書き換えるということを
行えば問題の答えがでます。

//砂糖が溶け残らないかどうか
 if ((C * k + D * l) <= (i*A + j*B) * E)
{
     //砂糖水の量
     var sugarWater = (A * i)*100 + (B * j)*100 + C * k + D * l;
    //砂糖の量
    var sugar = C * k + D * l;

    //濃度
    var concentration = sugar == 0 ? 0 : sugar / sugarWater * 100;

    //濃度が保存してあるものよりも高ければ情報を書き換える
    if (max < concentration)
    {
        max = concentration;
        maxSugarWater = sugarWater;
        maxSugar = sugar;
        }
    }

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Cmondai
{
    static void Main()
    {
        var line = Console.ReadLine().Split(' ').Select(x => decimal.Parse(x)).ToArray();
        var A = line[0];
        var B = line[1];
        var C = line[2];
        var D = line[3];
        var E = line[4];
        var F = line[5];

        //濃度（濃度を保存しておく変数）
        decimal max = -1;
        //砂糖水の量（砂糖水の量を保存しておく変数）
        decimal maxSugarWater =0;
        //砂糖の量（砂糖の量を保存しておく変数）
        decimal maxSugar = 0;

        //A
        //AがFを上限として最大まで入れられる回数
        var waterAmax = F / (A * 100);
        for (int i = 0; i <= waterAmax; ++i)
        {
            //B
            //BがFを上限として最大まで入れられる回数
            var bCount = (F - (A * i * 100)) / (B * 100);
            for (int j = 0; j <= bCount; ++j)
            {
                //水が入っていないことはあり得ない(砂糖が溶け残る場合はNG)ので「i」と「j」がどちらも０だった場合はcontinueする
                if (i == 0 && j == 0) continue;

                //C
                //CがFを上限として最大まで入れられる回数
                var cCount = (F - (A * i * 100 + B * j * 100)) / C;
                for (int k = 0; k <= cCount; ++k)
                {

                    //D
                    //DがFを上限として最大まで入れられる回数
                    var dCount = (F - ((A * i * 100 + B * j * 100) + C * k)) / D;
                    for (int l = 0; l <= dCount; ++l)
                    {

                        //砂糖が溶け残らないかどうか
                        if ((C * k + D * l) <= (i*A + j*B) * E)
                        {
                            //砂糖水の量
                            var sugarWater = (A * i)*100 + (B * j)*100 + C * k + D * l;
                            //砂糖の量
                            var sugar = C * k + D * l;

                            //濃度
                            var concentration = sugar == 0 ? 0 : sugar / sugarWater * 100;

                            //濃度が保存してあるものよりも高ければ情報を書き換える
                            if (max < concentration)
                            {
                                max = concentration;
                                maxSugarWater = sugarWater;
                                maxSugar = sugar;
                            }
                        }
                    }
                }
            }
        }
        Console.WriteLine($"{maxSugarWater} {maxSugar}");
    }
}