競プロ典型90問をRustで解いていこう（累積和）2日目

2022-03-07

はじめに

子供が40度の熱を出して金土日と気が気ではなかったのですが落ち着いたようで安心しました。長男、次男とどちらも日曜日の夜中に高熱になるので近所の大きな救急病院に連れていくことになるとは…。願わくば、大きな病気になることなく天寿を全うするような人生を送ってほしい。

何はともあれ、今日の問題を解いていきましょう。

本日の問題

競プロ典型90問をRustで解いていこう（準備）0日目

今日は上の記事から2問目である、この問題を解いていきます。 010 - Score Sum Queries（★2）

004 - Cross Sum（★2）

ざっくりいうと、1組と2組の人たちのテストの点数と出席番号が与えられます。各クラスのL番～R番までの人たちの合計点を求めるという問題です。

立てた方針

累積和なので、まずは1組と2組の点数リストを作りました。 iter().sumで作ったリストから指定された区間の累積和を求めました。

Rustでの回答例

use proconio::input;

fn main() {
    input! {
        n: usize,
        mut a: [[i32; 2];n],
        q:usize,
        mut b: [[i32; 2];q]
    }
    let mut one = vec![];
    let mut two = vec![];

    for v in a {
        if v[0] == 1 {
            one.push(v[1]);
            two.push(0);
        } else {
            one.push(0);
            two.push(v[1]);
        }
    }

    for v in b {
        let mut l = v[0] as usize - 1;
        let mut r = v[1] as usize;
        if one.len() < r {
            r = one.len();
        }

        let oans = &one[l..r].iter().sum::<i32>();

        l = v[0] as usize - 1;
        r = v[1] as usize;
        if two.len() < r {
            r = two.len();
        }

        let tans = &two[l..r].iter().sum::<i32>();
        println!("{} {}", oans, tans);
    }
}

無理くり感がすごいのですが、ギリギリ通っています。

想定回答

想定回答見てみると、累積和ということで都度合計を計算するのではなく累積和のリストを作っておき、その累積和の差を求めることで期待する範囲の値を算出するというものです。

早速修正してみます。

use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [(usize,usize);n],
        q:usize,
        b: [(usize,usize);q],
    }

    let mut one = vec![];
    one.push(0);
    let mut two = vec![];
    two.push(0);
    let mut sum1: i32 = 0;
    let mut sum2: i32 = 0;
    for (c, p) in a {
        if c == 1 {
            sum1 += p as i32;
        } else {
            sum2 += p as i32;
        }
        one.push(sum1);
        two.push(sum2);
    }

    for (l, r) in b {
        println!("{} {}", one[r] - one[l - 1], two[r] - two[l - 1]);
    }
}

1/10ぐらいの実行速度まで減らせましたね。

なるほどなぁ。