C++ の動作確認をしてみた（４５）

C++の練習を兼ねて, AtCoder Beginner Contest 034 の問題C（経路) ～問題D (食塩水) を解いてみた.

■感想.
1. 問題C は, AtCoder Beginner Contest 042 問題D (いろはちゃんとマス目 / Iroha and a Grid) と類似しているように見えたので, この問題の解答をベースに, 対応した.
2. 問題D は, 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
但し, おおよそ, このような内容を解答で説明されているだろう, との推測が多分に含まれていると思われる.
※例えば, テストケース s1.txt の WA回避対応で, 小数第10桁までを出力するように修正している.

本家のサイトAtCoder Beginner Contest 034 解説をご覧下さい.

■C++版プログラム(問題C／AC版).

// AtCoder Beginner Contest 042 問題D (いろはちゃんとマス目 / Iroha and a Grid)
// -> 上記問題をベースに対応.
#include <bits/stdc++.h>

using namespace std;

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

typedef long long LL;

const LL MOD = 1e9 + 7;

// Fermat's little theorem を 適用するため, 大きな冪乗の計算ができるようにする.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL inverse(LL a, LL b){
    LL t = 1;
    while(b) {
        if(b & 1) t = (t * a) % MOD;
        a *= a;
        a %= MOD;
        b >>= 1;
    }
    return t % MOD;
}

int main() {
    
    // 1. 入力情報取得.
    LL W, H;
    cin >> W >> H;
    
    // 2. 経路数 (H + W - 2)! ÷ (H - 1)! ÷ (W - 1)! を 計算.
    // 2-1. 0 ≦ x ≦ H + W - 2 の x!(MOD版) を 計算.
    LL LIMIT = H + W - 2;
    LL FAC[LIMIT + 1] = {};
    FAC[0] = 1;
    FOR(i, 1, LIMIT + 1) FAC[i] = i * FAC[i - 1] % MOD;
    
    // 2-2. 0 ≦ x ≦ H + W - 2 の x!(MOD版)の逆元 を 計算.
    LL INV[LIMIT + 1] = {};
    FOR(i, 0, LIMIT + 1) INV[i] = inverse(FAC[i], MOD - 2) % MOD;
    
    // 2-3. 経路数を計算.
    LL ans = 0LL;
    ans = FAC[H + W - 2];
    ans *= INV[H - 1];
    ans %= MOD;
    ans *= INV[W - 1];
    ans %= MOD;
    
    // 3. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;
    
}

// AtCoder Beginner Contest 042 問題D (いろはちゃんとマス目 / Iroha and a Grid)

// -> 上記問題をベースに対応.

#include <bits/stdc++.h>

using namespace std;

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

typedef long long LL;

const LL MOD = 1e9 + 7;

// Fermat's little theorem を適用するため, 大きな冪乗の計算ができるようにする.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL inverse(LL a, LL b){

LL t = 1;

while(b) {

if(b & 1) t = (t * a) % MOD;

a *= a;

a %= MOD;

b >>= 1;

}

return t % MOD;

}

int main() {

// 1. 入力情報取得.

LL W, H;

cin >> W >> H;

// 2. 経路数 (H + W - 2)! ÷ (H - 1)! ÷ (W - 1)! を計算.

// 2-1. 0 ≦ x ≦ H + W - 2 の x!(MOD版) を計算.

LL LIMIT = H + W - 2;

LL FAC[LIMIT + 1] = {};

FAC[0] = 1;

FOR(i, 1, LIMIT + 1) FAC[i] = i * FAC[i - 1] % MOD;

// 2-2. 0 ≦ x ≦ H + W - 2 の x!(MOD版)の逆元を計算.

LL INV[LIMIT + 1] = {};

FOR(i, 0, LIMIT + 1) INV[i] = inverse(FAC[i], MOD - 2) % MOD;

// 2-3. 経路数を計算.

LL ans = 0LL;

ans = FAC[H + W - 2];

ans *= INV[H - 1];

ans %= MOD;

ans *= INV[W - 1];

ans %= MOD;

// 3. 出力～後処理.

cout << ans << endl;

return 0;

}

■C++版プログラム(問題D／AC版).

// 解き直し.
// AtCoder Beginner Contest 034 解説.
// https://www.slideshare.net/chokudai/abc034
#include <bits/stdc++.h>

using namespace std;

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

typedef long long LL;

struct solution {
    LL w;  // 食塩水(グラム).
    LL p;  // 濃度(パーセント).
    double c;  // 計算上の濃度から過不足する食塩量(グラム).
};

// 指定した濃度の食塩水が作成可能であるかを確認.
// @param v: 食塩水の入った容器.
// @param x: 指定した濃度.
// @param K: 選択する容器数.
// @return: 
//    true:  指定した濃度の食塩水を作ることが可能である.
//    false: 指定した濃度の食塩水を作ることが不可能である.
bool check(vector<solution> v, double x, LL K) {
    
    // 食塩の過不足を確認,
    FOR(i, 0, v.size()) v[i].c = v[i].w * (v[i].p - x) / 100;
    
    // 過不足する食塩量で, 降順sort.
    sort(v.begin(), v.end(), [](const solution& x, const solution& y) {return x.c > y.c;});
    
    // 容器を, K個選択して, 食塩水を作ってみる.
    double wTotal = 0.0; // 食塩水の総量.
    double sTotal = 0.0; // 食塩の総量.
    FOR(i, 0, K) wTotal += v[i].w, sTotal += v[i].w * v[i].p;
    double ret = sTotal * 1.0 / wTotal;
    // cout << ret << endl;
    
    // 指定した濃度の食塩水を作ることが 可能 か 不可能か？
    if(ret >= x) return true;
    else         return false;

}

int main() {
    
    // 1. 入力情報取得.
    LL N, K;
    cin >> N >> K;
    vector<solution> v; // 食塩水に関する情報.
    FOR(i, 0, N) {
        LL w, p;
        cin >> w >> p;
        solution s;
        s.w = w;
        s.p = p;
        s.c = 0.0;
        v.push_back(s);
    }
    
    // 2. 解説通り.
    // -> 2分法使う.
    int counter = 0;
    double lower = 0.0;   // 食塩水濃度の下限.
    double upper = 100.0; // 食塩水濃度の上限.
    double ans = 0.0;     // 最終的に求めたい食塩水の濃度.
    while(counter < 50) {
        ans = (lower + upper) / 2;
        if(check(v, ans, K)) lower = ans;
        else                 upper = ans;
        counter++;
    }
    
    
    // 4. 出力 ～ 後処理.
    // s1.txt の WA回避対応.
    // -> AtCoderテストケース(25.000000000)より, 小数第10桁までで出力するように修正.
    cout << fixed;
    cout << setprecision(10) << ans << endl;
    return 0;
    
}

// 解き直し.

// AtCoder Beginner Contest 034 解説.

// https://www.slideshare.net/chokudai/abc034

#include <bits/stdc++.h>

using namespace std;

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

typedef long long LL;

struct solution {

LL w; // 食塩水(グラム).

LL p; // 濃度(パーセント).

double c; // 計算上の濃度から過不足する食塩量(グラム).

};

// 指定した濃度の食塩水が作成可能であるかを確認.

// @param v: 食塩水の入った容器.

// @param x: 指定した濃度.

// @param K: 選択する容器数.

// @return:

// true: 指定した濃度の食塩水を作ることが可能である.

// false: 指定した濃度の食塩水を作ることが不可能である.

bool check(vector<solution> v, double x, LL K) {

// 食塩の過不足を確認,

FOR(i, 0, v.size()) v[i].c = v[i].w * (v[i].p - x) / 100;

// 過不足する食塩量で, 降順sort.

sort(v.begin(), v.end(), [](const solution& x, const solution& y) {return x.c > y.c;});

// 容器を, K個選択して, 食塩水を作ってみる.

double wTotal = 0.0; // 食塩水の総量.

double sTotal = 0.0; // 食塩の総量.

FOR(i, 0, K) wTotal += v[i].w, sTotal += v[i].w * v[i].p;

double ret = sTotal * 1.0 / wTotal;

// cout << ret << endl;

// 指定した濃度の食塩水を作ることが可能か不可能か？

if(ret >= x) return true;

else return false;

}

int main() {

// 1. 入力情報取得.

LL N, K;

cin >> N >> K;

vector<solution> v; // 食塩水に関する情報.

FOR(i, 0, N) {

LL w, p;

cin >> w >> p;

solution s;

s.w = w;

s.p = p;

s.c = 0.0;

v.push_back(s);

}

// 2. 解説通り.

// -> 2分法使う.

int counter = 0;

double lower = 0.0; // 食塩水濃度の下限.

double upper = 100.0; // 食塩水濃度の上限.

double ans = 0.0; // 最終的に求めたい食塩水の濃度.

while(counter < 50) {

ans = (lower + upper) / 2;

if(check(v, ans, K)) lower = ans;

else upper = ans;

counter++;

}

// 4. 出力～後処理.

// s1.txt の WA回避対応.

// -> AtCoderテストケース(25.000000000)より, 小数第10桁までで出力するように修正.

cout << fixed;

cout << setprecision(10) << ans << endl;

return 0;

}

[入力例]
3 2
100 15
300 20
200 30

[出力例]
25.0000000000
※AtCoderテストケースより

[入力例]
3 2
100 60
300 25
200 30

[出力例]
40.0000000000

[入力例]
6 3
100 30
200 20
300 50
400 40
500 15
600 25

[出力例]
42.5000000000
※(300, 5), (400, 40), (100, 30) を 選択すると, 42.5000000000% を実現できる.

[入力例]
10 4
100 60
200 30
300 40
400 45
500 40
600 50
700 30
800 25
900 20
1000 35

[出力例]
47.1428571429
※(100, 60), (300, 40), (400, 45), (600, 50) を 選択すると, 47.1428571429% を実現できる.

[入力例]
1 1
1 0

[出力例]
0.0000000000
-> 仮に, 小数点以下10桁指定しないと, 7.88861e-29 のように出力される.
-> このように, 0 と出力されないので, s1.txt で, WA判定されたと推測した.

[入力例]

3 2

100 15

300 20

200 30

[出力例]

25.0000000000

※AtCoderテストケースより

[入力例]

3 2

100 60

300 25

200 30

[出力例]

40.0000000000

[入力例]

6 3

100 30

200 20

300 50

400 40

500 15

600 25

[出力例]

42.5000000000

※(300, 5), (400, 40), (100, 30) を選択すると, 42.5000000000% を実現できる.

[入力例]

10 4

100 60

200 30

300 40

400 45

500 40

600 50

700 30

800 25

900 20

1000 35

[出力例]

47.1428571429

※(100, 60), (300, 40), (400, 45), (600, 50) を選択すると, 47.1428571429% を実現できる.

[入力例]

1 1

1 0

[出力例]

0.0000000000

-> 仮に, 小数点以下10桁指定しないと, 7.88861e-29 のように出力される.

-> このように, 0 と出力されないので, s1.txt で, WA判定されたと推測した.

■参照サイト
AtCoder Beginner Contest 034

C++の練習を兼ねて, AtCoder Beginner Contest 034 の 問題C（経路) ～ 問題D (食塩水) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 034 の問題C（経路) ～問題D (食塩水) を解いてみた.

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