Published on

[Rust] ABC292 A~E 振り返り

Authors

ABC292 A~E の振り返り。

AtCoder Beginner Contest 292 - AtCoderAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jpAtCoder Beginner Contest 292 - AtCoder

公式解説はこちら。この記事とは内容が異なる可能性があるので、公式解説も合わせて読むことをおすすめします。

https://atcoder.jp/contests/abc292/editorial

Overview

感想

久々の5完でレート +33（1032）。
C問題に時間がかかったり、Fの手がかりが掴めなかったりと数学の弱さを改めて感じるコンテストでした。

A

A - CAPS LOCKAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jpA - CAPS LOCK

to_uppercase() を呼び出すだけ。

use proconio::input;

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

    println!("{}", s.to_uppercase());
}

B

B - Yellow and Red CardAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jpB - Yellow and Red Card

選手xが「イエローカード2枚貰った」もしくは「レッドカードを貰った選手」なら 'Yes' そうでなければ 'No' を出力する問題。
やり方は色々あると思うがイエローカードなら +1、レッドカードなら +2 して、2以上なら 'Yes' を出力するという方法で通した。

use proconio::input;
use std::collections::HashMap;

fn main() {
    input! {
        _: usize,
        q: usize,
    };

    let mut count = HashMap::new();

    for _ in 0..q {
        input! {
            t: usize,
            x: usize,
        };

        match t {
            1 => {
                let c = count.entry(x).or_insert(0);
                *c += 1;
            }
            2 => {
                let c = count.entry(x).or_insert(0);
                *c += 2;
            }
            3 => {
                if let Some(c) = count.get(&x) {
                    if *c >= 2 {
                        println!("Yes");
                        continue;
                    }
                }

                println!("No");
            }
            _ => unreachable!(),
        }
    }
}

C

C - Four VariablesAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jpC - Four Variables

整数Nに対して、AB+CD=N となるような整数A,B,C,Dの組み合わせの個数を求める問題。
N が 10^5 なので、O(N^2) で解くと TLE する。
愚直に全探索すると O(N^4) になるので、愚直全探索はできない。

回答は AB の組み合わせの個数と CD の組み合わせの個数の積になるので、別々に考えることができる。
Aに関しては 1..n まであり得るとき、B は 1..=n / a までありうる。
この時点での計算量は O(N log N) となる...はず。（あんまり自信がないが）

ABが求めれられれば、CD は N - AB で求められる。
CDの組み合わせはCDの約数の数となるので、事前にNまでの約数の個数を求めておく。
約数の列挙は √N で求められるため、CDを求めるのに O(N √N) になる。

そのためAとBの組み合わせを全探索して、CDの組み合わせを事前に求めておくと、O(N √N) で解ける。

use proconio::input;

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

    let mut ans = 0;
    let mut counts = vec![0; n + 1];

    for i in 1..=n {
        // 事前に約数の個数を求めておく
        counts[i] = divisors(i).len();
    }

    for a in 1..n {
        for b in 1..=n / a {
            let cd = n - a * b;

            ans += counts[cd];
        }
    }

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

// 約数の列挙
fn divisors(n: usize) -> Vec<usize> {
    let mut lst: Vec<usize> = vec![];

    let mut i = 1;

    while i * i <= n {
        if n % i == 0 {
            lst.push(i);
            if i != n / i {
                lst.push(n / i);
            }
        }

        i += 1;
    }

    lst
}

D

D - Unicyclic ComponentsAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jpD - Unicyclic Components

無向グラフが与えられるので、全ての連結成分に対して頂点と辺の個数が等しいか判定する問題。
この問題は2つの小問題に分けて考えられる。

  1. 連結成分を列挙する
  2. 各連結成分に対して頂点と辺の個数が等しいか判定する

1に関しては UnionFind を使えば便利。
各辺で unite していくと、最終的には連結成分の根が同じになる。
これを利用して、連結成分の根を Set に入れておくと全ての連結成分の根が列挙できる。

2に関しては色々解法がありそうだが、今回はBFSで解いた。
1で全ての連結成分の根を列挙したので、それぞれに対してBFSを行う。

頂点に到達するたびに頂点のカウントを +1, 辺の数だけ辺のカウントを +1 していく。
重複している辺をカウントしているので、辺の数は / 2 しておく。
頂点と辺の数が一致していない連結成分がある場合は No を出力して終了する。

use proconio::{input, marker::Usize1};
use std::collections::HashSet;

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

    let mut graph = vec![vec![]; n];
    let mut uf = UnionFind::new(n);

    for (u, v) in uv {
        graph[u].push(v);
        graph[v].push(u);
        uf.unite(u, v);
    }

    let mut set = HashSet::new();

    for i in 0..n {
        set.insert(uf.root(i));
    }

    for v in set {
        let (vertices, edges) = bfs(v, &graph);

        if vertices != edges {
            println!("No");
            return;
        }
    }

    println!("Yes");
}

fn bfs(v: usize, graph: &Vec<Vec<usize>>) -> (usize, usize) {
    let mut dist = vec![-1; graph.len()];
    let mut vertices = 0;
    let mut edges = 0;
    let mut queue = std::collections::VecDeque::<usize>::new();
    queue.push_front(v);
    dist[v] = 0;

    while !queue.is_empty() {
        let pos = *queue.front().unwrap();
        queue.pop_front().unwrap();
        vertices += 1;

        for i in 0..graph[pos].len() {
            let nex = graph[pos][i];
            edges += 1;
            if dist[nex] == -1 {
                dist[nex] = dist[pos] + 1;
                queue.push_back(nex);
            }
        }
    }

    (vertices, edges / 2)
}

struct UnionFind {
    par: Vec<usize>,
    siz: Vec<usize>,
}

#[allow(dead_code)]
impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind {
            par: (0..n).collect(),
            siz: vec![1; n],
        }
    }

    fn root(&mut self, x: usize) -> usize {
        if self.par[x] == x {
            return x;
        }

        self.par[x] = self.root(self.par[x]);
        self.par[x]
    }

    fn is_same(&mut self, x: usize, y: usize) -> bool {
        self.root(x) == self.root(y)
    }

    fn unite(&mut self, x: usize, y: usize) {
        let x = self.root(x);
        let y = self.root(y);

        if x == y {
            return;
        }

        if self.siz[x] < self.siz[y] {
            self.par[x] = y;
            self.siz[y] += self.siz[x];
        } else {
            self.par[y] = x;
            self.siz[x] += self.siz[y];
        }
    }

    fn size(&mut self, x: usize) -> usize {
        let x = self.root(x);
        self.siz[x]
    }
}

E

E - TransitivityAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jpE - Transitivity

単純有向グラフが与えられるので、AからBまでの有向辺とBからCまでの有向辺があれば、AからCまでの有向辺を追加していく。
最終的に追加する辺の最小数を出力する問題。

本番はBFSによるシミュレーションで解いた。
0..n までの頂点Xに対してBFSを行う。
Xから現在探索中の頂点の距離が1であるとき、次の頂点はXからの距離が2になるためXから次の頂点へ有向辺を追加したものとして考える。
BFSは幅優先で探索されるため、Xからの距離が2の頂点はXからの距離が1の頂点よりも後に探索される。

use proconio::{input, marker::Usize1};

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

    let mut graph = vec![vec![]; n];
    for (u, v) in uv {
        graph[u].push(v);
    }

    let mut ans = 0;

    for i in 0..n {
        let mut count = 0;
        bfs(i, &graph, &mut count);

        ans += count;
    }

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

fn bfs(v: usize, graph: &Vec<Vec<usize>>, count: &mut usize) -> Vec<isize> {
    let mut dist = vec![-1; graph.len()];
    let mut queue = std::collections::VecDeque::<usize>::new();
    queue.push_front(v);
    dist[v] = 0;

    while !queue.is_empty() {
        let pos = *queue.front().unwrap();
        queue.pop_front().unwrap();

        for i in 0..graph[pos].len() {
            let nex = graph[pos][i];
            if dist[nex] == -1 {
                if dist[pos] == 1 {
                    *count += 1;
                    dist[nex] = 1;
                } else {
                    dist[nex] = dist[pos] + 1;
                }

                queue.push_back(nex);
            }
        }
    }

    dist
}