LoginSignup
10
3

More than 1 year has passed since last update.

@hossie(ほっしー)

Rust の競プロで変数をどうするか問題

Posted at

はじめに

Rust で 1年ほど競技プログラミングをしています。AtCoder 緑色です。

競技プログラミングは時間内にどれだけ解けるかが正義です。普段のプログラミングと違い、読みやすさやメンテナンス性はあまり重視しません。たとえばマクロやグローバル変数は普段のプログラミングでは避けられがちですが、C++ 競技プログラミングでは良く使います。

しかし Rust の場合、安全性重視の言語ということで、C++ ほど自由には書けません。その制限の中で、素早く解きたいです。

本記事では変数に絞って、私はこのように書いていますという紹介をします。

想定読者

競技プログラミングで以下のようなコードを書く人向けです:

  • 重視すること
    • Rust
    • linter, formater 通過
    • その上で実装速度重視
    • 一般的な crate のみ使う
      • AtCoder で標準で使える proconio, itertools, petgraph は良いとする
  • 重視しないこと
    • コードの再利用性、関数化
    • 変数の名前付け

コードの書き方に正解はありません。このような書き方もあります、という記事です。

TL;DR

  • 標準入力を受ける変数
    • proconio で読み取る
    • 変数名は問題文と揃えた小文字にする
      • 配列の場合、タプルの配列の場合も同じ
    • 配列のインデックスとする入力値の扱い方を揃える
  • 一時変数
    • スコープ内の変数の個数を少なくする
      • ライブラリーにある機能をそのまま利用する
      • シャドーイングを積極的に使う
    • mut は控えめに
    • スコープの長い変数は、構造を示す名前を付ける
    • 出力行にロジックを書かない
  • おまけ
    • usize 以外の数値について
    • vec![] か Vec::with_capacity() か
    • windows() と tuple_windows()
    • タプルで十分なときはタプルを使う

標準入力を受ける変数

proconio で読み取る

次の問題 A を考えます。

問題

$N$ 月の次の月を出力してください

制約

  • $1 \le N \le 12$

入力

$N$

入力例

12

出力例

1

Rust で標準入力を読み込むのは手間です。ここに時間をかけるのは勿体ないです。

AtCoder では proconio を使うのをお勧めします。

proconio を使うと、次のように書けます。

a1.rs
use proconio::input;

fn main() {
    input! {
        n: usize,
    }
    let result = n % 12 + 1;
    println!("{}", result);
}

proconio なしだと、1つの整数を読み込むだけで「文字列を読み込んで、空白でトリムして、別の型に変換して」という感じになります。お勧めしません。

a2.rs
use std::io::stdin;

fn main() {
    let n: usize = {
        let mut s = String::new();
        let _ = stdin().read_line(&mut s);
        s.trim_end().parse().unwrap()
    };
    let result = n % 12 + 1;
    println!("{}", result);
}

変数名は問題文と揃えた小文字にする

先ほどのコードは、問題 A の入力 $N$ を小文字の変数 n で受けていました。

Rust では大文字開始の N はふつう定数を示します。次のように書くと、名前付けが良くないという警告が出ます。

a3.rs
use proconio::input;

fn main() {
    input! {
        N: usize,
    }
    let result = N % 12 + 1;
    println!("{}", result);
}

> cargo build
   Compiling work v0.1.0
warning: variable `N` should have a snake case name                                           
 --> src/main.rs:5:9
  |
5 |         N: usize,
  |         ^ help: convert the identifier to snake case: `n`
  |
  = note: `#[warn(non_snake_case)]` on by default

いくら解く速度優先でも、警告は良くないです。小文字にします。

たまに $T$ と $t$ 両方を入力とするような問題も出ます。このときはどちらかの変数名を避けます。

配列の場合

配列の場合も同じように、問題文と同じ名前を小文字で付けます。 $A_1,\ A_2,\ ...\ A_N$ をすべて1つの配列 a で受けます。

次の問題 B を考えます。

問題

$A_1,\ A_2,\ ...\ A_N$ の中でもっとも大きな数を出力してください

制約

  • $1 \le N \le 100$
  • $0 \le A_i \le 100$

入力

$N$
$A_1\ A_2\ ...\ A_N$

入力例

7
3 1 4 1 5 9 2

出力例

9

入力の配列を let a = vec![3, 1, 4, 1, 5, 9, 2]; としてまとめて受けます。これを順に処理します。

b1.rs
use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [usize; n]
    }
    let mut result = 0;
    for &x in &a {
        result = result.max(x);
    }
    println!("{}", result);
}

このコードの中には最初の入力読み取り以外で n が現れません。その場合は次のように省略して書くのも良いです。

b2.rs
    input! {
        a: [usize]
    }

この問題はもっと短く解けます。後半の一時変数の方でまた扱います。

タプルの配列の場合

入力が $W_1,\ H_1,\ W_2,\ H_2\ ...\ W_N,\ H_N$ のように、複数の値が同じ数だけ並ぶことがあります。これを受けるときは wh のように名前付けします。

次の問題 C を考えます。

問題

幅 $W_i$、高さ $H_i$ の長方形があります。面積の最大値を出力してください。

制約

  • $1 \le N \le 100$
  • $0 \le W_i \le 100$
  • $0 \le H_i \le 100$

入力

$N$
$W_1\ H_1$
$W_2\ H_2$
$:$
$W_N\ H_N$

入力例

4
3 1
4 1
5 9
2 6

出力例

45

入力の配列を let wh = vec![(3, 1), (4, 1), (5, 9), (2, 6)]; としてまとめて受けます。これを順に処理します。

c1.rs
use proconio::input;

fn main() {
    input! {
        n: usize,
        wh: [(usize, usize); n]
    }
    let mut result = 0;
    for &(w, h) in &wh {
        result = result.max(w * h);
    }
    println!("{}", result);
}

for 文で wh を回すときに、中身を w, h という変数で受けます。 この方針だと名前付けに迷うことが少なくなります。

配列のインデックスとする入力値の扱い方を揃える

次の問題 D を考えます。

問題

$A_{A_i}$ を返してください。

制約

  • $1 \le N \le 100$
  • $1 \le A_i \le N$

入力

$N$
$A_1\ A_2\ ... A_N$

入力例

6
1 3 2 5 6 4

出力例

1
2
3
6
4
5

プログラミング言語では、配列の先頭が 0 とすることが多いです。 Rust もそうです。

競技プログラミングの問題では $A_1$ のように、配列の先頭が 1 となりやすいです。単純に読み取ると、問題文と変数の持ち方がずれます。これは混乱します。

i 0 1 2 3 4 5 6
$A_i$ - 1 3 2 5 6 4
a[i] 1 3 2 5 6 4

どちらの世界に揃えるか、方法はいろいろあります。実装途中に「このコードは配列の先頭どちら？」と迷わないように、いつも同じように書くことをお勧めです。

A. 配列の先頭にダミー要素を入れる

d1.rs
use proconio::input;

fn main() {
    input! {
        n: usize,
        mut a: [usize; n],
    }
    a.insert(0, 0); // ダミーの値を先頭に挿入
    for i in 1..=n {
        println!("{}", a[a[i]]);
    }
}
i 0 1 2 3 4 5 6
$A_i$ - 1 3 2 5 6 4
a[i] - 1 3 2 5 6 4
a[a[i]] - 1 2 3 6 4 5

配列の先頭に a.insert(0, 0); のようにダミー要素を入れると、問題文と同じ 1 開始になります。

B. 配列にアクセスするときにインデックスを 1減らす

d2.rs
use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }
    for i in 0..n {
        println!("{}", a[a[i] - 1]);
    }
}
i 0 1 2 3 4 5 6
$A_i$ - 1 3 2 5 6 4
$A_{i-1}$ 1 3 2 5 6 4
a[i] 1 3 2 5 6 4
a[a[i] - 1] 1 2 3 6 4 5

こちらでも良いです。 - 1 を挟む場所を間違えないように注意です。

C. 入力時にインデックスを 1減らす

d3.rs
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        a: [Usize1; n],
    }
    for i in 0..n {
        println!("{}", a[a[i]] + 1);
    }
}
i 0 1 2 3 4 5 6
$A_i$ - 1 3 2 5 6 4
$A_{i-1}-1$ 0 2 1 4 5 3 -
a[i] 0 2 1 4 5 3
a[a[i]] 0 1 2 5 3 4
a[a[i]] + 1 1 2 3 6 4 5

インデックスを Rust で扱いやすい 0開始に、読み込み時に変更しておきます。 proconio にはそのために 1減らして読み込むマーカー Usize1 があります。

配列のインデックス操作が不要です。うっかり範囲外にアクセスすることも少ないです。 n も消して、スッキリ短く書けます。

d4.rs
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        a: [Usize1],
    }
    for &x in &a {
        println!("{}", a[x] + 1);
    }
}

もちろん、出力する場合はどこかで + 1 が必要です。

私は C. の方針で書くことが多いです。DP などで $A_0$ も使いたいときに、最初の方針のように挿入することもあります。

一時変数

スコープ内の変数の個数を少なくする

変数の数が多いと、どの変数を使ってよいか混乱します。同じスコープに出てくる変数の数を減らしたいです。とくに可変の変数 1 mut を減らしたいです。

ライブラリーにある機能をそのまま利用する

自分でコードを書くから変数を使います。すでにライブラリーにあるならただ呼べばいいです。バグも抑えられます。

問題 B 配列の最大値を求めるとき、以下のように書きました。可変の変数 result を手続き的に更新します。

b1.rs
use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [usize; n]
    }
    let mut result = 0;
    for &x in &a {
        result = result.max(x);
    }
    println!("{}", result);
}

配列のように連続した値を、イテレーターを使って順に調べ、その中の最大値を返す関数 iter().max() が標準機能としてあります。こちらを使うと一発で答えが求まります。

b3.rs
    let result = *a.iter().max().unwrap();
    println!("{}", result);

iter().max() は、 Option<usize> でくるんだ値を返します。最大値そのままではありません。配列が空のときに、空と分かるためです。 値を取り出したいときには unwrap() します。

unwrap() は panic! の原因になり一般には怖いです。しかし競技プログラミングの文脈では、入力の配列が空でないことを制約で保障していることが多いですので、えいやっと使って良いと思っています。

気になるなら unwrap() 以外の方法ではがします。

b4.rs
    if let Some(&result) = a.iter().max() {
        println!("{}", result);
    }

シャドーイングを積極的に使う

最大値を求める問題の解答を、次のようにも書けます。

b5.rs
use proconio::input;

fn main() {
    input! {
        a: [usize]
    }
    let mut result = 0;
    for &a in &a {
        result = result.max(a); // この a は配列の各要素
    }
    println!("{}", result);
}

for &a in &a という書き方で、$A_i$ の中身を取り出しています。右の &a は配列全体を、左の &a と {} 内は a[0], a[1] など配列の中身になります。シャドーイングです。

Rust に慣れていないと一見気持ち悪く、同名の a がどちらを指しているのか分かりにくいです。しかし、慣れるととても便利です。

  • ループの中で参照できる変数が a: usize, mut result: usize の 2つだけと少ない
  • 間違って配列の別の値にアクセスすることがない
  • もし配列にアクセスしたくなったとしても、型が異なるのですぐ直せる
  • 配列と中身の変数名をそれぞれ考えなくて良い

mut は控えめに

Rust では可変変数を使おうとすると、すぐに所有権に悩まされます。ほかの言語ならさくっと書けるところを、コンパイルエラーと格闘して時間を奪われかねません。控えめにします。

わたしは VS Code で mut に下線を引く設定にしています。とても目立ちますが、その分ドキッとします。例えば先日の AtCoder ABC286-G のグラフを図示してみる - Qiita より:

image.png

edges を更新していて、あとは参照っぽいことが分かります。

uf (UnionFind) はだいたい最初に作ったらそのあとは使うだけです。可変のままだと間違って更新してしまいかねません。 let uf = uf; として値を凍結すると安心です。下線も消えます。

スコープの長い変数は、構造を示す名前を付ける

ちょうど上の uf のように、構造を示す名前を付けます。たとえば次のような名前をよく付けます。

変数名 型 意味
a [], Vec array
v Vec vector
s, set HashSet, BTreeSet set
m, map HashMap, BTreeMap map
g, graph Vec<Vec> graph
queue VecDeque queue
stack Vec stack
heap BinaryHeap binary heap (priority queue)
uf UnionFind UnionFind (disjoint set)

アルゴリズムを示す名前を付けることもあります。

変数名 型 意味
dp Vec DP
cum Vec DP 累積和
imos Vec DP いもす法

普通のプログラミングでは名前重要です。でも競技プログラミングでは名前付けに時間をかけるのは勿体ないです。

スコープの短い変数の名前はなんでも良いです。for &a in &a { /* 1行 */ } も for &x in &a { /* 1行 */ } も周辺を見れば分かります。

出力行にロジックを書かない

println!("{}", a.iter().max().unwrap()); のように出力行にロジックを書くのは避けます。 yes や result という変数に結果を入れます。

答えが合わないときにデバッグ実行しにくいためです。

  • 出力行にロジックを書かない
  • その他
    • usize 以外の型
    • vec![] か Vec::with_capacity() か

おまけ

うまくまとめられなかったおまけです。

usize 以外の数値について

私は usize 以外あまり使いません。

  • usize
    • 非負整数なんでも使えます。配列のインデックスにも使えます。万能。
    • 64bit 環境だと u64 相当です。オーバーフローの恐れもあまりありません。
      • 32bit 環境だと u32 相当ですが、そんな環境はレアです。
  • i64
    • 負の計算が現れるときはこちら。
  • u32, i32
    • 明らかに 64bit が過剰なときに、消費メモリーを減らす意味で使うことはあります。
    • しかし入出力が 32bit の範囲でも、途中計算が 64bit になることはありますので、要注意です。
    • メモリーが潤沢にあるなら、usize, i64 で十分でしょう。
  • u128
    • 64bit におさまらない数を扱う際に使います。レアです。
  • f64
    • Rust では浮動小数点の比較にひと手間かかります。あまり使いたくないです。

vec![] か Vec::with_capacity() か

次の問題 E を考えます。

問題

$1$ から $N$ までをスペースで区切って順に出力してください。

制約

  • $1 \le N \le 12$

入力

$N$

入力例

5

出力例

1 2 3 4 5

要素数 n の配列を用意する際に、「ダミーの値が詰まった配列にする」か、「領域だけ確保して中身が空の配列にする」かの2通りがあります。

e1.rs
use itertools::Itertools;
use proconio::input;

fn main() {
    input! {
        n: usize,
    }
    let mut a = vec![0; n]; // ダミーの値が詰まった配列
    for i in 0..n {
        a[i] = i + 1;
    }
    let result = a.iter().join(" ");
    println!("{}", result);
}
e2.rs
use itertools::Itertools;
use proconio::input;

fn main() {
    input! {
        n: usize,
    }
    let mut a = Vec::with_capacity(n); // 領域だけ確保して中身が空の配列
    for i in 1..=n {
        a.push(i);
    }
    let result = a.iter().join(" ");
    println!("{}", result);
}

どちらでも良いです。

push だとインデックスを使わずに済みます。扱いやすそうです。しかし DP で配列の末尾の値を使いつつ次の値を push しようとすると所有権の問題にハマったりもします。ケースバイケースです。

スペース区切りの出力には itertools を使いました。

windows() と tuple_windows()

次の問題 F を考えます。

問題

$A_i \times A_{i+1}$ の最大値を求めてください。

制約

  • $2 \le N \le 100$
  • $1 \le A_i \le 100$

入力

$N$

入力例

7
3 1 4 1 5 9 2

出力例

45

インデックスを使う方法です。ループの範囲指定に注意です。うっかり i + 1 が配列の範囲を超えると panic します。

f1.rs
use proconio::input;

fn main() {
    input! {
        a: [usize],
    }
    let mut result = 0;
    for i in 0..(a.len() - 1) {
        result = result.max(a[i] * a[i + 1]);
    }
    println!("{}", result);
}

windows() で隣り合う 2つの値をスライス w で得られます。配列の範囲を超える心配が減ります。

型からはスライス内の要素数は分かりません。でもこれくらい短いスコープなら大丈夫でしょう。

f2.rs
fn main() {
    input! {
        a: [usize],
    }
    let result = a.windows(2).map(|w| w[0] * w[1]).max().unwrap();
    println!("{}", result);
}

itertools の tuple_windows() を使うとタプルで値を得られます。配列の範囲を超える心配が完全になくなります。ハマるといい感じです。今回の例くらい短いと windows() で十分ですが。

f3.rs
use itertools::Itertools;
use proconio::input;

fn main() {
    input! {
        a: [usize],
    }
    let result = a.iter().tuple_windows().map(|(w0, w1)| w0 * w1).max().unwrap();
    println!("{}", result);
}

タプルで十分なときはタプルを使う

グラフを辿る問題では、「距離」「価値」など複数の値を使って幅優先探索したくなることがあります。たとえば ABC286-E がそうでした。

「距離」「価値」ということをコード上で示したいとき、ふつうは構造体を作成し、優先度付きキューで使える比較関数を設定するはずです。

しかし競技プログラミングでは面倒です。タプル (Reverse(0), 0, u) のように書けば十分です。どういう順番に並んでいるかコメントをつけておけば良いでしょう。

abc286-e-sub.rs
let mut visited = vec![false; n];
let mut heap = BinaryHeap::new();
heap.push((Reverse(0), 0, u)); // step, value, pos
while let Some((Reverse(step), value, v)) = heap.pop() {
    if visited[v] {
        continue;
    }
    let value = value + a[v];
    results[u][v] = (step, value);
    visited[v] = true;
    for (i, &c) in s[v].iter().enumerate() {
        if c == 'Y' && !visited[i] {
            heap.push((Reverse(step + 1), value, i));
        }
    }
}

おまけのおまけです:

  • let mut heap = BinaryHeap::new() のように、コレクションの中に詰める型は変数定義時点では書かないことが多いです。コンパイルエラーに任せます。
  • 優先度付きヒープの優先度が小さな値ほど高いとするときは、 Reverse(step) のようにします。
    • i64 にして負数にしても良いです。そのときは反転したことを忘れないように注意です。
    • Reverse() していれば、はがしたときに正の優先度になることが明確です。
  • 配列のインデックスと値を両方欲しいときは for (i, &c) in s[v].iter().enumerate() のようによく書きます。
    • for i in 0..s[v].len() { let c = s[v][i]; } という形の方が見慣れているかもしれません。
    • でも配列のインデックス操作はちょっとミスするとすぐ panic しますから、できるだけ言語機能にお任せしたいです。

最後に

このような書き方もあります、という紹介記事でした。

最後にガイドブックを紹介して、本記事を終了とします。

  1. Rust では基本的に不変の変数を使います。 変数と可変性 - The Rust Programming Language 日本語版 ↩

10
3
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
Sign upLogin
10
3