AtCoder Beginner Contest 327振り返り

A - ab

abとbaをfindすればよい。

use proconio::input;

fn main() {
    input! {
        _n: usize,
        s: String,
    }

    if s.find("ab").is_some() || s.find("ba").is_some() {
        println!("Yes");
    } else {
        println!("No");
    }
}

B - A^A

a^aをaを加算しながら計算していく。bを超えたら計算終了。

use proconio::input;

fn pow(a: usize) -> usize {
    let mut x = 1;
    for _ in 0..a {
        x *= a;
    }
    x
}

fn main() {
    input! {
        b: usize,
    }

    let mut a = 1;
    loop {
        let aa = pow(a);
        if aa == b {
            println!("{}", a);
            return;
        }

        if aa > b {
            println!("-1");
            return;
        }

        a += 1;
    }
}

C - Number Place

ここまでしか解けなかった。
計算時間は気にしなくてよいので条件を満たしているかの関数を作る。

use itertools::iproduct;
use proconio::input;
use std::collections::BTreeSet;
fn is(a: &Vec<Vec<usize>>, x0: usize, y0: usize) -> bool {
    BTreeSet::from_iter(iproduct!(0..3, 0..3).map(|(y, x)| a[y0 + y][x0 + x])).len() == 9
}
fn main() {
    input! {
        a: [[usize; 9]; 9],
    }

    if !(0..9).all(|y| BTreeSet::from_iter((0..9).map(|x| a[y][x])).len() == 9) {
        println!("No");
        return;
    }

    if !(0..9).all(|x| BTreeSet::from_iter((0..9).map(|y| a[y][x])).len() == 9) {
        println!("No");
        return;
    }

    for (x0, y0) in [
        (0, 0),
        (3, 0),
        (6, 0),
        (0, 3),
        (3, 3),
        (6, 3),
        (0, 6),
        (3, 6),
        (6, 6),
    ] {
        if !is(&a, x0, y0) {
            println!("No");
            return;
        }
    }

    println!("Yes");
}

D - Good Tuple Problem

まったく解けなかった。
二部グラフであることを判定するらしい。

use petgraph::graph::*;
use proconio::{input, marker::Usize1};

struct Ctx {
    x: Vec<Option<usize>>,
    bipartite: bool,
}

fn dfs(i: usize, a: usize, g: &Graph<usize, usize, petgraph::Undirected, usize>, ctx: &mut Ctx) {
    ctx.x[i] = Some(a);

    for j in g.neighbors(node_index(i)).map(|j| j.index()) {
        if ctx.x[j].is_none() {
            dfs(j, 1 - a, &g, ctx);
        } else if ctx.x[i] == ctx.x[j] {
            ctx.bipartite = false;
        }
    }
}

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

    let g: Graph<usize, usize, petgraph::Undirected, usize> =
        UnGraph::from_edges((0..m).map(|i| (a[i], b[i])));

    let mut ctx = Ctx {
        x: vec![None; n],
        bipartite: true,
    };

    for i in 0..n {
        if ctx.x[i].is_none() {
            dfs(i, 0, &g, &mut ctx);
        }
    }

    if ctx.bipartite {
        println!("Yes");
    } else {
        println!("No");
    }
}

UnionFindを使用して判定するとシンプルに書けるようだった。

use petgraph::unionfind::UnionFind;
use proconio::{input, marker::Usize1};

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

    let mut uf = UnionFind::new(n * 2);
    for i in 0..m {
        uf.union(a[i], b[i] + n);
        uf.union(a[i] + n, b[i]);
    }

    let yes = (0..n).all(|i| !uf.equiv(i, i + n));
    println!("{}", if yes { "Yes" } else { "No" });
}

総括

Cまでは順調に解けたがDは二部グラフというのが思いつかなかった。
DFSで解こうとしたがTLEしてしまう。

参考

• 二部グラフ判定をUnionFindTreeで行う