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

今回のテーマ

• 基本文法 ( for / if / 入出力)

 

• 参照

 

• メモ化再帰

Option 型

HashMap / defaultdict / 辞書

次の記事：Pythonと比べて学ぶ競プロのためのRust Part2
次のテーマ：

累積和 / scan

オーバーフロー

all / any

lower_bound
座標圧縮

役に立つ記事

• RustCoder ―― AtCoder と Rust で始める競技プログラミング入門

 

• AtCoder 2020年言語アップデート以降の環境

 

Docker × VSCode × Rust な開発環境を３ステップで作る

ABC243 B – Hit and Blow

問題：

 

Python

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

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

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

問題：

 

Python

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

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

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

問題：

 

Python

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

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

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

問題：

 

Python

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

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

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

問題：

 

Python

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

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

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 を用いて同じように書くことができる。
// 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() とかく。