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

# はじめに

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

# なぜやるのか

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

# 目次

[A - Cabbages](#a---cabbages) (<font color="#808080">Difficulty 19</font>)
[B - Bouzu Mekuri](#b---bouzu-mekuri) (<font color="#808080">Difficulty 22</font>)
[C - Colorful Candies](#c---colorful-candies) (<font color="#808080">Difficulty 359</font>)
[D - National Railway](#d---national-railway) (<font color="#00C0C0">Difficulty 1507</font>)
[E - Ring MST](#e---ring-mst) (<font color="#0000FF">Difficulty 1618</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 - Cabbages

割引されながらキャベツを買う問題ですね。
問題文を読み解いてコードにすると、以下のようになるかと思います。

```rust
fn main() {
  input! {
    n: usize,
    a: usize,
    x: usize,
    y: usize
  }

  let ans = if a <= n {
    a * x + (n - a) * y // [a 個 が x 円] + [(n-a) 個 が y 円]
  } else {
    n * x
  };
  println!("{}", ans);
```

もしくは `min` と `max` を使って1行にまとめることもできます。
型を `usize` や `u32` などにしていると `max(0, n - a)` の `n - a` の部分で壊れるので注意です。

```rust
fn main() {
  input! {
    n: i32,
    a: i32,
    x: i32,
    y: i32
  }
  println!("{}", min(n, a) * x + max(0, n - a) * y);
}
```

# B - Bouzu Mekuri

山札からカードを交互に引いて `1` が出ると負けのゲームですね。
入力文字列 `S` のうち、始めにでてくる `1` が何番目かわかれば答えがわかります。
(いちど `1` がでれば、それ以降がすべて `1` だったり、`1` がひとつもでなかったりしても、勝敗には関係ありません)

`for` で先頭から 1 文字ずつ調べてもいいのですが、関数を使ってシンプルに書きたいです。書く量が減るとバグが減り、より速く提出できるからです。
調べると `find` という関数があるのでこれを使います。また、今回は問題の条件から `1` が必ず含まれていることがわかるので、`unwrap()` を使えますね。
これで `1` が何番目かわかるので、偶奇を判定して答えです。

```rust
fn main() {
  input! {
    _n: usize,
    s: String
  }
  let idx = s.find('1').unwrap();
  let ans = if idx % 2 == 0 { "Takahashi" } else { "Aoki" };
  println!("{}", ans);
}
```


# C - Colorful Candies

$N$ 個のキャンディーのうち、連続した $K$ 個の範囲にある種類の最大値を答える問題ですね。少し複雑です。

$1$～$K$番目、$2$～$K+1$番目 ... と言われたままに計算すると、全体の計算量が $K * (N - K + 1) = O(NK)$ かかります。今回の制約だと TLE してしまうので、なにか工夫が必要です。

これは尺取り法で考えましょう。配列上を範囲をずらしながら走査するアルゴリズムです。
境界だけを更新することで、共通部分を使いまわしながら範囲の情報を効率的に扱えます。

今回の問題では、範囲を1つ分更新するときは
・区間の左端を削除して
・区間の右端を追加する
という操作をすれば十分なことがわかります。境界ではない部分は共通しているので、以前に計算したものを使いまわせます。
つまり、1つ分の範囲の更新が $O(1)$ でおわります。前処理に $O(K)$ が必要なので、全体の計算量は $O(N + K)$ でいけそうですね。制約も間に合います。

----

ただ、今回は $C$ の範囲がとても広く、$C$ の扱いにも工夫が必要です。$C$ の全範囲を `vector` で持ったりすると、メモリ制限に引っかかります。
対策としては
・座標圧縮する
・HashMap を使う
などありますが、座標圧縮は書くのが少し大変なので、今回は HashMap を使います。
> 座標圧縮が気になる方は [ここ](https://atcoder.jp/contests/abc036/tasks/abc036_c) を見ると載っています。
> 実装は [ここ](https://atcoder.jp/contests/abc036/submissions?f.Task=abc036_c&f.LanguageName=Rust&f.Status=AC&f.User=) の [詳細] へどうぞ。

座標圧縮をするにも HashMap を使うにも $O(N\ log\ N)$ かかるので、全体の計算量が $O(N\ log\ N)$ になりました。
それでも制約には間に合いそうなので、この方針で実装します。

----

ここでもうひとつ。
Rust 的には  `HashMap` というと `match` を使って以下のような使い方をするかもしれません。

```rust
match mp.get(&key) {
  None => { ... },
  Some(&val) => { ... }
}
```

こちらについて、もっとシンプルな書き方を見つけたので紹介します。

```rust
  // mp[key] を返す。なければ 0 で初期化する
  *mp.entry(key).or_insert(0);

  // 戻り値は value として扱える  
  *mp.entry(key).or_insert(0) += 1;
```

これは、 `key` を探索して、見つからなければ `0` で初期化します。そのまま `value` として使えます。
また、 `match` を使うと `{ ... }` の部分で検索の処理を書くことが多く、合計で2回の検索がされます。それに対して `entry` を使った場合は1回の検索で済むので、速度でも得をします。

さて、以上をもとに実装すると、例えば次のようになりました。
キャンディの種類は別の変数に持つこともできますが、出てくる変数を減らしたかったので HashMap のサイズを使っています。

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

  let mut mp: HashMap<usize, usize> = HashMap::new();

  // 先頭から k 個のキャンディを処理する
  for i in 0..k {
    *mp.entry(c[i]).or_insert(0) += 1;
  }

  // len() がいま持っているキャンディの種類になる
  let mut ans = mp.len();

  // 残りのキャンディについて処理する
  for i in k..n {
    // i (右端) を加えて、 i-k (左端) を引く
    *mp.entry(c[i]).or_insert(0) += 1;
    *mp.entry(c[i - k]).or_insert(0) -= 1;

    // いま持っているキャンディの種類を len() で表すので、個数が 0 になったものは取り除く
    if mp[&c[i - k]] == 0 {
      mp.remove(&c[i - k]);
    }

    // 答えを更新
    ans = max(ans, mp.len());
  }
  println!("{}", ans);
}
```


# D - National Railway

なんか複雑な問題ですね。 愚直にやると $O(H^2 W^2)$ です。
探索範囲が非常に広くなるのでまず解けません。

ひとつずつ考えていきましょう。
まずは絶対値があります。これは非常に扱いにくいので、絶対値をなくすことを考えます。
(マンハッタン距離が浮かぶかもしれませんが、残念ながら今回は使えません)
$i$ と $j$ が減らない方向(南東の方角)へ進めば絶対値は不要になることがわかります。つまり、探索の方向を固定することで絶対値を外せることがわかります。そうすると計算できないパターンが出てきますが、グリッドを回転 / 反転させて2回探索すれば十分です。回転させるのはグリッドの問題でよくつかわれるテクニックです。

これでまずは絶対値を外せました。また、探索の方向が固定されました。

次は、座標 $(y, x)$ に駅を作って終わることを考えましょう。座標 $(y, x)$ にくる前のマスにいた時のコストを $cost$ とすると、座標 $(y, x)$ に駅を作って終わる時のコストは $cost + C + A_{yx}$ になります。1マス移動するコストの $C$ と、駅を作るコストの $A_{yx}$ が足されています。

これで漸化式の草案ができました。あとはこれを DP に落としこみます。
`dp[y][x] = どこかに駅を立てて (y, x) にいるときの最小コスト` とすると DP ができそうです。
`dp[y][x] = c + min(dp[y - 1][x], dp[y][x - 1], a[y - 1][x], a[y][x - 1])`
となるでしょうか。
`a[y - 1][x]` と `a[y][x - 1]` で「駅を作る」分のコストが考慮されています。
「駅を作って終わる」分のコストは含まれていないので注意です。
「駅を作って終わる」時のコストは `dp[y][x] + a[y][x]` になります。今回はこれを最小化する問題でしたね。 `dp` 配列の更新に合わせて最小値を計算しましょう。

32bit では収まらないこと、範囲外のケア、反転の処理に注意しながら実装します。
反転については上下でも左右でも、回転でも大丈夫です。180度の回転はダメなのでご注意ください。1回目に探索した方向と、2回目で探索する方向が直行していれば問題ありません。
また、dp の配列を初期化するタイミングに注意です (ひとつ外側のスコープで初期化しても、嘘解法で通ってしまうので混乱しました)。

これらを実装すると、以下のようになりました。

```rust
fn main() {
  input! {
    h: usize,
    w: usize,
    c: u64,
    mut a: [[u64; w]; h]
  }

  let inf: u64 = 1_000_000_000_000_000_000;
  let mut ans = inf;
  
  for _ in 0..2 { 
       
    // どこかに駅を立てて dp[y][x] にいるときの最小コスト
    let mut dp = vec![vec![inf; w]; h];
    // dp[y][x] + a[y][x] が (y, x) に2つめの駅を立てた時のコストになる
    // この dp[y][x] + a[y][x] を最小化する
    
    // 移動方向を固定することで、絶対値を外して考えられる
    for y in 0..h {
      for x in 0..w {
        if y > 0 && x > 0 {
          dp[y][x] = min(
              min(dp[y - 1][x], dp[y][x - 1]),
              min( a[y - 1][x],  a[y][x - 1])
            ) + c;
        }
        else if y > 0 { // x == 0 のとき
          dp[y][x] = min(dp[y - 1][x], a[y - 1][x]) + c;
        }
        else if x > 0 { // y == 0 のとき
          dp[y][x] = min(dp[y][x - 1], a[y][x - 1]) + c;
        }
        ans = min(ans, dp[y][x] + a[y][x]);
      }
    }

    // 上下反転
    for y in 0..h / 2 {
      let (v1, v2) =  a.split_at_mut(h - y - 1);
      mem::swap(&mut v1[y], &mut v2[0]);
    }
  }
  println!("{}", ans);
}
```

# E - Ring MST

グラフの問題ですね。クラスカル法と似ています。

初めは$N$ 個の頂点があって、辺は $0$ 個です。この状態で頂点同士に辺をつなぐと連結になりますね (あたりまえ)。すると、連結成分の個数が減ります。
この連結成分の個数を減らしていって、すべて連結になれば終わりです。この「辺をつなぐ」処理に数値 $A_i$ とコスト $C_i$ を使うので、このコストを最小化しましょう。

基本の方針としては、コストの小さいものから、連結成分の個数が減らせるだけ貪欲に減らしていくというものです。
連結成分を減らすので、その個数がどう減るかに注目しながら実際に試してみましょう。$A_i = 1, 2, 3, ... $ と試していくと、その減り方に特徴があると分かります。
例えば、$(N, A) = (10, 2)$ なら $2$ になって、$(N, A) = (10, 3)$ なら $1$ になって、、、などですね。 
観察を進めると、これは $gcd\ (N, A)$ の値になると分かります。
文章にすると、「連結成分の個数が $N$ 個のときに $A$ を使って可能なだけ辺をつなぐと、連結成分の個数が $gcd\ (N, A)$ になる 」です。
あとは、「すべての頂点が連結になる」 = 「連結成分の個数が $1$ 個になる」 = 「累積 GCD が $1$ になる」まで辺を繋げれば答えがわかります。

ここまでわかれば実装です。


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

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

  let mut acc = n; // 累積 gcd
  let mut ans = 0;

  // コスト順にソートする
  // a や (a, c) が重複するけれど、答えには影響しないので重複除去しない
  ac.sort_by_key(|k| k.1);
  for (a, c) in ac {
    let prev = acc;
    acc = gcd(acc, a);
    // 辺を1つつなぐと、連結成分の個数が1つ減るので、
    // 減った個数である (prev - acc) がつないだ辺の個数になる
    ans += c * (prev - acc);
  }

  if acc != 1 {
    println!("{}", -1);
  } else {
    println!("{}", ans);
  }
}
```