[Rust] ABC287 A~E 振り返り

ABC287 A~E の振り返り。

UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287) - AtCoderAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp

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

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

Overview

A

A - MajorityAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp

過半数が賛成しているかどうかを判定する問題。
if n / 2 < "For" count なら Yes と出力する。

use proconio::input;

fn main() {
    input! {
        n: usize,
        s: [String; n],
    };

    let count = s.iter().filter(|&s| s == "For").count();

    if n / 2 < count {
        println!("Yes");
    } else {
        println!("No");
    }
}

B

B - Postal CardAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp

S の末尾 3 文字に一致する T の文字列が存在するかどうかを判定する問題。
S,T はそれぞれの文字の長さが 6,3 で、共に個数が 1000 以下なので O(N^2) の全探索が可能。

S の長さは 6 文字と決まっているので、3 文字目以降を取得して T と比較すれば良い。
文字列の 3 文字目以降を取得するには &v[3..] とすると文字列スライスで取得できて便利。
そのまま &String と比較できる。

use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
        s: [String; n],
        t: [String; m],
    };

    let mut matches = vec![false; n];

    for i in 0..n {
        let v = &s[i];
        let pref = &v[3..];

        // Tに一致する文字列があるかどうか
        let is_match = t.iter().any(|t| t == pref);

        if is_match {
            matches[i] = true;
        }
    }

    println!("{}", matches.iter().filter(|&s| *s).count());
}

C

C - Path Graph?AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp

単純無向グラフが与えられるので、パスグラフかどうかを判定する問題。
そもそもパスグラフという用語を知らず公式の条件を見てもピンと来なかったので、パスグラフをググることから始めた。

パスグラフは、2 頂点を除き全ての頂点の次数が 2、残る 2 頂点の次数が 1 という特徴を持つ連結グラフとも言える。他のグラフの部分グラフとしてパスグラフを作った場合、それは元のグラフにおける道（パス）にあたる。パスグラフとは？わかりやすく解説 - Weblio 辞書

ということで、以下の条件を満たすことを判定することを考えた。

全ての頂点が連結している
スタートとゴールの頂点の次数が 1, それ以外の頂点の次数が 2

あとは自分のライブラリから DFS をコピペしてきて、次数 1 の頂点をスタートとして探索開始。
スタートとゴールが次数 1 以外、またはそれ以外の次数が 2 以外であれば、 No を出力して exit する。
最後に DFS で辿ったパスの長さが頂点数と一致すれば Yes を出力する。
（他にも BFS, UnionFind 等色々な解法はありそう）

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

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

    let mut graph = vec![vec![]; n];
    let mut count = vec![0; n];

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

        count[u] += 1;
        count[v] += 1;
    }

    if let Some(start) = count.iter().position(|&c| c == 1) {
        let paths = dfs(start, &graph);

        if paths.len() == n {
            println!("Yes");
        } else {
            println!("No");
        }
    } else {
        println!("No");
        return;
    }
}

fn dfs(v: usize, graph: &Vec<Vec<usize>>) -> Vec<usize> {
    let mut visited: Vec<bool> = vec![false; graph.len()];
    let mut ans: Vec<usize> = vec![];
    dfs_inner(v, graph, &mut visited, &mut ans, 1);
    ans
}

fn dfs_inner(
    v: usize,
    graph: &Vec<Vec<usize>>,
    visited: &mut Vec<bool>,
    ans: &mut Vec<usize>,
    count: usize,
) {
    visited[v] = true;
    ans.push(v);

    let nexts = &graph[v];

    if count == 1 || count == graph.len() {
        if nexts.len() != 1 {
            println!("No");
            std::process::exit(0);
        }
    } else {
        if nexts.len() != 2 {
            println!("No");
            std::process::exit(0);
        }
    }

    for &w in nexts.iter() {
        if !visited[w] {
            dfs_inner(w, graph, visited, ans, count + 1);
        }
    }
}

D

D - Match or NotAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp

判定する文字をキャタピラのように動かしていき、T とマッチするかどうかを判定する問題。
S,T が 3 * 10^5 なので、O(N^2) で解くと TLE する。つまり 2 重ループはできない。
実際に書いて考えると遷移がわかりやすい。

T と対象の文字が一致するかどうかは、現在何文字一致しているかの count を保持しておく。
ループごとに新しい文字が一致していれば count を増やし、無くなった文字が一致していれば count を減らす。
コンテスト中は無くなった文字が一致しているかどうかの判定を忘れており 1WA してしまった。

文字は Chars で受け取ると Vec<char> 型になるので文字判定に便利。

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

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

    let mut count = 0;

    let is_collect = |sc: char, tc: char| return sc == '?' || tc == '?' || sc == tc;

    for i in 0..t.len() {
        let sc = s[i + s.len() - t.len()];
        let tc = t[i];

        if is_collect(sc, tc) {
            count += 1;
        }
    }

    if count == t.len() {
        println!("Yes");
    } else {
        println!("No");
    }

    for i in 0..t.len() {
        let sc = s[i];
        let tc = t[i];
        let sc_back = s[i + s.len() - t.len()];

        if is_collect(sc, tc) {
            count += 1;
        }

        if is_collect(sc_back, tc) {
            count -= 1;
        }

        if count == t.len() {
            println!("Yes");
        } else {
            println!("No");
        }
    }
}

E

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

文字列が N 個与えられるため、そのうちの各文字列に対して、他の文字列との先頭から一致する最大文字数を求める問題。
N が 5 * 10^5 なので、O(N^2) で解くと TLE する。
こういった 他の値と比べる といった問題は基本的にソートしても問題ないので、ソートしてから考えることにしている。（ただし、今回は回答順が決まっているので元の順番は壊さないように）
辞書順にソートすると、文字列の先頭から一致する最大文字数が自分の前か後ろの文字になるため、前と後ろの一致文字数を求めて最大値を出力すれば良い。
計算量が心配になるが、S の長さの総和が 5 * 10^5 なので、十分間に合う。

個人的にはこの解法しか思いつかなかったのだが、Twitter をみると Trie 木とかローリングハッシュとか人によって大分解法が違ったよう。

以下のコンテスト中に提出したコードはリファクタする気にもならないぐらい、汚いので注意...

個人的にはこの方の提出が程よくまとまっており、わかりやすくて参考になった。

Submission #38440096 - UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287)AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp

use proconio::input;

fn main() {
    input! {
        n: usize,
        s: [String; n],
    };

    let mut c = s.clone();
    c.sort();

    for v in s {
        let current_i = c.binary_search(&v).unwrap();
        let prev_i = (current_i as isize - 1).max(0) as usize;
        let next_i = (current_i + 1).min(n - 1);

        let mut prev_count = 0;
        let mut next_count = 0;
        let current = &c[current_i];
        let prev = &c[prev_i];
        let next = &c[next_i];

        if current_i != prev_i {
            for i in 0..current.len() {
                if i >= prev.len() {
                    break;
                }

                if current[i..i + 1] == prev[i..i + 1] {
                    prev_count += 1;
                } else {
                    break;
                }
            }
        }

        if current_i != next_i {
            for i in 0..current.len() {
                if i >= next.len() {
                    break;
                }

                if current[i..i + 1] == next[i..i + 1] {
                    next_count += 1;
                } else {
                    break;
                }
            }
        }

        let ans = prev_count.max(next_count);

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