Pro Exam Eligibility の解説

二分探索をする。

oの数をw, 区間の幅をLとした時に勝率がX以上になる時は

$$\frac{w}{L} \ge X$$

なので、

$$w - L \times X \ge 0$$

となる。

ここからは定石として覚えておきたいが、 xはL - w個あるのでこれを意識して式変形すると

$$w \times (1 - X) + (L - w) \times (-X) \ge 0$$

となる。

つまり勝率の条件は

• o -> 1 - X
• x -> -X

と置き換えたとき、累積和が0以上になる区間に言い換えることができる。

ここまでくればにぶたんは簡単で、K以上存在する必要があることに注意をしながら実装すればよい。 (といいつつseg木使ったらTLEしたので注意)

fn main() {
    input! {
        n: usize,
        k: usize,
        s: Chars
    }
    let counter = {
        let c = s
            .iter()
            .map(|&e| if e == 'o' { 1usize } else { 0 })
            .collect_vec();
        PrefixSum1D::new(&c)
    };

    let mut left = 0.;
    let mut right = 1.;

    while right - left > 10f64.powf(-6.1) {
        let mid = (left + right) / 2.;
        let s = s
            .iter()
            .map(|&e| if e == 'o' { 1. - mid } else { -mid })
            .collect_vec();
        let acc = PrefixSum1D::new(&s);
        let mut flg = false;
        let mut l2 = 0;

        let mut low = f64::MAX / 2.;
        for right in 1..=n {
            while l2 < right && counter.range_sum(l2..right) >= k {
                low = low.min(acc.prefix_sum(l2));
                l2 += 1;
            }
            if acc.prefix_sum(right) - low >= 0. {
                flg = true;
            }
        }
        if flg {
            left = mid;
        } else {
            right = mid;
        }
    }
    println!("{}", left);
}