はじめに
競技プログラミング、最初はC++でやってたんですよ。
でもある日、「Rustでも書けるよな？」と思って試してみたら...
型システムに救われまくった。
この記事では、Rustで競プロをやるメリットと、実際に助けられた場面を紹介します。
目次
Rustで競プロのメリット
1. コンパイルが通れば大体動く
これが一番大きい。
C++だと「コンパイル通ったのにWA（Wrong Answer）」「なぜかRE（Runtime Error）」がよくあるけど、Rustだとコンパイルエラーの段階でバグを潰せることが多い。
2. 整数オーバーフローを検知
fn main() {
let a: i32 = 2_000_000_000;
let b: i32 = 2_000_000_000;
let c = a + b; // デバッグビルドでパニック！
}
C++だと静かにオーバーフローするけど、Rustのデバッグビルドではパニックしてくれる。
3. Option/Resultで境界エラーを防止
fn main() {
let v = vec![1, 2, 3];
// C++だとv[10]で未定義動作
// Rustだとget(10)でNoneが返る
match v.get(10) {
Some(x) => println!("{}", x),
None => println!("範囲外！"),
}
}
4. 標準ライブラリが充実
use std::collections::{HashMap, HashSet, BinaryHeap, VecDeque};
// 全部標準で使える！
型システムに救われた場面
救われた1：符号なし整数の引き算
fn main() {
let a: usize = 3;
let b: usize = 5;
let c = a - b; // パニック！（デバッグビルド）
}
C++だと 3 - 5 が巨大な正の数になって、変な答えが出る。Rustだと教えてくれる。
対処法
fn main() {
let a: usize = 3;
let b: usize = 5;
// saturating_sub: 0未満にならない
let c = a.saturating_sub(b); // 0
// checked_sub: Optionで返す
let d = a.checked_sub(b); // None
// wrapping_sub: C++と同じ挙動
let e = a.wrapping_sub(b); // 18446744073709551614
}
救われた2：配列の境界チェック
AtCoderでよくある「DPテーブルにアクセス」：
fn main() {
let dp = vec![vec![0; 100]; 100];
// 添え字ミスってたら即パニック
// println!("{}", dp[100][0]); // パニック！
}
救われた3：文字列処理
fn main() {
let s = "あいう";
// C++だとs[0]で壊れた値が取れることも
// Rustだとchars()でちゃんとUnicode処理
for c in s.chars() {
println!("{}", c);
}
}
救われた4：型の不一致
fn gcd(a: i64, b: i64) -> i64 {
if b == 0 { a } else { gcd(b, a % b) }
}
fn main() {
let x: i32 = 12;
let y: i32 = 8;
// let g = gcd(x, y); // コンパイルエラー！型が違う
let g = gcd(x as i64, y as i64); // OK
}
意図しない型の混在をコンパイル時に検出できる。
競プロでよく使うRustテクニック
入力の受け取り
標準的な方法
use std::io::{self, BufRead};
fn main() {
let stdin = io::stdin();
let mut lines = stdin.lock().lines();
let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
let v: Vec<i64> = lines.next().unwrap().unwrap()
.split_whitespace()
.map(|s| s.parse().unwrap())
.collect();
}
proconio を使う（AtCoderで使用可能）
use proconio::input;
fn main() {
input! {
n: usize,
a: [i64; n],
}
println!("{}", a.iter().sum::<i64>());
}
proconio を使うと入力が超楽になる。AtCoderの環境に入ってるので使い放題。
よく使うイディオム
ソート
let mut v = vec![3, 1, 4, 1, 5];
v.sort(); // 昇順
v.sort_by(|a, b| b.cmp(a)); // 降順
最大値・最小値
let v = vec![3, 1, 4, 1, 5];
let max = *v.iter().max().unwrap();
let min = *v.iter().min().unwrap();
累積和
fn main() {
let a = vec![1, 2, 3, 4, 5];
let mut cumsum = vec![0; a.len() + 1];
for i in 0..a.len() {
cumsum[i + 1] = cumsum[i] + a[i];
}
// 区間 [l, r) の和
let l = 1;
let r = 4;
println!("{}", cumsum[r] - cumsum[l]); // 2+3+4 = 9
}
二分探索
fn main() {
let v = vec![1, 2, 4, 4, 4, 7, 9];
// 4以上の最初のインデックス
let lb = v.partition_point(|&x| x < 4); // 2
// 4より大きい最初のインデックス
let ub = v.partition_point(|&x| x <= 4); // 5
println!("4の個数: {}", ub - lb); // 3
}
mod計算
const MOD: i64 = 1_000_000_007;
fn main() {
let mut ans: i64 = 1;
for i in 1..=10 {
ans = (ans * i) % MOD;
}
println!("{}", ans);
}
グラフの表現
隣接リスト
fn main() {
let n = 5; // 頂点数
let edges = vec![(0, 1), (0, 2), (1, 3), (2, 4)];
let mut graph = vec![vec![]; n];
for (u, v) in edges {
graph[u].push(v);
graph[v].push(u); // 無向グラフの場合
}
}
BFS
use std::collections::VecDeque;
fn bfs(graph: &Vec<Vec<usize>>, start: usize) -> Vec<i32> {
let n = graph.len();
let mut dist = vec![-1; n];
let mut queue = VecDeque::new();
dist[start] = 0;
queue.push_back(start);
while let Some(v) = queue.pop_front() {
for &next in &graph[v] {
if dist[next] == -1 {
dist[next] = dist[v] + 1;
queue.push_back(next);
}
}
}
dist
}
ダイクストラ法
use std::collections::BinaryHeap;
use std::cmp::Reverse;
fn dijkstra(graph: &Vec<Vec<(usize, i64)>>, start: usize) -> Vec<i64> {
let n = graph.len();
let mut dist = vec![i64::MAX; n];
let mut heap = BinaryHeap::new();
dist[start] = 0;
heap.push(Reverse((0, start)));
while let Some(Reverse((d, v))) = heap.pop() {
if d > dist[v] { continue; }
for &(next, cost) in &graph[v] {
let new_dist = dist[v] + cost;
if new_dist < dist[next] {
dist[next] = new_dist;
heap.push(Reverse((new_dist, next)));
}
}
}
dist
}
C++と比較して
⭕ Rustが有利な点
| 項目 | Rust | C++ |
|---|---|---|
| コンパイル時チェック | 強い | 弱い |
| オーバーフロー検知 | デバッグビルドで検知 | 黙って壊れる |
| 境界チェック | 常にチェック | 未定義動作 |
| 標準ライブラリ | モダン | やや古い |
❌ Rustが不利な点
| 項目 | Rust | C++ |
|---|---|---|
| コンパイル時間 | 遅い | 速い |
| 実行速度 | 同程度 | 同程度 |
| 競プロ資料 | 少なめ | 豊富 |
| ライブラリ流用 | 面倒 | コピペでOK |
実行速度について
「Rustは遅い？」と思われがちだけど、リリースビルドならC++と同程度。
# デバッグビルド（境界チェック有り、オーバーフローチェック有り）
cargo build
# リリースビルド（最適化有り）
cargo build --release
AtCoderではリリースビルドで実行されるので、速度は問題ない。
よくあるミスと対策
ミス1：TLE（Time Limit Exceeded）
// ❌ 遅い
let mut result = String::new();
for i in 0..n {
result += &format!("{} ", a[i]); // 毎回メモリ確保
}
// ⭕ 速い
let result: Vec<String> = a.iter().map(|x| x.to_string()).collect();
println!("{}", result.join(" "));
ミス2：出力のフォーマット
// 小数点以下6桁
println!("{:.6}", 3.14159265358979); // 3.141593
// Yes/Noの出力
println!("{}", if condition { "Yes" } else { "No" });
ミス3：i32 vs i64
// ❌ i32だとオーバーフロー
let a: i32 = 1_000_000;
let b: i32 = 1_000_000;
let c = a * b; // オーバーフロー！
// ⭕ i64を使う
let a: i64 = 1_000_000;
let b: i64 = 1_000_000;
let c = a * b; // OK
競プロでは基本的に i64 を使っておけば安心。
まとめ
Rustで競プロのチェックリスト
-
proconioを使って入力を楽に -
整数は基本
i64を使う - イテレータを活用する
-
BinaryHeapは最大ヒープ（Reverseで最小ヒープに） - デバッグ時はオーバーフローに注意
今すぐできるアクション
- AtCoderで簡単な問題をRustで解いてみる
-
proconioの使い方を覚える - よく使うアルゴリズムをRustで書いておく
型システムに怒られるのは最初だけ。慣れると「コンパイル通ったらACできる」確率がめちゃくちゃ上がります。
Rustで競プロ、意外といいですよ。
この記事が役に立ったら、いいね・ストックしてもらえると嬉しいです！