Count Close Pairs の解説

尺取法を正しくかけるかという問題です。 2 * Nなので二分探索は使えません。 いつも甘えてにぶたんしてるので地味に時間を使ってしまいました。

fn main() {
    input_interactive! {
        n: usize
    }
    let mut ans = 0;
    let mut right = 1;
    for i in 0..n {
        while right < n {
            println!("? {} {}", i + 1, right + 1);
            input_interactive! {
                s: String
            }
            if s == "Yes" {
                right += 1usize;
            } else {
                break;
            }
        }
        ans += right - i - 1;
        right = max(right, i + 2);
    }
    println!("! {}", ans);
}