ABC226 を Rust で解く (E問題まで)

# はじめに

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


# なぜやるのか

コンテストから時間をあけて解きなおすことで、記憶へ定着すればいいなと思っています。
また、会社で Rust を使うのですが私はまだ慣れておらず、その練習のためにやっています。
(コンテスト本番には C++ を使って参加している水色コーダーです。)


# 目次

[A - Round decimals](#a---round-decimals) (<font color="#808080">Difficulty 14</font>)
[B - Counting Arrays](#b---counting-arrays) (<font color="#808080">Difficulty 192</font>)
[C - Martial artist](#c---martial-artist) (<font color="#804000">Difficulty 539</font>)
[D - Teleportation](#d---teleportation) (<font color="#804000">Difficulty 706</font>)
[E - Just one](#e---just-one) (<font color="#00C0C0">Difficulty 1327</font>)


# 前提

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

```rust
#[allow(unused_imports)]
use proconio::{input, fastout, marker::Chars};
#[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 - Round decimals

四捨五入をする問題ですね。

`f64` で受け取って、 `round()` を使えば答えがわかります。

競プロで浮動小数点数を使うのは誤差が怖いですが、今回は入力で小数第三位までもらえますね。
これは小数第一位で四捨五入をする問題なので、誤差を気にしなくても大丈夫です。

```rust
fn main() {
  input! {
    x: f64
  }
  println!("{}", x.round());
}
```


# B - Counting Arrays 

問題文が少し複雑ですが、与えられた数列の種類を答える問題です。

全通り試すと $O(N^2)$ かかってしまい、時間内に解けません。
重複する数列を取り除いたときに残っている数列の個数を数えれば答えになります。

これは `HashSet` を使います。`HashSet` は集合を扱うデータ構造で、要素の重複を許しません。また、`Vec` をそのまま扱うことができるので、入力をそのまま `Vec` にすることができます。つまり、今回の問題にぴったりですね。

追加する操作 `insert()` が $O(log N)$ で $N$ 回あるので、全体では $O(N log N)$ で解くことができました。

```rust
fn main() {
  input! {
    n: usize
  }
  let mut st = HashSet::<Vec<usize>>::new();
  for _ in 0..n {
    input! {
      l: usize,
      a: [usize; l]
    }
    st.insert(a); // 追加する
  }
  println!("{}", st.len()); // サイズが答えになる
}
```


# C - Martial artist 

技を習得するコストを求める問題ですね。

ある技を習得するには別の技が必要です。まずはこの関係を図に描いてみましょう。矢印を交えて描いてみると、名前のある図になります。いわゆる有向グラフですね。(ちなみに、矢印の向きは [技] -> [習得に必要な技] だとあとで楽です。) 習得にかかる時間もグラフに描くことで、ノードに重みがあるタイプの重み付き有向グラフになります。

有向グラフが描けたら、この問題の挙動を見てみましょう。技 $N$ からこのグラフをたどります。この時に訪れたノードにある時間の合計が、今回求める値になります。

ここまでわかれば実装です。実装では、グラフを構築した後にBFSをしています。

```rust
fn main() {
  input! {
    n: usize
  }
  let mut t = Vec::<usize>::new();
  let mut graph = vec![vec![]; n];
  for i in 0..n {
    input! {
      _t: usize,
      k: usize,
      a: [usize; k]
    }
    t.push(_t);
    for to in a.into_iter() {
      graph[i].push(to - 1);
    }
  }

  let mut ans = 0;

  // 頂点N から BFS をする
  let mut come = vec![false; n];
  let mut que = VecDeque::new();
  que.push_back(n - 1);

  while let Some(now) = que.pop_front() {
    if come[now] { continue }
    ans += t[now]; // 訪れたノードの時間を足す
    come[now] = true;
    for to in graph[now].iter() {
      que.push_back(*to);
    }
  }
  println!("{}", ans);
}

```


# D - Teleportation 

街から街へ移動する問題ですね。

まず制約が小さいので、すべての街の組み合わせを試せます。すべての街の組み合わせは `N * (N - 1)` 通りで、ここから減らせるだけ減らします。

まず、同じ魔法はなくせます。重複除去というやつですね。ここはB問題と同じ考えで `HashSet` が使えます。

続いて、任意に選んだ 2つの街を `i1` と `i2` とします。この時、`i1` と `i2` を結ぶ直線状に他の街がある場合は同じ魔法を使って移動できますね。つまり使う魔法を減らせます。この減らし方が特殊なのですが、最大公約数を使います。
例えば `i1` と `i2` のちょうど真ん中に他の街がある場合は、 `i1` から `i2` へ移動する魔法の移動量を `x, y`  ともに半分にすれば3つの街に訪れることができますよね。`i1` と `i2` の 1:2 の位置にあれば、魔法の移動量を 1/3 にすることで3つの街に訪れることができます。ちなみに町の位置は格子点なので、そこに街があれば魔法の移動量も割り切ることができます。
これを一般化すると、魔法の移動量の `x` と `y` を `x, y` の最大公約数で割ることになります。

あとは、`x,y` を最大公約数で割った数を `(x, y)` のタプルにして `HashSet` にいれれば大丈夫です。
魔法は 「`i1` から `i2` に向かうもの」と「`i2` から `i1` に向かうもの」の2種類が必要なので注意です。これは `(x, y)` を `(-x, -y)` とすれば実現できます。

以下、実装です。

```rust
fn gcd(a: i64, b: i64) -> i64 {
  if b == 0 { a }
  else { gcd(b, a % b) }
}

fn main() {
  input! {
    n: usize,
    xy: [(i64, i64); n]
  }

  let mut set = HashSet::<(i64, i64)>::new();
  for i1 in 0..n {
    for i2 in i1 + 1..n {
      let dx = xy[i1].0 - xy[i2].0;
      let dy = xy[i1].1 - xy[i2].1;

      let gd = gcd(dx, dy);

      let x = dx / gd;
      let y = dy / gd;

      set.insert(( x,  y)); // i1 から i2 に向かう
      set.insert((-x, -y)); // i2 から i1 に向かう
    }
  }
  println!("{}", set.len());
}
```


# E - Just one 

グラフの問題ですね。

まず、グラフは「木」でもなければ「連結」ではありません。つまり、連結成分ごとに分かれていることがあります。連結成分ごとの組み合わせを求めれば、その積が答えになりそうです。

連結成分ごとの組み合わせを考えます。
答えを書きますが、以下の条件を満たすときに2通り、満たさなければ 0通りになります。
・頂点の数と枝の数が一致する。
私は紙に書いていると気づきました（出次数と入次数をうまく使って証明するんでしょうけれど、未証明です。ごめんなさい）。

ここまでわかれば実装です。
実装では、連結成分ごとの頂点数と枝の数を扱うのが少し複雑です。
連結成分といえば UnionFind木ですが、今回の問題ではうまく使えません。
( `unite() / merge()` を改造すれば解けますが、`petgraph::unionfind` を使えないので大変です )
おとなしく BFS でやりましょう。

コメントをコードに入れたので参考ください。

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

  if n != m {
    println!("0");
    return;
  }

  // Vec::<(頂点, index)>
  let mut graph = vec![vec![]; n];
  for i in 0..m {
    let (from, to) = uv[i];
    let from = from - 1;
    let to = to - 1;

    graph[from].push((to, i));
    graph[to].push((from, i));
  }

  let mut shown_node = vec![false; n];
  let mut shown_edge = vec![false; m];
  let m = 998244353_i64;
  let mut ans = 1_i64;

  // 0 から順に BFS
  for now in 0..n {
    // この判定を入れることで、各連結成分につき一度だけチェックできる
    if shown_node[now] { continue; }

    let mut que = VecDeque::<usize>::new();
    que.push_back(now);

    let mut node = 0; // この連結成分の頂点の数
    let mut edge = 0; // この連結成分の枝の数

    while let Some(now) = que.pop_front() {
      if shown_node[now] { continue; }
      shown_node[now] = true;
      node += 1;
      for (to, i) in graph[now].iter() {
        if !shown_edge[*i] {
          edge += 1;
          shown_edge[*i] = true;
        }
        que.push_back(*to);
      }
    }

    if node == edge {
      ans *= 2;
      ans %= m;
    }
    else {
      ans = 0;
      break;
    }
  }
  println!("{}", ans);
}

```


----

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