はじめに

AtCoder Beginner Contest 287 の C問題までを Rust で解きました！
詳しめに解説をしていこうと思います。
役にたちましたらいいねいただけると嬉しいです。
AC 確認はしてますが、もっとスマートな書き方がありましたら教えてください。

なぜやるのか

ABC287 は弊社ユニークビジョンがスポンサーの会でした！記念に記事にします。

プログラミングは知っているけれどアルゴリズムは知らない、という方に向けて書いています。半分は社内向けです。
また、私は Rust に慣れておらず、その練習のためにやっています。
(コンテスト本番には C++ を使って参加している水色コーダーです。)

問題

A - Majority (Difficulty 11)
B - Postal Card (Difficulty 45)
C - Path Graph? (Difficulty 466)
D - Match or Not (Difficulty 796)
E - Karuta (Difficulty 1093)
F - Components (Difficulty 2034)
G - Balance Update Query (Difficulty 2180)
Ex - Directed Graph and Query (Difficulty 2639)

前提

この記事にあるコードはこちらを import しています。

#[allow(unused_imports)]
use proconio::{input, fastout, marker::Chars, marker::Usize1};
#[allow(unused_imports)]
use std::collections::{HashSet, HashMap, BTreeSet, VecDeque};
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use itertools::Itertools;

A - Majority

For か Against が入力で与えられるので、For が全体の過半数かどうかを判定する問題ですね。
問題文をそのまま処理すれば答えがわかるかと思います。

実装はこのようになりました。

#[fastout]
fn main() {
  input! {
    n: usize,
    s: [String; n]
  }
  let mut for_count = 0;
  for s_i in s {
    if s_i == "For" {
      for_count += 1;
    }
  }

  // 過半数かどうかを判定
  if for_count * 2 >= n {
    println!("Yes");
  } else {
    println!("No");
  }
}

B - Postal Card

文字列が2グループ与えられてマッチングをする問題ですね。
問題文に末尾 3文字とありますが、Rust にはスライスがあるので簡単に取得できます。

グループのサイズはそれぞれ $N$ と $M$ です。まず全探索を考えると、 $O(NM)$ になります。制約を見ると $1 \le N, M \le 1000$ なので、全探索が実行制限時間内に間に合いそうです。

全探索をするときに注意なのが、問題文にある「$T_1, T_2, ..., T_M$ のいずれか」の部分です。
愚直に判定をしていると $T_i$ が重複したときに複数回カウントしてしまいます。そうすると答えが合わなくなるので注意です。

実装はこのようになりました。

#[fastout]
fn main() {
  input! {
    n: isize,
    m: isize,
    s: [Chars; n],
    t: [Chars; m],
  }

  let mut ans = 0;
  for s_i in s {
    for t_i in &t {
      // s の末尾 3文字をスライスで取得する
      // 型を合わせるために t もスライスにする
      if s_i[3..6] == t_i[0..] {
        ans += 1;
        // t が重複しているときに答えが合わなくなるので break する
        break;
      }
    }
  }
  println!("{}", ans);
}

C - Path Graph?

グラフ¹を与えられるので、パスグラフかどうかを判定する問題ですね。
わたしはパスグラフというものをこの問題で初めて知ったので、軽く例を挙げてみます。
これらの例より、パスグラフとそうでないものがわかれば嬉しいです。

パスグラフの例

順番が変わっても形が変わらなければパスグラフです

パスグラフでないものの例

分岐があるもの

ループがあるもの

連結していないもの

連結していなくてループがあるもの

続いて、パスグラフの判定をします。
ここではパスグラフかどうかを判定するよりも、パスグラフでないことを判定します。そのほうが書きやすいためです。

パスグラフでない条件を挙げます。

分岐があるもの
ループがあるもの
連結していないもの
連結していなくてループがあるもの

(4. が不要に見えるかもしれませんが、あったほうがわかりやすいと思って用意しました。)

まず、1. を判定します。これは各ノードの次数²を見ればわかります。パスグラフのノードは次数が1 か 2 になるので、 1 か 2 でないときはパスグラフではありません。

つぎに 2. を判定します。ループの判定には UnionFind木をつかいます。³

続いて 3. について、グラフの連結判定をするのですが、連結していないものはエッジの個数が少なくなります。そのため、エッジの個数を比較すれば判定できます。今回はノードの個数が $N$ なのでエッジの個数が $N-1$ なら連結です。
※ループがあるときはこの判定ができないのですが、4. で判定します。
※UnionFind木の親ノードの個数を数えてもいいのですが、私が使っている petgraph::unionfind::UnionFind だと親ノードの個数を取得できないようでした。

最後に 4. は 2. のループ判定で弾けます。

以上より、1. 2. 3. 4. のどれにも該当しないものがパスグラフだとわかります。

実装は以下のようになりました。

use petgraph::unionfind::UnionFind;

#[fastout]
fn main() {
  input! {
    n: usize,
    m: usize,
    uv: [(Usize1, Usize1); m] // ノードのインデックスを受け取るときは Usize1 がオススメ
  }

  // 各ノードの次数
  let mut deg = vec![0; n];
  let mut ans = "Yes";

  // 連結でない、またはループがあるものを除く
  if n != m + 1 {
    ans = "No";
  }
  let mut uf = UnionFind::<usize>::new(n);
  for (u, v) in uv {
    // ループがあるものを除く
    if !uf.union(u, v) {
      ans = "No";
    }
    deg[u] += 1;
    deg[v] += 1;
    // 分岐があるものを除く
    if deg[u] > 2 || deg[v] > 2 {
      ans = "No";
    }
  }
  println!("{}", ans);
}

最後まで読んでいただきありがとうございます！

グラフはここの冒頭で説明してみたので、良ければ見てください： DAG（有向非巡回グラフ）の紹介とトポロジカルソート ↩
ノードから出ているエッジの個数を次数といいます ↩
全探索をしても連結判定をできるのですが、競プロでは UnionFind木がよく出てきて、全探索に比べてよりシンプルに書けます。そのため、 UnionFind木を使うのをオススメします。 ↩

ABC287 を Rust で解く (C問題まで)

はじめに

なぜやるのか

問題

前提

A - Majority

B - Postal Card

C - Path Graph?