Rustの勉強ログ　競プロ典型90問をRustで説いてみる　その2　004 Cross Sum

# 目的

[前回](https://qiita.com/mickie895/items/f7920400a512deb31e8b)の続き。
今回も習熟を目的として易しめの問題である[004 Cross Sum](https://atcoder.jp/contests/typical90/tasks/typical90_d)を解いてみる。

# 問題の考え方

全マス(最大2000×2000)に対して計算を行い、文字を出力する必要があるため、計算量は最低でもO(H * W)になる。
ここを定数時間で完了させないとTLEとなるはず。

各行・各列の合計値を中間データとして持っておき、それを使って同じ行・列の合計を出せるはず。
そうすれば中間データの作成、最終結果の出力ともにO(H * W)になるため十分な速度を保つはずだ。

# コード

<details><summary>例によって長いので折りたたみ</summary>
<div>

```rust
use std::io;

fn main() {
    let hw_line: Vec<i32> = read_line_to_num();
    let h: i32 = hw_line[0];
    let w: i32 = hw_line[1];

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

    for _ in 0..h{
        a.push(read_line_to_num());
    }

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

    for i in 0 .. h as usize{
        let row: &Vec<i32> = &a[i];
        row_sum.push(sum(row));
    }

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

    for i in 0 .. w as usize{
        let col: Vec<i32> = (0..h as usize).map(|x| a[x][i]).collect();
        col_sum.push(sum(&col));
    }

    for y in 0 .. h as usize{
        for x in 0 .. w as usize{
            if x != 0{
                print!(" ");
            }
            print!("{}", row_sum[y] + col_sum[x] - a[y][x]);
        }
        println!();
    }

}

fn read_line_to_num() -> Vec<i32>{
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let splitted: Vec<&str> = input.trim().split(" ").collect();
    let mut result: Vec<i32> = Vec::new();

    for s in splitted{
        result.push(s.parse().unwrap());
    }

    result
}

fn sum(items:&Vec<i32>) -> i32{
    // itemsは使用するが破壊的な変更などを行うことはないため、単に借りておく。
    let mut sum:i32 = 0;

    for i in items{
        sum += i;
    }

    sum
}

```
</div>
</details>

# 今回のポイント

## すでに定義されている値を別の場所で使いたい場合は借用する

例えば下記の部分。Vec(a)の中のVec(a[i])を参照しようとしていて、a[i]はもちろん上の方で定義されている。

このように一時的に値を借りる場合、借用すれば良いようだ。前回はここらへんがうろ覚えになっていた気がする。
(Cを昔触ってたせいで&a[i]がポインタを示してる気がしてしまうのが辛い。)

```rust
    for i in 0 .. h as usize{
        let row: &Vec<i32> = &a[i];
        row_sum.push(sum(row));
    }
```

## for文を使わなくても処理できないか考える

https://qiita.com/segfo/items/964dae7987e4cb882328

上記記事を読みながら、「同じ列の配列をまとめてVecにする」処理をfor文を使わずに表したのが下記の部分。

```rust

    for i in 0 .. w as usize{
        let col: Vec<i32> = (0..h as usize).map(|x| a[x][i]).collect();
        col_sum.push(sum(&col));
    }

```

# 提出後のリファクタリング

最近の言語なんだしsum関数ぐらいライブラリ側で実装されているはず、と書いているときから気になっていた。
上記のコードでとりあえず通してから色々調べたら、ちゃんと定義されていることがわかった。

https://doc.rust-lang.org/std/iter/trait.Sum.html

それに、map関数はもっと多くの場所に適用でき、そうすればaやrow_sumなどのmut宣言は外せそうであることに気がついた。

最終的な出力は次のとおりになった。
だいぶスッキリしたコードになって満足。
(最初の時点では1293 Byteだったコードサイズが865 Byteまで減らせた。)

```rust
use std::io;

fn main() {
    let hw_line: Vec<i32> = read_line_to_num();
    let h: i32 = hw_line[0];
    let w: i32 = hw_line[1];

    let a: Vec<Vec<i32>> = (0 .. h).map(|_| read_line_to_num()).collect();

    let row_sum: Vec<i32> = (0 .. h as usize).map(|x| a[x].iter().sum()).collect();

    let col_sum: Vec<i32> = (0 .. w as usize).map(|i| (0..h as usize).map(|x| a[x][i]).sum()).collect();

    for y in 0 .. h as usize{
        for x in 0 .. w as usize{
            if x != 0{
                print!(" ");
            }
            print!("{}", row_sum[y] + col_sum[x] - a[y][x]);
        }
        println!();
    }

}

fn read_line_to_num() -> Vec<i32>{
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();

    input.trim().split(" ").map(|split_str| split_str.parse().unwrap()).collect()
}

```