競プロ典型 90 問 Cross Sum

こんにちは、ナナオです。

前回に引き続き競プロを実施していきたいと思います。

今回はAtCoderの問題を解いていきます。

問題は以下です。

実装

二次元の累積和ですね。

とりあえず愚直に解いてみます。

package main
import "fmt"
func main() {
  var h, w int
  fmt.Scan(&h, &w)
  g := make([][]int, h)
  for i := 0; i < h; i++ {
    g[i] = make([]int, w)
    for j := 0; j < w; j++ {
      fmt.Scan(&g[i][j])
    }
  }
  hg := make([]int, h)
  for i := 0; i < h; i++ {
    s := 0
    for j := 0; j < w; j++ {
      s += g[i][j]
    }
    hg[i] = s
  }
  wg := make([]int, w)
  for i := 0; i < w; i++ {
    s := 0
    for j := 0; j < h; j++ {
      s += g[j][i]
    }
    wg[i] = s
  }
  ans := make([][]int, h)
  for i := 0; i < h; i++ {
    ans[i] = make([]int, w)
    for j := 0; j < w; j++ {
      ans[i][j] = hg[i] + wg[j] - g[i][j]
    }
  }
  for i := 0; i < h; i++ {
    for j := 0; j < w; j++ {
      if j < w - 1 {
        fmt.Printf("%d ", ans[i][j])
      } else {
        fmt.Printf("%d", ans[i][j])
      }
    }
    fmt.Println()
  }
}

ですがこれだとタイムオーバーしてしまいました。

なんでやねん。

解説記事を見つつ、一部のコードを修正しました。

package main
import "fmt"
func main() {
  var h, w int
  fmt.Scan(&h, &w)
  g := make([][]int, h)
  hg := make([]int, h)
  wg := make([]int, w)
  for i := 0; i < h; i++ {
    g[i] = make([]int, w)
    for j := 0; j < w; j++ {
      fmt.Scan(&g[i][j])
      hg[i] += g[i][j]
      wg[j] += g[i][j]
    }
  }
  for i := 0; i < h; i++ {
    for j := 0; j < w; j++ {
      if j < w - 1 {
        fmt.Printf("%d ", hg[i] + wg[j] - g[i][j])
      } else {
        fmt.Printf("%d", hg[i] + wg[j] - g[i][j])
      }
    }
    fmt.Println()
  }
}

横軸と縦軸の計算と出力時の計算をそれぞれ一つのループ内にまとめることで、計算量を減らすことができました。

これで実行してみましたが、やはり実行速度が遅く…なぜ…

通っているパターンのGoのコードを見ながら少し修正しました。

package main
import (
  "bufio"
  "os"
  "fmt"
)
func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

  var h, w int
  fmt.Fscan(in, &h, &w)
  g := make([][]int, h)
  hg := make([]int, h)
  wg := make([]int, w)
  for i := 0; i < h; i++ {
    g[i] = make([]int, w)
    for j := 0; j < w; j++ {
      fmt.Fscan(in, &g[i][j])
      hg[i] += g[i][j]
      wg[j] += g[i][j]
    }
  }
  for i := 0; i < h; i++ {
    for j := 0; j < w; j++ {
      fmt.Fprint(out, hg[i] + wg[j] - g[i][j])
      if j < w - 1 {  
        fmt.Fprint(out, " ")
      }
    }
    fmt.Fprintln(out)
  }
}

これなら通るんですね。ロジックじゃない部分で通らないってこともあるんですね。。。

Goは早い言語だと思ってたですが、そうでもないかも…

というわけで今回はこれで👍

実装#

実装