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

# はじめに

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

# なぜやるのか

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

# 目次

[A - Rolling Dice](#a---rolling-dice) (<font color="#808080">Difficulty 28</font>)
[B - Factorial Yen Coin](#b---factorial-yen-coin) (<font color="#808080">Difficulty 51</font>)
[C - Fair Candy Distribution](#c---fair-candy-distribution) (<font color="#808080">Difficulty 142</font>)
[D - Shortest Path Queries 2](#d---shortest-path-queries-2) (<font color="#008000">Difficulty 1190</font>)

# A - Rolling Dice

1~6 が出るサイコロを $A$ 回ふったとき、合計値を $B$ にすることができますか？という問題です。

合計値は最小で $A$、 最大で $A * 6$ になりますね。
範囲で考えるとわかりやすくて、 $A$ ～ $A * 6$ の範囲に $B$ があれば `Yes` で、なければ `No` です。
`let ans = if min <= b && b <= max { "Yes" } else { "No" };`
または
`let ans = if (min..=max).contains(&b) { "Yes" } else { "No" };`
などで解けます。

```rust
fn main() {
  input! {
    a: usize,
    b: usize
  }
  let min = a;
  let max = a * 6;
  let ans = if (min..=max).contains(&b) { "Yes" } else { "No" };
  println!("{}", ans);
}
```

# B - Factorial Yen Coin

$1!$ 円 から $10!$ 円 までの硬貨を使って $P$ 円 を払う問題ですね。このときに払う枚数を少なくします。

これは 
$1$ 円, 
$10$ 円, 
$100$ 円, 
$1000$ 円, 
$10000$ 円, 
$100000$ 円... を使ってお金を払うことを考えるとイメージしやすいです。
例えば、 $12345$ 円を払うときは $1 + 2 + 3 + 4 + 5 = 15$ 枚が最小ですね。
これを考えるときは金額の大きいものから順に払っていったと思います。
同様に今回の問題でも、金額の大きい硬貨から払っていけば最小の払い方になります。
また、この払い方をすると、硬化ごとの払う枚数が最大でも10枚ほどになります。
つまり、問題文にある $100$ 枚の制約は無視できます。

さて、ここまでわかったら実装です。

階乗を計算するので、私は関数にしました。
`for` を降順でまわすので、範囲を`(1..=10).rev()` にしています。
`p / coin` が払える枚数で、払った後は `p % coin`円 が残ります。

```rust
fn fact(n: usize) -> usize {
  if n <= 1 { 
    1 
  } else { 
    n * fact(n - 1)
  }
}

fn main() {
  input! {
    mut p: usize
  }

  // 大きい硬貨から
  let mut ans = 0;
  for i in (1..=10).rev() {
    let coin = fact(i);
    // いまの硬貨で払えるだけ払う
    ans += p / coin;
    // 残り金額が p % coin になる
    p %= coin;
  }
  println!("{}", ans);
}
```

# C - Fair Candy Distribution

$N$ 人に $K$ 個のキャンディを配る問題ですね。
全員に最低でも $K / N$ 個は配ることができます。
残るキャンディは $K % N$ 個で、これを国民番号が小さい順に配ります。
この国民番号について $O(N)$ でループすれば解けるのですが、 $10^9$ なので TLE します。何か工夫が必要です。
少し考察を進めると、国民番号は値に意味はなく、その大小だけが重要な情報だということがわかります。
つまり大小関係を保ったまま最大値を小さくすればいいですね。それは座標圧縮という操作になります。
もしくは、 `iter().enumerate()` をしたあと、第2要素でソートしても大丈夫です。

ここまでわかったら実装です。

実装の流れはコメントに書いたのでご覧ください。

```rust
fn main() {
  input! {
    n: i64,
    k: i64,
    mut a: [i32; n]
  }

  // a を (index, 番号) の形にしてから番号でソートする
  // 型がかわるので shadowing をする
  let mut a = a.iter().enumerate().collect::<Vec<_>>();
  a.sort_by_key(|&(_, a)| a);

  // n 人に k / n 個ずつ配る
  // 残りキャンディが k % n 個になる
  let mut ans = vec![k / n; n as usize];

  // a が番号順にならんでいるので、
  // 番号の小さいほうから k % n 人にキャンディを配る
  for i in 0..(k % n) as usize {
    let idx = a[i].0;
    ans[idx] += 1;
  }

  for i in 0..n as usize {
    println!("{}", ans[i]);
  }
}
```

# D - Shortest Path Queries 2


ワーシャルフロイド法しってますか？という問題です。
ワーシャルフロイド法は全点対最短経路を求められるアルゴリズムです。
$O(N^3)$ なので、 $N$ が $500$ 程度までは実行時間内で実行できます。

例えば、他の有名なグラフアルゴリズムであるダイクストラ法は、単一始点最短経路を $O(|E|\ log\ |V|)$ で求められます。

さて、この問題はワーシャルフロイド法で最短経路を見つける過程を理解していれば解けます。
辺がつながっていると `dist[from][to]` が初期値から更新されて答えの計算対象になります。
以下の式で判定して、答えに加算します。
`if dist[from][to] != INF { ans += dist[from][to]; }`


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

  // INF で初期化した N x N の二次元配列を作る
  const INF: i64 = 1 << 60;
  let mut dist = vec![ vec![INF; n]; n];
  for i in 0..n {
    dist[i][i] = 0;
  }

  for i in 0..m {
    let (from, to, cost) = edge[i];
    dist[from - 1][to - 1] = cost as i64;
  }

  let mut ans = 0;
  for k in 0..n { // k のノードを経由する
    for from in 0..n { // 開始点
      for to in 0..n { // 終了点
        dist[from][to] = min(dist[from][to], dist[from][k] + dist[k][to]);
        if dist[from][to] != INF { ans += dist[from][to]; }
      }
    }
  }
  println!("{}", ans);
}
```