← ブログ一覧に戻る

Codeforces Round 867 (Div. 3)

#Codeforces

Codeforces Round 867 (Div. 3) バーチャル参加したのでまとめ。 A, B, C, D, E 5完。 F は実装下手くそで時間内に解けなかった。 ChatGPT に課金したので、問題文貼り付けて「要約して下さい」って言い続けたけた。よく考えたら翻訳では…？まぁ日本語でまとめてくれたから何でもいいや。

image.png (3.5 kB)

A. TubeTube Feed

問題文

$A_i \leq t$ で $B_i$ が最大となるような $i$ を選ぶ。

fn solve(sc:&mut Scanner) {
    let n = sc.usize();
    let t = sc.usize();
    let a = sc.vec::<usize>(n);
    let b = sc.vec::<usize>(n);

    let mut ans = None;
    let mut max = 0;
    for i in 0..n {
        if a[i] + i <= t && chmax(&mut max, b[i]) {
            ans = Some(i);
        }
    }

    if let Some(ans) = ans { println!("{}", ans + 1); }
    else { println!("-1"); }
}

提出



B. Karina and Array

問題文

数列の要素を好きに削除して良いので、隣り合う値の積の最大値を最大化して下さいという問題。 正の絶対値が大きいやつ2つか、負の絶対値が大きい奴2つをかけるのが良いのソートして雑にやる。 要らないとは思ったけど $0$ が含まれていたら $0$ とも MAX を取っておいた。

fn solve(sc:&mut Scanner) {
    let n = sc.usize();
    let mut a = sc.vec::<i64>(n);
    a.sort();

    let mut ans = a[0] * a[1];
    ans = ans.max(a[n-1] * a[n-2]);
    if a.iter().any(|&a| a == 0) { ans = ans.max(0); }
    println!("{}", ans);
}

提出



C. Bun Lover

問題文

うずまきパンのチョコレート部分の長さを求める問題。難しい

3箇所囲まれている場所が必ず4箇所あって、他は2箇所囲まれている。後は、共有部分を引けば良いがわからない。サンプルから $10, 17, 26$ になるので、OIESに投げてみると $ n ^ 2 + 1$ と言われるので、言われるがままに引く。

fn solve(sc:&mut Scanner) {
    let n = sc.usize();

    let mut ans = 0;
    ans += 3 * 4;
    ans += 2 * (n * n - 4);
    ans -= (n-1) * (n-1) + 1;
    println!("{}", ans);
}

提出



D. Super-Permutation

問題文

よくわからないけど、$1$ 以外の奇数はダメそう。 偶数の場合、$0, 2, 4, \cdots$ と $\cdots, 5, 3, 1$ を交互に混ぜれば良さそう（サンプル）。

fn solve(sc:&mut Scanner) {
    let n = sc.usize();

    if n == 1 {
        println!("1");
        return;
    }
    if n % 2 == 1 {
        println!("-1");
        return;
    }

    let mut ans = vec![0; n];
    let f = |x:usize| { if x == 0 {n} else {x}};

    for i in (0..n).step_by(2) { ans[i] = f(i); }
    for i in (0..n).rev().step_by(2) { ans[i] = f(n - i); }

    println!("{}",
        ans.iter().map(|&a| a.to_string()).collect::<Vec<_>>().join(" ")
    )
}

提出



E. Making Anti-Palindromes

問題文

文字列を折りたたんだとき（？）に同じじゃないようにしたくて、できる操作はスワップ。操作回数の最小値は？という問題。めんどくさい。

$ s _ i $ と $ s _ {n - i - 1}$ が一致しているときの、文字種を適当に求めて他の文字種と打ち消し合っていけばスワップ回数が減らせる。残った奴はもう適当にスワップするしかないので全部足す。

fn solve(sc:&mut Scanner) {
    let n = sc.usize();
    let mut t = sc.chars();

    if n % 2 == 1 {
        println!("-1");
        return;
    }

    let mut cnt = vec![0; 26];
    for &c in t.iter() {
        cnt[(c as u8 - 'a' as u8) as usize] += 1;
    }

    let max = cnt.iter().max().cloned().unwrap();
    if max > n / 2 {
        println!("-1");
        return;
    }

    let mut pair = vec![0; 26];
    for i in 0..n/2 {
        if t[i] == t[n-i-1] {
            pair[(t[i] as u8 - 'a' as u8) as usize] += 1;
        }
    }

    let mut pq : BinaryHeap<_> = pair.iter().filter(|&&x| x > 0).cloned().collect();
    let mut ans = 0;
    while pq.len() > 2 {
        let a = pq.pop().unwrap();
        let b = pq.pop().unwrap();
        if a > 1 { pq.push(a - 1); }
        if b > 1 { pq.push(b - 1); }
        ans += 1;
    }

    if !pq.is_empty() { ans += pq.pop().unwrap(); }
    println!("{}", ans);
}

提出



F. Gardening Friends

問題文

全方位木DPが下手くそで時間内に実装できなかった。

fn solve(sc:&mut Scanner) {
    let n = sc.usize();
    let k = sc.usize();
    let c = sc.usize();

    let edges = sc.edges(n-1);
    let mut g = vec![vec![]; n];
    for (a, b) in edges { g[a].push(b); g[b].push(a); }

    let dist = bfs(0, n, &g);

    let mut dp1 = vec![0; n];
    let mut visited = vec![false; n];
    dfs1(0, &g, &mut dp1, &mut visited);

    let mut dp2 = vec![0; n];
    let mut visited = vec![false; n];
    dfs2(0, None, &g, &dp1, &mut dp2, &mut visited);

    // eprintln!("{:?}", dp1);
    // eprintln!("{:?}", dp2);
    // eprintln!("{:?}", dist);

    let mut ans = 0;
    for i in 0..n {
        ans = ans.max(
            (dp1[i].max(dp2[i]) * k).saturating_sub(dist[i] * c)
        );
    }

    println!("{}", ans);
}

fn dfs1(v: usize, g: &Vec<Vec<usize>>, dp: &mut Vec<usize>, visited: &mut Vec<bool>) {
    visited[v] = true;
    for &next in &g[v] {
        if visited[next] { continue; }
        dfs1(next, g, dp, visited);
        dp[v] = dp[v].max(dp[next] + 1);
    }
}

fn dfs2(v: usize, p: Option<usize>, g: &Vec<Vec<usize>>, dp1:&Vec<usize>, dp2: &mut Vec<usize>, visited: &mut Vec<bool>) {
    visited[v] = true;

    let mut left = vec![0];
    for &u in g[v].iter().filter(|&&u| Some(u) != p) {
        left.push(left.last().cloned().unwrap().max(dp1[u] + 1));
    }
    let mut right = vec![0];
    for &u in g[v].iter().rev().filter(|&&u| Some(u) != p) {
        right.push(right.last().cloned().unwrap().max(dp1[u] + 1));
    }
    right.reverse();

    for (i, &u) in g[v].iter().filter(|&&u| Some(u) != p).enumerate() {
        let d = left[i].max(right[i+1]) + 1;
        dp2[u] = d.max(dp2[v] + 1);
        dfs2(u, Some(v), g, dp1, dp2, visited);
    }
}

fn bfs(start: usize, n: usize, g: &Vec<Vec<usize>>) -> Vec<usize> {
    let mut dist = vec![std::usize::MAX; n];
    let mut q = std::collections::VecDeque::new();
    q.push_back((start, 0));
    while let Some((v, d)) = q.pop_front() {
        if dist[v] <= d { continue; }
        dist[v] = d;
        for &next in &g[v] {
            q.push_back((next, d+1));
        }
    }
    dist
}

提出



G1. Magic Triples (Easy Version)

問題文

見てない



G2. Magic Triples (Hard Version)

問題文

見てない



まとめ

全方位木DP、ライブラリ化するか定期的に書いてすぐ実装できるようにしようね！

← ブログ一覧に戻る