Go to Qiita Advent Calendar 2024 Top
LoginSignup
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@pinana(ぴぃの)

【Rust】競プロ文脈でジェネリック、トレイトを理解する【二次元累積和】

Posted at

コンテスト中で忙しい人へ

実装した二次元累積和を置いておきます。
半開区間[i0, i1) × [j0, j1)の値の総和を$O(1)$求めます（構築は$O(HW)$）。
半開区間のためi1の行とj1の列は含まれないことに注意してください。

image.png

num_traitsクレートを使用しているため、AtCoder以外のJudgeでは多分動かないと思います。

コピペして使用してください
use cumsum2d::CumSum2D;

pub mod cumsum2d {
    use num_traits::Zero;
    use std::ops::Sub;

    #[derive(Debug, Clone)]
    pub struct CumSum2D<T> {
        pub data: Vec<Vec<T>>,
    }

    impl<T> CumSum2D<T>
        where T: Zero + Copy + Clone + Sub<Output=T>
    {
        pub fn from(input: &Vec<Vec<T>>) -> Self {
            let h = input.len();
            let w = input[0].len();
            let mut data = vec![vec![T::zero(); w + 1]; h + 1];
            for i in 1..=h {
                for j in 1..=w {
                    data[i][j] = data[i - 1][j] + data[i][j - 1] + input[i - 1][j - 1] - data[i - 1][j - 1];
                }
            }
            CumSum2D { data }
        }

        pub fn query(&self, i0: usize, i1: usize, j0: usize, j1: usize) -> T {
            self.data[i1][j1] - self.data[i1][j0] - self.data[i0][j1] + self.data[i0][j0]
        }
    }

    #[test]
    fn test_cumsum2d() {
        let cs = CumSum2D::from(&vec![vec![1, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78);
        assert_eq!(cs.query(0, 1, 0, 1), 1);
        assert_eq!(cs.query(1, 3, 1, 3), 34);

        // for i64
        let cs = CumSum2D::from(&vec![vec![1i64, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78i64);

        // for u64
        let cs = CumSum2D::from(&vec![vec![1u64, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78u64);

        // for usize
        let cs = CumSum2D::from(&vec![vec![1usize, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78usize);

        // // for f64
        // // Cargo.tomlに以下を追加してね
        // // assert_approx_eq = "1.1.0"
        // use assert_approx_eq::assert_approx_eq;
        // use num_traits::Float;
        // let cs =  CumSum2D::from(&vec![vec![0.1,0.2,0.3,0.4],
        //                                vec![0.5,0.6,0.7,0.8],
        //                                vec![0.9,1.0,1.1,1.2]]);
        // assert_approx_eq!(cs.query(1, 3, 1, 3), 3.4);
    }
}

はじめに

先日のABC203のD問題で二次元累積和を使用する問題が出たので、これを機にライブラリとして整備しました。
どうせならi64だけではなくf64等にも使えるようにしたいとか考えていたら、実装でいろいろ躓いたので記事にします。

二次元累積和については、以下を参照してください（実装も下記記事に準拠します）。

対象読者

  • そろそろ自分用の競プロライブラリをつくりたいと思ってる人
  • 正直Rustのトレイト、ジェネリックがあやふやな人
  • Rustつよつよの人のライブラリをチラ見したら、宇宙語が書いてあってそっと閉じた人

事始め

次の2つのメソッドを持つ構造体を作成することを考えます。

  • 二次元ベクタの参照を引数に取り、累積和を構築するメソッドfrom
  • 区間[i0, i1) × [j0, j1)の値の総和の返すメソッドquery

以下が使用イメージです。

let a = vec![vec![1, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]];
let cs = CumSum2D::from(&a);
println("{}", cs.query(1, 3, 1, 3))  // 34

以下に構造体とメソッドのガワを準備しました。dataに構築した累積和が入ります。
何の前置きもせずジェネリック実装してますが、Tにi64やf64が入ると考えれば、それほど理解は難しくないと思います。

#[derive(Debug, Clone)]
pub struct CumSum2D<T> {
    pub data: Vec<Vec<T>>,
}

impl<T> CumSum2D<T>
{
    pub fn from(input: &Vec<Vec<T>>) -> Self {
        todo!()  // ①
    }

    pub fn query(&self, i0: usize, i1: usize, j0: usize, j1: usize) -> T {
        todo!()  // ②
    }
}

ここから①、②を実装していきます。

トレイト境界

①fromを実装していきます。
インプットが$H$×$W$のベクタとすると、二次元累積和は$(H+1)$×$(W+1)$のベクタになります。
まず、$(H+1)$×$(W+1)$のベクタを0埋めして作成することを考えます。

impl<T> CumSum2D<T>
{
    pub fn from(input: &Vec<Vec<T>>) -> Self {
        let h = input.len();
        let w = input[0].len();
        let mut data = vec![vec![0 as T; w + 1]; h + 1];   // エラー
        CumSum2D { data }
    }
}

いかにも怪しい実装です。実際にコンパイルが通りません。

エラーメッセージを見て行きましょう。

error[E0277]: the trait bound `T: std::clone::Clone` is not satisfied
80 |let mut data = vec![vec![0 as T; w + 1]; h + 1];
   |                         ^^^^^^^^^^^^^^^^^^^^^^ the trait `std::clone::Clone` is not implemented for `T`

まず、Tに対して、Cloneが実装されてないことを怒られているようです。

今回Tが対象としたいのは、i32やf64といったプリミティブな数値型です。
プリミティブな数値型は次の代入に示されるように、値がコピーされます。

let a = 1;
let b = a;      // 値渡しで代入される

従って、TはCopy + Cloneを条件を必ず満たして欲しいということになります。
このようにTに制約を課していくことを、トレイト境界（今回の場合、特にジェネリック境界）と言います。

トレイト境界はimplに記載していきます。（二通り書き方があり、今回はwhere句で書いていきます）

impl<T> CumSum2D<T>
    where T: Copy + Clone

0が欲しい

Copy + Cloneをトレイト境界に定めても、まだまだエラーが出ます。

error[E0605]: non-primitive cast: `i32` as `T`
80 |         let mut data = vec![vec![0 as T; w + 1]; h + 1];
   |                                  ^^^^^^
   = note: an `as` expression can only be used to convert between primitive types. Consider using the `From` trait

0をTにキャストするためにFromトレイトを定めないといけないようです。

でも、ちょっと待って下さい。
今回行いたいことは、二次元配列を0で埋めることです。
ここで言う0とは、i32では0i32、f64では0.0、usizeでは0usizeのことになります。

型に依って適切な0が降ってくる仕組みはないかなー？？？
ということで活躍するトレイトが、num_traits::Zeroです。

以下のようにトレイト境界を定めます。

use num_traits::Zero;
impl<T> CumSum2D<T>
    where T: Zero + Copy + Clone

すると、Tに対してzero()というメソッドが生えてきます。
このメソッドこそが前述した「i32では0i32、f64では0.0、usizeでは0usize」を返すメソッドとなります。

let mut data = vec![vec![T::zero(); w + 1]; h + 1];   // これならOK

あとは累積和を構築していくコードを書いてfromは完成です。

impl<T> CumSum2D<T>
    where T: Zero + Copy + Clone
{
    pub fn from(input: &Vec<Vec<T>>) -> Self {
        let h = input.len();
        let w = input[0].len();
        let mut data = vec![vec![0 as T; w + 1]; h + 1];
        for i in 1..=h {
            for j in 1..=w {
                data[i][j] = data[i - 1][j] + data[i][j - 1] + input[i - 1][j - 1] - data[i - 1][j - 1];
            }
        }
        CumSum2D { data }
    }
}

演算子のオーバーロードとT::Output

この調子で、②のQueryを実装していきます。

impl<T> CumSum2D<T>
    where T: Zero + Copy + Clone
{
    pub fn query(&self, i0: usize, i1: usize, j0: usize, j1: usize) -> T {
        self.data[i1][j1] - self.data[i1][j0] - self.data[i0][j1] + self.data[i0][j0]
    }
}

error[E0369]: cannot subtract `T` from `T`
  --> src/bin/d.rs:83:84
   |
83 |                 data[i][j] = data[i - 1][j] + data[i][j - 1] + input[i - 1][j - 1] - data[i - 1][j - 1];
   |                              ----------------------------------------------------- ^ ------------------ T
   |                              |
   |                              T
   = note: `T` might need a bound for `std::ops::Sub`

コンパイラに怒られました。
どうやらTに対して引き算が行えることを保証してあげなければいけないようです。
Rustくんは細かいなぁ…

use std::ops::Sub;
impl<T> CumSum2D<T>
    where T: Zero + Copy + Clone + Sub

error[E0308]: mismatched types
  --> src/bin/d.rs:83:30
   |
83 |                 data[i][j] = data[i - 1][j] + data[i][j - 1] + input[i - 1][j - 1] - data[i - 1][j - 1];
   |                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter `T`, found associated type
   |
   = note: expected type parameter `T`
             found associated type `<T as std::ops::Sub>::Output`
   = note: you might be missing a type parameter or trait bound

error[E0369]: cannot subtract `T` from `<T as std::ops::Sub>::Output`
  --> src/bin/d.rs:90:47
   |
90 |         self.data[i1][j1] - self.data[i1][j0] - self.data[i0][j1] + self.data[i0][j0]
   |         ------------------------------------- ^ ----------------- T
   |         |
   |         <T as std::ops::Sub>::Output
   |
   = note: an implementation of `std::ops::Sub` might be missing for `<T as std::ops::Sub>::Output`

トレイト境界に、演算子のオーバーロードに必要なstd::ops::Subを追加しましたが、まだ怒られます。
これはTとTの引き算の結果がTであるとは限らないことに起因します。
Rustくんは本当に細かいなぁ…

以下のように<Output=T>を付けたトレイト境界を定めることで、上記条件を保証することが可能です。

impl<T> CumSum2D<T>
    where T: Zero + Copy + Clone + Sub<Output=T>

完成コード

use cumsum2d::CumSum2D;

pub mod cumsum2d {
    use num_traits::Zero;
    use std::ops::Sub;

    #[derive(Debug, Clone)]
    pub struct CumSum2D<T> {
        pub data: Vec<Vec<T>>,
    }

    impl<T> CumSum2D<T>
        where T: Zero + Copy + Clone + Sub<Output=T>
    {
        pub fn from(input: &Vec<Vec<T>>) -> Self {
            let h = input.len();
            let w = input[0].len();
            let mut data = vec![vec![T::zero(); w + 1]; h + 1];
            for i in 1..=h {
                for j in 1..=w {
                    data[i][j] = data[i - 1][j] + data[i][j - 1] + input[i - 1][j - 1] - data[i - 1][j - 1];
                }
            }
            CumSum2D { data }
        }

        pub fn query(&self, i0: usize, i1: usize, j0: usize, j1: usize) -> T {
            self.data[i1][j1] - self.data[i1][j0] - self.data[i0][j1] + self.data[i0][j0]
        }
    }

    #[test]
    fn test_cumsum2d() {
        let cs = CumSum2D::from(&vec![vec![1, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78);
        assert_eq!(cs.query(0, 1, 0, 1), 1);
        assert_eq!(cs.query(1, 3, 1, 3), 34);

        // for i64
        let cs = CumSum2D::from(&vec![vec![1i64, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78i64);

        // for u64
        let cs = CumSum2D::from(&vec![vec![1u64, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78u64);

        // for usize
        let cs = CumSum2D::from(&vec![vec![1usize, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78usize);

        // // for f64
        // // Cargo.tomlに以下を追加してね
        // // assert_approx_eq = "1.1.0"
        // use assert_approx_eq::assert_approx_eq;
        // use num_traits::Float;
        // let cs =  CumSum2D::from(&vec![vec![0.1,0.2,0.3,0.4],
        //                                vec![0.5,0.6,0.7,0.8],
        //                                vec![0.9,1.0,1.1,1.2]]);
        // assert_approx_eq!(cs.query(1, 3, 1, 3), 3.4);
    }
}

最後に

ABC203-DでAC出たんで大丈夫かと思うんですが、実装コードに誤りがあったら教えて下さい。

参考

3
0
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
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?