今までは 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 な開発環境を3ステップで作る
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()
とかく。