AtCoder Beginner Contest 284 - zeronosu77108’s blog

AtCoder Beginner Contest 284 です。

1ペナ 5完。ペナ込み 25:14（+5:00）。 5完まではぼちぼち早かったけど、全人類 F 通してて悲しい気持ちになった。 Rolling Hash っぽいものをゴニョニョ書いてたけど、バグらせて終了。というか条件をちゃんと分離できてなかった…。

A - Sequence of Strings

問題文

逆順に出力する。

fn main() {
    input! {
        s : [String]
    }

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

提出

B - Multi Test Cases

問題文

奇数を数える。マルチテストケース。

fn main() {
    input! {
        t : usize
    }

    let mut ans = Vec::with_capacity(t);
    for _ in 0..t {
        input! { a : [usize] }
        ans.push(a.iter().filter(|&a| a % 2 == 1).count());
    }

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

提出

C - Count Connected Components

問題文

シンプルに連結成分を数える問題。 Union-Find で適当にマージして、 i == root(i) となるやつを数えると連結成分が分かる。

fn main() {
    input! {
        n : usize,
        m : usize,
        edges : [(Usize1, Usize1); m]
    }

    let mut uni = UnionFind::new(n);
    for (a ,b) in edges { uni.merge(a, b); }

    let ans = (0..n).filter(|&i| i == uni.root(i)).count();
    println!("{}", ans);
}

提出

D - Happy New Year 2023

問題文

よく分からないので、ポラード・ロー法とか使ってる早いライブラリを Library Checker から盗んでくる…（Factorize）。

よく考えると、 $ \sqrt [ 3 ] { N } $ くらいまで探索したら良いので、そんな感じで書いても良かったかも。

fn main() {
    input! {
        t : usize
    }

    let mut ans = vec![];
    for _ in 0..t {
        input! { n : i64 }
        let f = pollard_rho::factorize(n);

        let mut p = 0; let mut q = 0;
        for (k, v) in f {
            if v == 1 { q = k; }
            else { p = k; }
        }
        ans.push(format!("{} {}", p, q));
    }

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

提出

E - Count Simple Paths

問題文

答えが $ \min ( K , 10 ^ 6) $ なので、超えたら全ての探索を打ち切ったら間に合う。適当に DFS とかを書く。インクリメントする場所の関係で出力が $ 10 ^ 6 $ より大きくなることがあって 1WA。

fn main() {
    input! {
        n : usize,
        m : usize,
        edges : [(Usize1, Usize1); m]
    }

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

    let mut path = FxHashSet::default();
    dfs(0, &g, &mut path, &mut ans);

    println!("{}", 1_000_000.min(ans));
}

fn dfs(v:usize, g:&Vec<Vec<usize>>, path:&mut FxHashSet<usize>, ans:&mut usize) {
    *ans += 1;
    path.insert(v);
    if *ans >= 1_000_000 { return; }

    for &u in g[v].iter() {
        if path.contains(&u) { continue }
        dfs(u, g, path, ans);
    }

    path.remove(&v);
}

提出

F - ABCBAC

問題文

バグらせ太郎。 Z algorithm とかでうまくできそうだな～と思いながら、良い方法が思い浮かばなかったので Rolling Hash もどきで力業実装しようとするも、うまくできず…。

結局後から AC。もうちょっと落ち着いて考えれば解けたなぁという感想。 Rolling Hash 、 LeetCode の Weekly Contest で Rolling Hash もどきを書いて通したことがあるくらいでその方針に走ったのが良くないかもなぁ…。 Z algorithm とか Suffix Array とかなんとなくは知ってるんだけど意味が分からなくなりがちなので結局通せないがち何だよなぁ…。その辺の問題たくさん解くか～。

後から通したACコード

Rolling Hash もバグらせないようにライブラリ化したんだけど、逆を勝手に持っておくようにしたんだけどよく考えたら、 $B ^ {-i}$ みたいなので逆を計算した方が良くないか？まぁ、また今度で…。

ライブラリ化したやつ
 Z algorithm版