bouzuya.hatenablog.com

ぼうずやのにっき

体調が悪い / ABC321 A, B, C, D, E

体調が悪い。子どもが熱を出しているので家庭保育のために休んでいたのだけどむしろぼくの体調が悪い。昼間子どもは家でぴょんぴょんしているし、それをとめているぼくの側が疲れていた。

サントリープログラミングコンテスト2023（AtCoder Beginner Contest 321）

use proconio::input;

/// x から k 下がった深さの個数を求める
fn g(n: usize, x: usize, k: usize) -> usize {
    if x > n {
        return 0;
    }

    let (mut l, mut r) = (x, x);
    for _ in 0..k {
        l *= 2;
        r = r * 2 + 1;
        if l > n {
            return 0;
        }
    }
    r = r.min(n);

    r + 1 - l
}

fn f(n: usize, mut x: usize, mut k: usize) -> usize {
    // 下がるだけ
    let mut sum = g(n, x, k);
    // 1つ上がってから下がる
    while x > 1 && k >= 2 {
        sum += g(n, x ^ 1, k - 2);
        k -= 1;
        x /= 2;
    }
    // 1つ上がるだけ
    if x != 1 && k == 1 {
        sum += 1;
    }
    sum
}

fn main() {
    input! {
        t: usize,
        nxk: [(usize, usize, usize); t],
    }
    for (n, x, k) in nxk {
        let ans = f(n, x, k);
        println!("{}", ans);
    }
}

今日のコミット。