5
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

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

Last updated at Posted at 2022-04-27

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

今回のテーマ

  • 基本文法 ( for / if / 入出力)
  • 参照
  • メモ化再帰
  • Option
  • HashMap / defaultdict / 辞書

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

  • 累積和 / scan
  • オーバーフロー
  • all / any
  • lower_bound
  • 座標圧縮

役に立つ記事

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 型であるため、値を取り出すためには unwrapunwrap_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;
    
  • sorteditertools に含まれるメソッド。AtCoder の Rust では itertools = 0.9.0 が使える。

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

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

5
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?