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

# はじめに

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


# なぜやるのか

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


# 問題

[A - Swap Odd and Even](https://atcoder.jp/contests/abc293/tasks/abc293_a) (<font color="#808080">Difficulty 12</font>)
[B - Call the ID Number](https://atcoder.jp/contests/abc293/tasks/abc293_b) (<font color="#808080">Difficulty 65</font>)
[C - Make Takahashi Happy ](https://atcoder.jp/contests/abc293/tasks/abc293_c) (<font color="#804000">Difficulty 431</font>)
[D - Tying Rope](https://atcoder.jp/contests/abc293/tasks/abc293_d) (<font color="#008000">Difficulty 830</font>)
[E - Geometric Progression](https://atcoder.jp/contests/abc293/tasks/abc293_e) (<font color="#00C0C0">Difficulty 1453</font>)
[F - Zero or One](https://atcoder.jp/contests/abc293/tasks/abc293_f) (<font color="#C0C000">Difficulty 2038</font>)
[G - Triple Index](https://atcoder.jp/contests/abc293/tasks/abc293_g) (<font color="#0000FF">Difficulty 1753</font>)
[Ex -  Optimal Path Decomposition](https://atcoder.jp/contests/abc293/tasks/abc293_h) (<font color="#FF0000">Difficulty 2831</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 - Swap Odd and Even

入力された文字列を入れ替える問題ですね。

入れ替え方が独特で、
- 1文字目と2文字目
- 3文字目と4文字目
- ...
という入れ替え方をします。

入力を `mut` でもらったあと、 `swap` を使って入れ替えることで実装できました。

```rust
    input! {
        mut s: Chars
    };

    for i in 0..s.len() / 2 {
        s.swap(i * 2, i * 2 + 1);
    }
    println!("{}", s.into_iter().join(""));
```


# B - Call the ID Number 

ちょっと複雑な問題ですね。
実際にシミュレーションをしてみれば問題概要がわかるかと思います。

また、この問題は効率的な解き方が浮かびにくいかもしれませんが、そういうときは愚直にシミュレーションをすると解けたりします。
実際にこの問題もシミュレーションで解きます。

ひとりずつ順番に見ていけばシミュレーションができるので、計算量は $O(N)$  になります。十分間に合います。

コードはこのようになりました。

```rust
    input! {
        n: usize,
        a: [Usize1; n]
    };

    // 1 だったら呼ばれていない
    let mut res = vec![1; n];

    for i in 0..n {
        // 呼ばれていなければ
        if res[i] == 1 {
            // a[i]番目 の人を呼ぶ
            res[a[i]] = 0;
        }
    }

    // 呼ばれていない人数
    println!("{}", res.iter().sum::<usize>());

    // 呼ばれていない人の番号
    for i in 0..n {
        if res[i] == 1 {
            println!("{}", i + 1);
        }
    }
```


# C - Make Takahashi Happy  

グリッド上を動きながら、同時に数字を管理する問題ですね。
AtCoder ではこのようなグリッドを扱う問題はよく出ます。

計算量を考えてみます。まずは全探索から。
取り得るルートを列挙してみると、 $H = 10, W = 10$ の時に最大となって、 $C(H + W - 2,  W - 1) = C(18, 9) = 48620$ 通りです。
今回の問題はそれに加えて整数の重複判定もあるのですが、これに $O((H + W)^2)$ かかるとして、 $C(18, 9) * 20^2 = 19448000$ ステップです。
実際は重複判定の部分が $(H + W)^2$ よりも小さくなるので、全探索で十分に間に合う計算量になりました。

続いて実装です。グリッドでの全探索は DFS や BFS をよく使います。今回も例に漏れずDFSを使います。
DFS といえば再帰ですね。もしくは `while` と `vec` を使っても実装できます。今回は再帰でやりました。

:::note

`while` と `vec` を使うときは、ループ部分でこのようにするとスマートです

```rust
while let Some(val) = vec.pop() {
  ...
}
```

:::

コードはこのようになりました。

```rust
fn dfs(y: usize, x: usize, mp: &Vec<Vec<usize>>, stack: &mut Vec<usize>) -> usize {
    // 枝刈り
    // 見たことある数字だったら return
    if stack.contains(&mp[y][x]) {
        return 0;
    }

    let h = mp.len();
    let w = mp[0].len();

    // 端まで来た
    if y == h - 1 && x == w - 1 {
        return 1;
    }

    // いまのグリッドの整数を stack にいれる
    stack.push(mp[y][x]);
    let mut ret = 0;

    // 下
    if y < h - 1 {
        ret += dfs(y + 1, x, mp, stack);
    }

    // 右
    if x < w - 1 {
        ret += dfs(y, x + 1, mp, stack);
    }

    // いまのグリッドから抜けるときに、
    // この回で stack に入れた整数 (mp[y][x]) を抜く
    stack.pop();
    ret
}

#[fastout]
fn main() {
    input! {
      h: usize,
      w: usize,
      mp: [[usize; w]; h]
    };

    let mut stack = vec![];
    println!("{}", dfs(0, 0, &mp, &mut stack));
}
```



----

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