C++ の動作確認をしてみた（１２）

C++の練習を兼ねて, AtCoder Beginner Contest 074 の問題C（Sugar Water）を解いてみた.

■感想.
1. 結構解ききるまでに, 結構苦労した.
2. 濃度の上限 100 × E / (100 + E) に関するバグを修正するのに, 時間かかってしまった.
3. テストケース 01.txt が, 通過しなかったので, 試行錯誤の結果, 濃度上限が, 0% のパターンと推定して,
砂糖水が, 100 × A [g] あると仮定して, 漸く全テストケースを通過した.

本家のサイトARC083 / ABC074 解説をご覧下さい.

■C++版プログラム

#include <iostream>

using namespace std;

#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define max(x, y) ((x > y) ? x : y)

int main() {
    
    // 1. 入力情報取得.
    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;
    
    // 2. 濃度の最も高い砂糖水を探索.
    int sugar = 0;
    int sugarWater = 0;
    double maxConcentration = 0;
    // double limitConcentration = 100 * E / (100 + E);
    // -> 整数値(limitConcentration = 35) となるバグ(※コーディング誤り)を確認した.
    
    // 以下のように修正して, limitConcentration = (100 * 55) / (100 + 55) = 35.4839 を確認できた.
    double limitConcentration = 100.0 * E / (100.0 + E);
    //cout << "limitConcentration = " << limitConcentration << endl;
    
    // 操作1 の 最大回数.
    int aMax = F / (100 * A);
    FOR(a, 0, aMax + 1) {
        // 操作2 の 最大回数.
        int bMax = (F - (100 * A * a)) / (100 * B);
        FOR(b, 0, bMax + 1) {
            if(a == 0 && b == 0) continue;
            // 操作3 の 最大回数.
            int cMax = (F - (100 * A * a) - (100 * B * b)) / C;
            FOR(c, 0, cMax + 1) {
                // 操作4 の 最大回数.
                int dMax = (F - (100 * A * a) - (100 * B * b) - C * c) / D;
                FOR(d, 0, dMax + 1) {
                    // 濃度計算.
                    double concentration = 0.0;
                    int sg  = C * c + D * d;
                    int sgw = 100 * A * a + 100 * B * b + C * c + D * d;
                    
                    // 2-1. 砂糖の質量を加算し, 100倍.
                    concentration += sg;
                    concentration *= 100;
                    
                    // 2-2. 砂糖水の質量で除算.
                    concentration /= sgw;
                    
                    // 2-3. 過去の最高濃度と比較し, 更新.
                    // ビーカーの中に砂糖を解け残らせない … concentration <= limitConcentration
                    // 砂糖水の質量上限は, F[g] … sgw <= F
                    // 
                    // なぜか, 入力例) 17 19 22 26 55 2802 の 場合に, 
                    // a = 1, b = 0, c = 7, d = 29 で, 探索が止まる(本来は, dMax = 36 なので, d = 30 も 調査対象).
                    // -> 本件バグは, limitConcentration = (100 * 55) / (100 + 55) = 35 と計算されていたことが原因.
                    if(concentration > maxConcentration && concentration <= limitConcentration && sgw <= F) {
                        maxConcentration = concentration;
                        sugar = sg;
                        sugarWater = sgw;
                    }
                }
            }
        }
    }
    
    // 3. 出力 ～ 後処理.
    // cout << sugarWater << " " << sugar << endl;
    // テストケース 01.txt が, 通過出来なかったので, max(sugarWater, 100 * A) に置き換えた.
    cout << max(sugarWater, 100 * A) << " " << sugar << endl;
    return 0;
    
}

#include <iostream>

using namespace std;

#define FOR(i, a, b) for(int i=(a); i<(b); ++i)

#define max(x, y) ((x > y) ? x : y)

int main() {

// 1. 入力情報取得.

int A, B, C, D, E, F;

cin >> A >> B >> C >> D >> E >> F;

// 2. 濃度の最も高い砂糖水を探索.

int sugar = 0;

int sugarWater = 0;

double maxConcentration = 0;

// double limitConcentration = 100 * E / (100 + E);

// -> 整数値(limitConcentration = 35) となるバグ(※コーディング誤り)を確認した.

// 以下のように修正して, limitConcentration = (100 * 55) / (100 + 55) = 35.4839 を確認できた.

double limitConcentration = 100.0 * E / (100.0 + E);

//cout << "limitConcentration = " << limitConcentration << endl;

// 操作1 の最大回数.

int aMax = F / (100 * A);

FOR(a, 0, aMax + 1) {

// 操作2 の最大回数.

int bMax = (F - (100 * A * a)) / (100 * B);

FOR(b, 0, bMax + 1) {

if(a == 0 && b == 0) continue;

// 操作3 の最大回数.

int cMax = (F - (100 * A * a) - (100 * B * b)) / C;

FOR(c, 0, cMax + 1) {

// 操作4 の最大回数.

int dMax = (F - (100 * A * a) - (100 * B * b) - C * c) / D;

FOR(d, 0, dMax + 1) {

// 濃度計算.

double concentration = 0.0;

int sg = C * c + D * d;

int sgw = 100 * A * a + 100 * B * b + C * c + D * d;

// 2-1. 砂糖の質量を加算し, 100倍.

concentration += sg;

concentration *= 100;

// 2-2. 砂糖水の質量で除算.

concentration /= sgw;

// 2-3. 過去の最高濃度と比較し, 更新.

// ビーカーの中に砂糖を解け残らせない … concentration <= limitConcentration

// 砂糖水の質量上限は, F[g] … sgw <= F

// なぜか, 入力例) 17 19 22 26 55 2802 の場合に,

// a = 1, b = 0, c = 7, d = 29 で, 探索が止まる(本来は, dMax = 36 なので, d = 30 も調査対象).

// -> 本件バグは, limitConcentration = (100 * 55) / (100 + 55) = 35 と計算されていたことが原因.

if(concentration > maxConcentration && concentration <= limitConcentration && sgw <= F) {

maxConcentration = concentration;

sugar = sg;

sugarWater = sgw;

}

// 3. 出力～後処理.

// cout << sugarWater << " " << sugar << endl;

// テストケース 01.txt が, 通過出来なかったので, max(sugarWater, 100 * A) に置き換えた.

cout << max(sugarWater, 100 * A) << " " << sugar << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 074

C++の練習を兼ねて, AtCoder Beginner Contest 074 の 問題C（Sugar Water）を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 074 の問題C（Sugar Water）を解いてみた.

コメントを残すコメントをキャンセル