AtCoder Beginner Contest 253 - zeronosu77108’s blog

A - Median?

$a,b,c$ が与えられるので $b$ が中央値か？と言う問題 a..=c の間に $b$ が含まれていると良い。

fn main() {
    input! {
        a : usize,
        b : usize,
        c : usize
    }
 
    println!("{}", if (a.min(c)..=c.max(a)).contains(&b) {"Yes"} else {"No"});
}

提出

B - Distance Between Tokens

問題文

'o' の座標を求めて、x軸方向とy軸方向別々に距離を足したら良い。同じ記号なので少しめんどくさい。

fn main() {
    input! {
        h : usize,
        w : usize,
        s : [Chars; h]
    }
 
    let mut st = (0,0);
    let mut g = (0,0);
    let mut f = false;
 
    for i in 0..h { for j in 0..w {
        if s[i][j] == '-' {continue}
        if !f { st = (i,j); f=true;}
        else { g = (i,j); }
    }}
 
    println!("{}", st.0.max(g.0) - st.0.min(g.0) + st.1.max(g.1) - st.1.min(g.1));
}

提出

C - Max - Min Query

問題文

$x$ を多重集合に入れたり、 $x$ を $c$ 個多重集合から消したりする（足りなかったら $0$ になるまで）。後、多重集合の max と min を求める。

問題はシンプルだが、データ構造がないとめんどくさい。 BTreeMultiSet を作っているので、それをはっつける。 $c$個削除は実装していなかったので、温かみのある実装をする。

流石に無いのは不便なので、コンテストあとに実装した（修正版）。

fn main() {
    input! { q : usize }
 
    let mut s = BtreeMultiSet::new();
    for _ in 0..q {
        input! { t : u8 }
        match t {
            1 => {
                input! { x : usize }
                s.add(x);
            }
            2 => {
                input! { x : usize, c : usize }
                match s.set.get_mut(&x) {
                    Some(xc) => {
                        if *xc <= c { s.set.remove(&x); }
                        else { *xc -= c; }
                    }
                    None => {},
                }
            }
            3 => {
                println!("{}", s.last().unwrap() - s.first().unwrap());
            }
            _ => unreachable!()
        }
    }
}

提出

D - FizzBuzz Sum Hard

問題文

$N$ 以下の正整数のうち $A$の倍数でも $B$ の倍数でもないものの総和を求める問題。最初総和じゃなくて個数を求めて「？？？」となっていた。

Rust を信じて (0..=n).step_by(a).sum::<usize>() などとするも TLE。 O(1) でやってくれ……！

仕方ないので、自分で式を書く。

fn main() {
    input! {
        n : usize,
        a : usize,
        b : usize
    }
 
    let mut ans = n * (n+1) / 2;
 
    ans -= (a + n/a*a) * (n/a) / 2;
    ans += (lcm(a,b) + n/lcm(a,b)*lcm(a,b)) * (n/lcm(a,b)) / 2;
    ans -= (b + n/b*b) * (n/b) / 2;
 
    println!("{}", ans);
}

提出
 ちょっと綺麗にした版

E - Distance Sequence

問題文

dp[i][j] i桁決まって、 $A _ i = j$ である場合の数とかをやれば良い。そのまま計算すると O(NMK) とかになってヤバそうなので、累積和取っておいて、総和 - 満たさない範囲とかをしたら良い。 $K = 0$ のときに注意

fn main() {
    input! {
        n : usize,
        m : usize,
        k : usize
    }

    if k == 0 {
        println!("{}", pow(m,n,MOD as usize));
        return;
    }

    const MOD : i64 = 998_244_353;

    let mut dp = vec![1; m+1];

    for _ in 1..n {
        let mut next = vec![0; m+1];
        let mut csum = vec![0; m+2];
        let mut sum = 0;
        for i in 1..=m {
            csum[i] = (csum[i-1] + dp[i]) % MOD;
            sum += dp[i]; sum %= MOD;
        }

        for i in 1..=m {
            next[i] = (sum + MOD - csum[m.min(i+k-1)] + csum[i.saturating_sub(k)]) % MOD;
            next[i] %= MOD;
        }
        dp = next.into_iter().map(|d| d % MOD).collect_vec();
    }

    let mut ans = dp[1..].iter().fold(0, |acc,&v| (acc+v) % MOD) % MOD;
    println!("{}", ans);
}

提出

F - Operations on a Matrix

問題文

本番中解けなかった。クエリ平方分割しようとして沼った。

後半に考えていた、後ろからやって $i$ 行目を $x$ にする操作のときに良い感じに計算するやつ、結局時間が足りずに詰め切れなかったんだけど、コンテスト後にちゃんと書いたら通った。

3 のクエリが流れてきたときを $0$ として、良い感じにやると良い。

fn main() {
    input! {
        n : usize,
        m : usize,
        q : usize,
    }

    let mut queries = Vec::with_capacity(q);

    let mut bit = FenwickTree::<i64>::new(m+1);

    let mut cnt = 0;
    let mut nq = vec![vec![]; n];
    for _ in 0..q {
        input! { t : u8 }
        match t {
            1 => {
                input! { l:Usize1, r:usize, x:i64 }
                queries.push((t, l, r, x));
            }
            2 => {
                input! { i:Usize1, mut x:i64 }
                queries.push((t, i, 0, x));
            }
            3 => {
                input! { i:Usize1, j:Usize1 }
                queries.push((t, i, j, cnt));
                cnt += 1;
            }
            _ => unreachable!()
        }
    }

    let mut ans = vec![0; cnt as usize];
    for (t, l, r, x) in queries.into_iter().rev() {
        match t {
            1 => { bit.add(l, x); bit.add(r, -x); }
            2 => {
                let i = l;
                for (index, j) in nq[i].drain(..) {
                    ans[index as usize] += x + bit.fold(j);
                }
            }
            3 => {
                let (i, j) = (l,r);
                let index = x as usize;
                nq[i].push((index, j));
                ans[index] -= bit.fold(j);
            }
            _ => unreachable!()
        }
    }

    for i in 0..n {
        for (index, i) in nq[i].drain(..) {
            ans[index as usize] += bit.fold(i);
        }
    }


    println!("{}", ans.iter().join("\n"));
}

提出

G - Swap Many Times

問題文

見てない。

Ex - We Love Forest

問題文

見てない

まとめ

微妙。レート 1529 → 1530(+1)