Rust初心者がAtCoder Beginers SelectionをRustで解いてみた

Rustの勉強を始めたので,今回はRustの理解も兼ねて
[AtCoder Beginners Selection](https://atcoder.jp/contests/abs)を解いてみます.

自分がAtCoderで水色で、そのレベルだとここの問題を解くのは難しくないレベルです.
なので,問題を解くアルゴリズムを考えることではなく,Rustの文法に慣れることを目指して解説していきます.

## 文字列の扱い
競技プログラミングでは入力を受けて処理をするので、まず入力の文字列を処理する方法を考えます.

Rustでは文字列を扱うときはよくstr型とString型が使われます.
Stringは[コード](https://github.com/rust-lang/rust/blob/master/src/liballoc/string.rs#L283)を見ると構造体としては
Vector型で,strはu8のスライスとなります.

どちらもutf8以外受け取らない様になっています.

### 変換方法
これらは簡単に変換することができまず.実際,以下で変形します.

str -> String: `to_string`,
String -> &str:  `&`をつけるだけ

Stringはヒープに値を持つの可変長,strは固定長なので,適当に文字列操作して新しい文字列を操作するのであれば,`&str`型を使うほうが性能が出そうです.
ただ,str型は基本さらに参照して使う事が多いため,メソッドの引数と復帰値両方に使う場合はライフタイムを意識しないといけない場合はがあります.

### メソッドでのライフタイム

ライフタイムは変数が何かを参照して作ったもの場合に,その参照先のデータが残っていることを保証するための仕組みです.

とはいえ、常に書いていると面倒なので、基本はコンパイラ側で推論してくれています.
ただ,いつまでなのか期間が保証されない場合は自分で指定する必要があります.
例えば以下のメソッドを見ます.


```rust
fn main() {
    let hello = "Hello";
    let world = "World";
    println!("{}", longer(hello, world));
}

fn longer(x: &str, y: &str) -> &str {
    if x.len() >= y.len() { return x} else {return y}
    }
```
これをコンパイルしようとすると,

```
|
9 | fn longer(x: &str, y: &str) -> &str {
 |                                ^ expected lifetime parameter
 |
 = help: this function's return type contains a borrowed value, but the signature does not say whether it is borrowed from `x` or `y`
```
とエラーになります.

この変数の復帰値がどこまでのライフタイムを保証すればいいかわからないからです.
この場合はx,yの短い方と明記する必要があります.(実際これをライフタイムの短い方に勝手に推論してくれてもいい気はしますが...)
なので、引数の参照になる場合は気をつけなければいけません.

これを回避するにはライフタイムを指定するのが常套手段ですが,
それ以外に以下のように新しくヒープ領域にデータを作ってしまう(つまりString)にしてしまうという方法があります.

```rust
fn main() {
    let hello = "Hello";
    let world = "World";
    println!("{}", longer(hello, world));
}

fn longer(x: &str, y: &str) -> String {
    if x.len() >= y.len() { return x.to_string()} else {return y.to_string()}
    }
```

こういうエラーははまりやすいので、メソッドの復帰値では新しい文字列をStringで生成する方が楽なのかなと思います.

## 標準入力

rustの標準入力はread_lineが使われます.
引数は必ず文字列型になるため、AtCoder用には条件に応じて型を変換する必要があります.

```rust
let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();
```
AtCoderでそのまま読むには[これ](https://qiita.com/penguinshunya/items/cd96803b74635aebefd6)が一番素直なやり方かなと思います.


## AtCoderの問題
前置きが相当長くなったので、この辺から真面目にAtCoderときましょう.

今回は上のサイトにある`read`のコードを使いました.
また,全てを使うわけではないので、何も考えずにコンパイルするとwarningが出ます.
なので、コードの先頭に`#![allow(dead_code)]`と書くことを推奨しておきます.

### Prcatice
文字を入力として、ただしく受け取ればよいです.
今回は数値は`read_vec`,文字列は`read`で取得してみます.

```rust
fn practice() {
    let first_int: Vec<i32> = read_vec();
    let second_int: Vec<i32> = read_vec();
    let s: String = read();
    let mut res = first_int[0];
    res += second_int[0] + second_int[1];
    println!("{} {}", res, s);
}
```

### ABC086a
入力の積を2で割った余りをみて出力します.

```rust
fn abc086a() {
    let fline: Vec<i32> = read_vec();
    if (fline[0] * fline[1]) % 2 == 1 {
        println!("Odd");
    } else {
        println!("Even");
    }
}
```
### ABC081a
文字として受け取って、一文字ずつループさせ、'1'の場合は1増やします.

```rust
fn abc081a() {
    let s: String = read();
    let mut num = 0;
    for i in 0..3 {
        if s.chars().nth(i).unwrap() == '1' {
            num += 1;
        }
    }
    println!("{}", num);

}
```

### ABC081B

問題はループの中で再帰的に2で割っていけば,求まると思います.
rustの場合,条件を満たすまでずっとループするのは`loop`でかけます.
脱出の時はbreakですが、今回のようにforでネストしてしまう場合はスコープを指定する必要があります.

```rust
fn abc081() {
    let n: usize = read();
    let mut A: Vec<i32> = read_vec();
    let mut ret = 0;
    'outer: loop {
        for i in 0..n {
            if A[i] % 2 == 1 {
                break 'outer;
            } else {
                A[i] /= 2;
            }
        }
        ret += 1;
    };
    println!("{}", ret);
}
```

### ABC087B
1250通りしかないので、愚直に全探索します.

```rust
fn abc087b() {
    let a: i32 = read();
    let b: i32 = read();
    let c: i32 = read();
    let x: i32 = read();
    let mut num = 0;
    for _a in 0..(a+1) {
        for _b in 0..(b+1) {
            for _c in 0..(c+1) {
                if 500 *_a + 100 * _b + 50 * _c  == x {
                    num += 1;
                }
            }
        }
    }
    println!("{}", num);
}
```

### ABC083B
これも10000個しかないので、全探索します.
桁数の和は数値を文字列に変形して,一文字ずつ分割した後足しました.
rustの場合はchar型の列にして、それを文字コードをみながら整数に置き直しています.

```rust
fn abc083b(){
    let input: Vec<i32> = read_vec();
    let (n, a, b) = (input[0], input[1], input[2]);
    let mut num = 0;
    for _n in 1..(n+1) {
        let _n_sum: i32 = _n.to_string().chars().map(|c| c as i32 - 48).fold(0, |sum, c| sum + c);
        if _n_sum >= a  && _n_sum <= b {
            num += _n;
        }
    }
    println!("{}", num);
}
```

### ABC088B
全体をソートして差分をひきます.

```rust
fn abc088b() {
    let n: usize = read();
    let mut a: Vec<i32> = read_vec();
    let mut num = 0;
    a.sort();
    for _n in 0..n {
        if _n % 2 == 0 {
           num += a[n-1-_n];
        } else {
            num -= a[n-1-_n];
        }
    }
    println!("{}", num);
}
```
### ABC085B
重複排除して、サイズを数えればよいです.
重複排除するときはsetにするのが自然かと思いますが,
rustの場合はHashSetクラスが存在するので、それで計算します.

```rust
fn abc085b(){
    let n: u32 = read();
    let d: Vec<Vec<u32>> = read_vec2(n);
    let uniq_d: HashSet<u32> = d.into_iter().map(|x| x[0]).collect();
    println!("{}", uniq_d.len());
}
```

### ABC085C
条件を考えると
1000円札をz枚使ったとき,
10000円札をx枚、5000円札をy枚使う解答があるかどうかは

- $Y - 1000 z$ が$5000$で割り切れ

さらに,以下の方程式について、x,yを解くと0以上の整数解(今回は整数には必ずなので)になればよいです。

- $2x + y = (Y - 1000 z) / 5000$
- $x + y =  N - z$

それは $x = (Y -1000 z) / 5000  - N + z >= 0$かつ$y = N - z - x >= 0$で判定できます.

```rust
fn abc085c(){
    let input: Vec<i32> = read_vec();
    let (n, Y) = (input[0], input[1]);
    let mut flag = false;
    for z in 0..(n+1) {
        if (Y - 1000 * z) % 5000 != 0 { continue }
        let div_y = (Y - 1000 * z) / 5000;
        let x = div_y - n + z;
        let y = n - z - x;
        if x < 0 || y < 0 { continue }
        flag = true;
        println!("{} {} {}", x, y, z);
        break
    }
    if !flag {
        println!("{} {} {}", -1, -1, -1);
    }
}
```



### ABC049C
貪欲に解けばいいです.後ろからの方が楽そうですが,何も考えずに前から解きます.
条件をざっと考えると,

- 1文字目がeの場合
  - eraser or erase
  - 文字の長さが5かつeraseならYes
  - 文字の長さが6かつeraserならYes
  - 文字列の長さが6以下で上記以外の場合No
  - 6文字目がrならeraserを削除
  - 6文字目がe or dなら eraseを削除
  - それ以外No
- dreamの場合も同様に分けていけばよい.
  - ただし、dreamera,dreamerd等で区別する必要はある.

```rust
n abc049c(){
    let mut s: String = read();
    loop {
        let len = s.len();
        if len < 5 {
            println!("NO");
            break
        }
        if s == "erase" || s == "eraser" || s == "dream" || s == "dreamer" {
            println!("YES");
            break
        }
        if s.chars().nth(0).unwrap() == 'e' {
            if &s[0..6] == "eraser" {
                s = s[6..len].to_string();
            } else if &s[0..5] == "erase" {
                s = s[5..len].to_string();
            } else {
                println!("NO");
                break
            }
        } else if s.chars().nth(0).unwrap() == 'd' {
            if &s[0..7] == "dreamer" {
                if &s[0..8] == "dreamera" {
                    s = s[5..len].to_string();
                } else {
                    s = s[7..len].to_string();
                }
            } else if &s[0..5] == "dream" {
                s = s[5..len].to_string();
            } else {
                println!("NO");
                break
            }
        } else {
            println!("NO");
            break
        }
    }
}
```

~~脳直で書いたらひどいコードになってしまった...~~

いろいろ整理する方法がありますが,今回はアルゴリズムは気にしないことにしたので,妥協します.

### ABC086 C
移動時間が最短移動時間$＋2n(n >= 0)$であればよいので、
それに合わせて実装します.

```rust
fn abc086c(){
    let n: u32 = read();
    let input: Vec<Vec<i32>> = read_vec2(n);
    let mut old_x = 0;
    let mut old_y = 0;
    let mut old_t = 0;
    let mut flag = true;
    for inp_i in input {
        let (t, x, y) = (inp_i[0], inp_i[1], inp_i[2]);
        let diff = t - old_t - (x - old_x).abs() - (y - old_y).abs();
        if diff < 0 || diff % 2 == 1 {
            println!("No");
            flag = false;
            break;
        } else {
            old_t = t;
            old_x = x;
            old_y = y;
        }
    }
    if flag {
        println!("Yes");
    }
}
```

## 感想
なんとか解けました. 感想としては

- 標準入力は大変だなというお気持ち.
- 配列のindexがuintでないとエラーになるのはつらい.
- 常に型を意識するので、コードを書く時間はかかるが、変なミスは減りそう.
- 実行時エラーをきちんと読むのは大変そう(indexをミスって実行時エラーが何回か発生した)
- 知識がない状態で書いたので、他の人のコードを見た時の学びが多い.

なによりも

- 何よりも,慣れれば楽しそうでﾜｸﾜｸする.

## 参考

最後に今回いろいろ参考にした記事をあげておきます.

- [AtCoder に登録したら解くべき精選過去問 10 問を Rust で解いてみた](https://qiita.com/tubo28/items/e6076e9040da57368845)
- [Stringとstr入門](https://qiita.com/Mizunashi_Mana/items/db88cb0bff002abce1ae)
- [Rustの文字列調査](https://qiita.com/aflc/items/f2be832f9612064b12c6)
- [標準入力のマクロ](https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8)
- [Rust の標準入出力は(何も考えないで使うと)遅い](https://qiita.com/tubo28/items/41eeb0dfa1ebbccb1ddc)