Rustの勉強ログ 競プロ典型90問をRustで説いてみる 010 Score Sum Queries

目的

知人からRustを勧められたため、試しに競プロの問題をRustで解いてみた。

背景(著者のスペック)

AtCoderは主にPythonを使用している。最高レーティングは1200強。
一応昔Cも触っていたので、ポインタの考え方や静的型付けはある程度は理解しているつもり。

Rustを触ってみることが主目的なので、自分の実力で余裕を持って解ける問題(ABC換算で300点)をまず解いてみる。
今回はタイトルの通り、010に挑戦。

010の考え方

まず、NとQのサイズがともに10 ^ 5のため、常識的な時間(Pythonでも解ける時間)でときたい場合、
O(N)時間の処理とO(Q)時間の処理で対応する必要が出てくる。

この場合、1組と2組の最初のX人の点数の合計値を出し(O(N))、適切に差分を取って(Qのそれぞれで定数時間→O(Q))答えを出せば良い。

Pythonならこうなるかな。(先にRustで書いてからpythonを書いている)

N = int(input())

student_list = [tuple(map(int, input().split())) for _ in range(N)]

class1_sum = [0] * (N + 1)
class2_sum = [0] * (N + 1)

for i, student in enumerate(student_list):
    class1_sum[i + 1] = class1_sum[i]
    class2_sum[i + 1] = class2_sum[i]
    if student[0] == 1:
        class1_sum[i + 1] += student[1]
    else:
        class2_sum[i + 1] += student[1]

Q = int(input())

for _ in range(Q):
    L, R = map(int, input().split())
    print(f"{class1_sum[R] - class1_sum[L - 1]} {class2_sum[R] - class2_sum[L - 1]}")

Rustで書いた場合

内包表記と変数の宣言の文だけ長いな。
下記折りたたんだコードの引っかかりポイントを順番に書いていくことにする。

長いので折りたたみ

use std::io;

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let n : i32 = input.trim().parse().expect("入力エラー");

    // let point_list: [i32; N]はコンパイルエラー(E0435)。配列は定数(コンパイル時に決まっている数字)でなければいけない
    // ついでにベクタを後で操作するのでmut付きの宣言が必要。
    let mut point_list: Vec<i32> = Vec::new();
    let mut class_list: Vec<i32> = Vec::new();

    // _はpythonと同じ使い方ができる、が、多分変数扱いにはなっていない。
    // iをループ変数にしたら警告が出た
    for _ in 0..n{
        // 上の方ですでに所有権を他の関数に渡しているし、同じ変数である必要がないため、もう一度inputを宣言する。
        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        let cells = split_i32(input);

        class_list.push(cells.0);
        point_list.push(cells.1);
    }

    let mut class1_point_sum: Vec<i32> = Vec::new();
    let mut class2_point_sum: Vec<i32> = Vec::new();

    class1_point_sum.push(0);
    class2_point_sum.push(0);

    // usize：このコンピュータで使えるポインタにサイズを合わせた整数型。
    // キャストしなければ「スライスのインデクサにはusizeを使って」とエラーを出される(E0277)
    for i in 0 .. n as usize{
        let mut class1_sum = class1_point_sum[i];
        let mut class2_sum = class2_point_sum[i];

        if class_list[i] == 1 {
            class1_sum = class1_sum + point_list[i];
        }else{
            class2_sum = class2_sum + point_list[i];
        }

        class1_point_sum.push(class1_sum);
        class2_point_sum.push(class2_sum);
    }

    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let q : i32 = input.trim().parse().expect("入力エラー");

    for _ in 0 .. q{
        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        let cells = split_i32(input);

        println!("{} {}", class1_point_sum[cells.1 as usize] - class1_point_sum[cells.0 as usize - 1], 
            class2_point_sum[cells.1 as usize] - class2_point_sum[cells.0 as usize - 1]);
    }

}

fn split_i32(input_str: String) -> (i32, i32){
    let splitted: Vec<&str> = input_str.trim().split(" ").collect();
    let mut parsed: Vec<i32> = Vec::new();

    for s in splitted{
        parsed.push(s.parse().unwrap_or(-1));
    }

    (parsed[0], parsed[1])
}

Rust引っかかりポイント

エラーが起きる可能性がある場所は必ず対処

Pythonだったらint(input())で済むが、厳密に言うと標準入力から値を取得した時とキャストを行ったときに、
エラーが出る可能性がある。
「AtCoderだからきちんとした入力は保証されている」といった甘えは使えない。

(甘えがきくPythonは多人数で開発したときにヤバいことになることがあるため、個人的にはRustのメリットの一つだと思う。)

    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let n : i32 = input.trim().parse().expect("入力エラー");

配列は固定長

固定長かどうかは、コンパイル時に置き換えられるかどうかで判別しているようだ。

    // let point_list: [i32; N]はコンパイルエラー(E0435)。配列は定数(コンパイル時に決まっている数字)でなければいけない
    // ついでにベクタを後で操作するのでmut付きの宣言が必要。
    let mut point_list: Vec<i32> = Vec::new();

所有権を渡した変数は変更する必要があるかを確認

下記ループの内部では、inputを再度宣言し直さなければコンパイルエラーが発生する。
前のループのinputと今のループのinputは関係があるだろうか。今回は関係ないから毎回定義しよう。

    // _はpythonと同じ使い方ができる、が、多分変数扱いにはなっていない。
    // iをループ変数にしたら警告が出た
    for _ in 0..n{
        // 上の方ですでに所有権を他の関数に渡しているし、同じ変数である必要がないため、もう一度inputを宣言する。
        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        let cells = split_i32(input);

        class_list.push(cells.0);
        point_list.push(cells.1);
    }

ポインタのサイズは環境依存

昔は32bitCPUだったのでrustで言うならi32型をポインタとして使えた。
なら今は？よくわからないからusizeを使おう、ということらしい。

    // usize：このコンピュータで使えるポインタにサイズを合わせた整数型。
    // キャストしなければ「スライスのインデクサにはusizeを使って」とエラーを出される(E0277)
    for i in 0 .. n as usize{
        let mut class1_sum = class1_point_sum[i];
        let mut class2_sum = class2_point_sum[i];

        if class_list[i] == 1 {
            class1_sum = class1_sum + point_list[i];
        }else{
            class2_sum = class2_sum + point_list[i];
        }

        class1_point_sum.push(class1_sum);
        class2_point_sum.push(class2_sum);
    }

感想

確かにエラーコードを読まなければいけない分とっつきづらさはあるものの、
バグを出さないようにするという観点では素晴らしいプログラミング言語だと思う。
標準入出力関連を自分にとってもう少しとっつきやすくできればAtCoderでも使えそうだ。