Pythonと比べて学ぶ競プロのためのRust

今までは Python で競技プログラミングをしていましたが、最近 Rust の勉強を始めました。同じように Python を書いたことがあり Rust へ入門しようと考えている人向けに AtCoder の過去問 (B~C) を両言語で解いてみます。


#### 今回のテーマ
- 基本文法 ( `for` / `if` / 入出力)
- 参照
- メモ化再帰
- `Option` 型
- `HashMap` / `defaultdict` / 辞書

> 次の記事：[Pythonと比べて学ぶ競プロのためのRust Part2](https://qiita.com/hinu1116/items/fe2c91a4570eb8243ce4)
> 次のテーマ：
> - 累積和 / `scan`
> - オーバーフロー
> - `all` / `any`
> - `lower_bound`
> - 座標圧縮  
  



#### 役に立つ記事

- [RustCoder ―― AtCoder と Rust で始める競技プログラミング入門](https://zenn.dev/toga/books/rust-atcoder)
- [AtCoder 2020年言語アップデート以降の環境](https://github.com/rust-lang-ja/atcoder-rust-resources/wiki/2020-Update)
- [Docker × VSCode × Rust な開発環境を３ステップで作る](https://qiita.com/schrosis/items/1d99b68ae00d3cdbf9e1)



#### ABC243 B - Hit and Blow

問題：

https://atcoder.jp/contests/abc243/tasks/abc243_b

##### Python

提出：https://atcoder.jp/contests/abc243/submissions/31304249

```python
I = lambda:int(input())
LI = lambda:list(map(int,input().split()))

n = I()
al = LI()
bl = LI()

ans1,ans2 = 0,0
for i in range(n):
    for j in range(n):
        if al[i] == bl[j]:
            ans1 += (i==j)
            ans2 += (i!=j)
print(ans1)
print(ans2)
```

##### Rust

提出：https://atcoder.jp/contests/abc243/submissions/31281681

```rust
fn main() {
    proconio::input! {
        n:usize,al:[usize;n],bl:[usize;n]
    }
    let mut ans1 = 0;
    let mut ans2 = 0;
    for i in 0..n {
        for j in 0..n {
            if al[i] == bl[j] {
                ans1 += (i == j) as usize;
                ans2 += (i != j) as usize;
            }
        }
    }
    println!("{}", ans1);
    println!("{}", ans2);
}
```

- `usize` は非負整数を扱う型で、配列やベクタのインデックスとして用いる場合は `usize` 型でなければならない。
- 数値型から数値型へのキャストを行う場合は `as` を使う。
- Rust では変数宣言時に `mut` をつけると可変な変数となり、そうでなければ不変な変数(定数)となる。
- 配列を出力するときは `println!("{:?}",lis);` と書く。



#### ABC088 B - Card Game for Two

問題：

https://atcoder.jp/contests/abs/tasks/abc088_b

##### Python

提出：https://atcoder.jp/contests/abs/submissions/31303893

```python
I = lambda:int(input())
LI = lambda:list(map(int,input().split()))

n = I()
al = sorted(LI(),key=lambda a:-a)

ans = 0
for i,a in enumerate(al):
    ans += a if i%2 == 0 else -a
print(ans)
```

##### Rust 

提出：https://atcoder.jp/contests/abs/submissions/31096051

```rust
fn main() {
	proconio::input! {
        n:i32,mut al:[i32;n],
    }

    let mut ans = 0;
    al.sort_by_key(|x| -x);
    for (i, a) in al.iter().enumerate() {
        ans += if i % 2 == 0 { *a } else { -*a }
    }
    println!("{}", ans)
}
```

- ループ中の `a` の型は参照 (`&i32`) であるため、値を表すように `*a` とする必要がある。`*` は参照に対する値を、`&` は値に対する参照を返す。
- 配列をそのままループに用いると所有権が移動し、以降その配列を利用できなくなる。
    - `.iter()` を付けて参照のループにすれば所有権は移動しない。
    - `.into_iter()` は実際の値でイテレータ化するので所有権が移動する。
    - `.iter_mut()` は `&mut` でイテレータ化するので可変かつ所有権が移動しない



#### ABC247 C - 1 2 1 3 1 2 1

問題：

https://atcoder.jp/contests/abc247/tasks/abc247_c

##### Python

提出：https://atcoder.jp/contests/abc247/submissions/30855957

```python
I = lambda:int(input())
n = I()

memo = [[] for _ in range(20)]
memo[1] = [1]
def g(m):
    if not memo[m]:
        memo[m] = calc(m-1) + [m] + calc(m-1)
    return memo[m]

print(*calc(N))
```

##### Rust

提出：https://atcoder.jp/contests/abc247/submissions/31305129

```rust
fn main() {
    proconio::input! {
        n:usize
    }
    let mut memo: Vec<String> = vec!["".to_string(); 20];
    memo[1] = "1".to_string();
    println!("{}", g(n, &mut memo));
}

fn g(m: usize, memo: &mut Vec<String>) -> String {
    if memo[m] == *"" {
        memo[m] = format!("{} {} {}", g(m - 1, memo), m, g(m - 1, memo));
    }
    memo[m].clone()
}
```

- メモ化再帰関数を実装する場合、メモ用の変数に `&mut` を指定する。 `&mut` は値を書き込むことができる参照になる。
- 文字列を扱う型は `char` , `String` , `&str` などがある。
- Rust では `return` は関数の途中で値を返して処理を中断するときに用いる。そうでない場合は単に `;` をつけずに値を書けばよい。



#### ABC081 B - Shift only

問題：

https://atcoder.jp/contests/abs/tasks/abc081_b

##### Python

提出：https://atcoder.jp/contests/abs/submissions/31305806

```python
I = lambda:int(input())
LI = lambda:list(map(int,input().split()))

n = I()
al = LI()
def g(x):
    return 0 if x%2 else g(x//2) + 1
print(min(g(a) for a in A))
```

##### Rust

提出：https://atcoder.jp/contests/abs/submissions/31305392

```rust
fn main() {
    proconio::input! {
        n:usize,al:[usize;n]
    }
    println!("{}", al.iter().map(|&x| g(x)).min().unwrap());
}
fn g(m: usize) -> usize {
    if m % 2 == 0 { g(m / 2) + 1 } else { 0 } 
}
```

- Rust には安全に値を取り出すために `Option` 型が用意され、値を取得できない可能性がある関数は `Option` 型を返すようになっている。`min` の返り値も `Option` 型であるため、値を取り出すためには `unwrap` や `unwrap_or` を用いる必要がある。
- 今回は関数 `g` を定義したが、例えば `.map(|&x| (x&(-x)).trailing_zeros())` と書く方法もある。



#### ABC243 C - Collision 2

問題：

https://atcoder.jp/contests/abc243/tasks/abc243_c

##### Python

提出：https://atcoder.jp/contests/abc243/submissions/31301450

```python
I=lambda:int(input())
LI=lambda:list(map(int,input().split()))
from collections import defaultdict as dd
import re

n = I()
yl = dd(list)
xy = [LI() for _ in [0]*N]
s = input()

for i in range(N):
    x,y=xy[i]
    c=s[i]
    yl[y].append((x,c))
    
flg=True
for k,v in yl.items():
    check = ["L"] + [p[1] for p in sorted(v,key=lambda x:x[0])] + ["R"]
    check = "".join(check)
    flg = flg and bool(re.fullmatch(r"^(L+R+)$",check))
    
print(['Yes','No'][flg])
```

##### Rust

提出：https://atcoder.jp/contests/abc243/submissions/31302909

```rust
use itertools::sorted;
use std::collections::HashMap;
type VS = Vec<String>;

fn main() {
    proconio::input! {
        n:usize,
        mut xy:[(usize,usize);n],
        s:String
    }

    let mut yl: HashMap<usize, Vec<(usize, String)>> = HashMap::new();
    for ((x, y), c) in xy.iter().zip(s.chars()) {
        (*yl.entry(*y).or_insert(vec![])).push((*x, c.to_string()));
    }

    let mut flg = true;
    for (_, v) in yl.iter() {
        let mut check = vec![
            vec!["L".to_string()],
            sorted(v).map(|x| (*x).clone().1).collect::<VS>(),
            vec!["R".to_string()],
        ]
        .concat();
        check.dedup();
        flg &= check == vec!["L".to_string(), "R".to_string()];
    }

    println!("{}", if !flg { "Yes" } else { "No" })
}
```

- $y$ の値ごとに分割して $x$ 座標と対応する向き `c` のペアを配列化し、$x$ 座標でソートしたときの文字が L...LR...R のようになっているかどうかを確認する。
- ベクタの先頭への要素追加は遅いが、今回は間に合うので使用した。

- Python の `defaultdict` は存在しないキーを指定したときの初期値を設定できる辞書。Rust では `HashMap` を用いて同じように書くことができる。

  ```rust
  // dic[key].append(val)
  (*dic.entry(key).or_insert(vec![])).push(val);
  // dic[key]+=1;
  *dic.entry(key).or_insert(0)+=1;
  ```

- `sorted` は `itertools` に含まれるメソッド。AtCoder の Rust では `itertools = 0.9.0` が使える。

- `.dedup()` は隣接する同じ要素を一つにまとめた配列を作る。

- vec1 + vec2 はRustでは `vec![vec1,vec2].concat()` とかく。