ABC211 を Rust で解く (D問題まで)

# はじめに

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

# なぜやるのか

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

# 目次

[A - Blood Pressure](#a---blood-pressure) (<font color="#808080">Difficulty 6</font>)
[B - Cycle Hit](#b---cycle-hit) (<font color="#808080">Difficulty 17</font>)
[C - chokudai](#c---chokudai) (<font color="#804000">Difficulty 559</font>)
[D - Number of Shortest paths](#d---number-of-shortest-paths) (<font color="#804000">Difficulty 755</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 - Blood Pressure

問題文に答えの式が書いてありますね。
`(A - B) / 3 + B` または、展開して `A / 3 + B * 2 / 3` などで答えがわかります。
小数点以下も出力する必要があるので、型は `f32` や `f64` にすることに注意です。

```rust
fn main() {
  input! {
    a: f32,
    b: f32
  }
  let ans = a / 3.0 + b * 2.0 / 3.0;
  println!("{}", ans);
}
```

# B - Cycle Hit

重複があるか確かめる問題ですね。

入力からもらった 4つの要素に重複がなければ条件と合います。
条件を満たす並び方は `4! = 24` 通りなのですべて調べれば解けますが、少し大変ですね。
今回は `Vec` にいれて、ソートするのが手軽です。
ソートした後は、1要素ずつ確認したり、重複除去したり、といった方法があります。
もしくは、HashSet をつかっても判定できます。

### 1要素ずつ確認する

```rust
fn main() {
  input! {
    s1: String,
    s2: String,
    s3: String,
    s4: String,
  }
  let mut vec = vec![s1, s2, s3, s4];
  vec.sort();
  let ans = if
     vec[0] == "2B" &&
     vec[1] == "3B" &&
     vec[2] ==  "H" &&
     vec[3] == "HR"
  {
    "Yes" 
  } else { 
    "No"
  };
  println!("{}", ans);
}
```

### 重複除去する
```rust
fn main() {
  input! {
    s1: String,
    s2: String,
    s3: String,
    s4: String,
  }
  let mut vec = vec![s1, s2, s3, s4];
  vec.sort();
  vec.dedup();
  let ans = if vec.len() == 4 { "Yes" } else { "No" };
  println!("{}", ans);
}
```

### HashSet をつかう

```rust
fn main() {
  input! {
    s1: String,
    s2: String,
    s3: String,
    s4: String,
  }
  let set: HashSet<String> = vec![s1, s2, s3, s4].iter().cloned().collect();
  let ans = if set.len() == 4 { "Yes" } else { "No" };
  println!("{}", ans);
}
```



# C - chokudai

典型90問の8問目 ([AtCounter](https://atcoder.jp/contests/typical90/tasks/typical90_h)) とほぼ同じ問題ですね。DPの問題で、中でも「耳DP」と呼ばれるものです。
典型90問の[解説](https://twitter.com/e869120/status/1379927227739987972?s=20)が画像つきでよくまとまっているので載せておきます 

`chokudai` をつくるには `chokuda` が必要ですね。このように、前から $n$ 文字を作るには、前から $n-1$ 文字が必要です。
答えの組み合わせについて、前から $n-1$ 文字の組み合わせがわかると、前から $n$ 文字の組み合わせの数がわかります。
つまり、`組み合わせ[i文字まで] = 組み合わせ[i-1文字まで]` になります。
これが、同じ文字が出るたびに加算されるので、
`組み合わせ[i文字まで] = 組み合わせ[i文字まで] + 組み合わせ[i-1文字まで]`
という式になります。

コードでは `組み合わせ[i文字まで]` を `dp[i]` で表しています。

また、このコードは `base` を書き換えることで、様々な文字列に対応できるようになっています (典型90問でも使えます) 。 ご参考になれば幸いです。
これはちょっとしたコツですが、 `dp[i] %= m;` の部分は `if dp[i] >= m { dp[i] -= m; }` とすると少し速くなります。試してみてください。

```rust
fn main() {
  input! {
    s: Chars
  }
  let m = 1000000007;
  let base = "chokudai";
  let mut dp = vec![0_i32; base.len()]; // base の i 文字目を作る組み合わせ
  for c in s {
    for (i, bc) in base.chars().enumerate() {
      if c == bc {
        if i == 0 {
          dp[0] += 1;
        } else {
          dp[i] += dp[i - 1];
          dp[i] %= m;
        }
      }
    }
  }
  println!("{}", dp[base.len() - 1]);
}

```

# D - Number of Shortest paths

これも DP の問題ですね。グラフの頂点に沿って更新する問題です。

問題文には「都市 $1$ から $N$ まで "最も速く" 移動する」とあるので、都市を頂点・道路を辺として、頂点 $1$ から頂点 $N$ への最短経路を考えます。
問題文を言い換えると、頂点 $1$ から頂点 $N$ への最短経路の数を求める問題になります。(前提として、今回のグラフは木ではないので、最短経路も複数個あります。)
最短経路を扱うときは BFS を使うと考えやすくて、データ構造的には `Queue` を使います。

通常の BFS では、各頂点に2回目以降に遷移したときは枝刈りをするので処理されません。しかし今回の問題では、「最短経路で合流した場合」に限り2回目以降の処理が必要です。
つまり、「初めて訪れた場合」と「最短距離で2回目以降に訪れた場合」を判定しながら BFS をします。
これは頂点 $1$ からの距離を記録しておけば判定可能です。
・「初めて訪れた場合」は、初期値かどうか
・「最短距離で2回目以降に訪れた場合」は、 `if 遷移先の距離 == いまの距離 + 1`
で判定します。

あとは「今の頂点に最短距離で移動する経路」の数を更新しながら頂点 $N$ まで遷移すれば答えがわかります。
コードでは「今の頂点に最短距離で移動する経路」の数を `dp[i]` で表しています。

```rust
fn main() {
  input! {
    n: usize,
    m: usize,
    ab: [(usize, usize); m]
  }
  let mut graph = vec![vec![0; 0]; n];
  for (mut a, mut b) in ab {
    a -= 1;
    b -= 1;
    graph[a].push(b);
    graph[b].push(a);
  }

  let m = 1000000007;
  let mut dp = vec![0_i32; n];
  let mut dist = vec![0; n];
  let mut que = VecDeque::<usize>::new();
  dp[0] = 1;
  dist[0] = 0;
  que.push_back(0);
  while let Some(now) = que.pop_front() {
    // BFS なので、初めて now に着いたときは最短経路になっている
    // now についたあとで que に残っているものは最短経路ではないので、この枝刈りができる
    // n - 1 からの遷移は不要
    if now == n - 1 { break }

    for &next in graph[now].iter() {
      // now からいける頂点が next になる
      if dist[next] == 0 {
        // 初めて来たとき
        dist[next] = dist[now] + 1;
        que.push_back(next);
        dp[next] += dp[now];
      } else if dist[next] == dist[now] + 1 {
        // 別のノードから最短経路で合流したとき
        dp[next] += dp[now];
      }
      dp[next] %= m;
    }
  }
  println!("{}", dp[n - 1]);
}
```