Ccmmutty logo
Commutty IT
・2 min read

RustとAtCoderを勉強する(typical90_j)

AtCoderRust
https://cdn.magicode.io/media/notebox/blob_vFDPXUe

はじめに

AtCoder の問題を Rust で解いていきます。AtCoder も Rust も初心者ですが、温かい目で成長を見守っていただけるとありがたいです。
今回は、競プロ典型90問の010 - Score Sum Queries（★2）を解きました。

提出コード

クロージャ を意識して利用してみました。
rust
use proconio::{derive_readable, input};

#[derive_readable]
struct Student {
    class: usize,
    point: usize,
}

fn main() {
    input! {
        n: usize,
        student: [Student; n],
    }
    let acc_class = |class| {
        let mut acc = student
            .iter()
            .scan(0, |state, s| {
                if s.class == class {
                    *state += s.point;
                }
                Some(*state)
            })
            .collect::<Vec<usize>>();
        acc.insert(0, 0);
        acc
    };
    let acc_class_1 = acc_class(1);
    let acc_class_2 = acc_class(2);

    input! {
        q: usize,
    }
    for _ in 0..q {
        input! {l: usize, r: usize}
        let a = acc_class_1[r] - acc_class_1[l - 1];
        let b = acc_class_2[r] - acc_class_2[l - 1];
        println!("{} {}", a, b);
    }
}

解説

この問題のキーワードは 累積和 です。 累積和 は以下のコードのように scan() で求めることが出来ます。
rust
let acc: Vec<usize> = (1..=5)
    .scan(0, |state, x| {
        *state += x;
        Some(*state)
    })
    .collect();
println!("{:?}", acc);
[1, 3, 6, 10, 15]

まとめ

  • 累積和は scan() で求める
  • クロージャをうまく使えるようになりたい

Discussion

コメントにはログインが必要です。