はまやんはまやんはまやん

hamayanhamayan's blog

Win Percentages [CSAcademy #59 B]

https://csacademy.com/contest/round-59/task/win-percentages/statement/

G1回ゲームをして勝率がP1パーセントだった。
そこから更にG2-G1回ゲームをして、合計G2回で勝率がP2パーセントになった。
G2-G1回ゲームをしている中で最大何回ゲームに勝ったといえるか。
なお、パーセントは全て切り捨てで計算されている。
最大を計算するのは、切り捨てによる誤差があるためである。

解法

G1回中w1回、G2回中w2回ゲームに勝利したとする。
まずG2-G1回ゲームをする中での勝ちゲーム数を最大化するが、これはw2を最大化し、w1を最小化することで達成できる。
 
まず、G1とP1からw1を計算する時に考えうる中で最も小さいものを計算する。
w1は[0,G1]であり、O(10^6)なので全探索で計算して構わない。
切り捨てで条件を満たすものを探す。
 
同様にG2とP2からw2を計算する時に考えうる中で最も大きいものを計算する。
これも全探索する。
 
あとは、w2-w1が答えなのだが、コーナーケースがある。
それはG2-G1回しか勝負がないのでそれを上回る回数を答えることは出来ないというものである。
そのため、答えはmin(w2-w1, G2-G1)

int G1, P1, G2, P2;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> G1 >> P1 >> G2 >> P2;

    int w1 = 0;
    rep(i, 0, G1 + 1) {
        if (P1 * G1 <= i * 100) {
            w1 = i;
            break;
        }
    }

    int w2 = 0;
    rep(i, 0, G2 + 1) {
        if ((P2 + 1) * G2 <= i * 100) {
            w2 = i - 1;
            break;
        }
    }

    int ans = min(w2 - w1, G2 - G1);
    cout << ans << endl;
}