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

# はじめに

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


# なぜやるのか

[ABC287](https://atcoder.jp/contests/abc287) は弊社ユニークビジョンがスポンサーの会でした！記念に記事にします。

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

# 問題

[A - Majority](https://atcoder.jp/contests/abc287/tasks/abc287_a) (<font color="#808080">Difficulty 11</font>)
[B - Postal Card](https://atcoder.jp/contests/abc287/tasks/abc287_b) (<font color="#808080">Difficulty 45</font>)
[C - Path Graph?](https://atcoder.jp/contests/abc287/tasks/abc287_c) (<font color="#804000">Difficulty 466</font>)
[D - Match or Not](https://atcoder.jp/contests/abc287/tasks/abc287_d) (<font color="#804000">Difficulty 796</font>)
[E - Karuta](https://atcoder.jp/contests/abc287/tasks/abc287_e) (<font color="#008000">Difficulty 1093</font>)
[F - Components](https://atcoder.jp/contests/abc287/tasks/abc287_f) (<font color="#C0C000">Difficulty 2034</font>)
[G - Balance Update Query](https://atcoder.jp/contests/abc287/tasks/abc287_g) (<font color="#C0C000">Difficulty 2180</font>)
[Ex -  Directed Graph and Query](https://atcoder.jp/contests/abc287/tasks/abc287_h) (<font color="#FF8000">Difficulty 2639</font>)


# 前提

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

```rust
#[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` が全体の過半数かどうかを判定する問題ですね。
問題文をそのまま処理すれば答えがわかるかと思います。

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

```rust
#[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$ が重複したときに複数回カウントしてしまいます。そうすると答えが合わなくなるので注意です。

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

```rust
#[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? 

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

<details>

<summary>
パスグラフの例
</summary>

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748702/4351fc8e-503f-fd21-62fc-210e9f99da6d.png)

順番が変わっても形が変わらなければパスグラフです
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748702/0bd5bb9f-6ac0-6a1b-a7f3-223e46fdd631.png)

</details>

<details>

<summary>
パスグラフでないものの例
</summary>

<br>

分岐があるもの
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748702/67143a21-10dc-73b7-8e48-a6e00363eaa1.png)

ループがあるもの
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748702/c10a6f2d-ea70-69c0-94f2-0821c493f46c.png)

連結していないもの
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748702/c747cf12-41f3-75b3-a8a4-8d249dca4a13.png)

連結していなくてループがあるもの
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748702/5ec8e74e-0185-8d16-830c-052b23f37598.png)

</details>

----

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

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

1. 分岐があるもの
2. ループがあるもの
3. 連結していないもの
4. 連結していなくてループがあるもの

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

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

つぎに **2.** を判定します。ループの判定には UnionFind木をつかいます。[^3]

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

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

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

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

```rust
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);
}

```



----

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


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