AtCoder Regular Contest 025 B - チョコレート

前回に引き続き累積和系の過去問

問題

arc025.contest.atcoder.jp

コード（Scala 2.11.7）

https://arc025.contest.atcoder.jp/submissions/2486360

object Main extends App {
  val Array(h, w) = io.StdIn.readLine().split(' ').map(_.toInt)
  val squares = Array.fill(h+1)(Array.fill(w+1)(0))
  for (i <- 1 to h) {
    val line = io.StdIn.readLine().split(' ').map(_.toInt)
    for (j <- 1 to w) {
      val c = if (((i ^ j) & 1) == 0) line(j-1) else -line(j-1)
      squares(i)(j) += squares(i)(j-1)
      squares(i)(j) += c
    }
  }
  for {
    j <- 1 to w
    i <- 2 to h
  } squares(i)(j) += squares(i-1)(j)
  var max = 0
  for {
    i <- 1 to h
    j <- 1 to w
    ii <- i to h
    jj <- j to w
  } {
    //   h 0 □ □ □ □ □
    //  ii 0 □ ■ ■ ■ □
    //   i 0 □ ■ ■ ■ □
    //     0 □ □ □ □ □
    //   0 0 0 0 0 0 0
    //     0   j   jj w
    if (squares(ii)(jj) - squares(i-1)(jj) - squares(ii)(j-1) + squares(i-1)(j-1) == 0)
      max = Math.max(max, (ii-i+1) * (jj-j+1))
  }
  println(max)
}

コード（Go 1.6）

https://arc025.contest.atcoder.jp/submissions/2486303

package main

import (
  "bufio"
  "fmt"
  "os"
  "strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
    sc.Scan()
    i, _ := strconv.Atoi(sc.Text())
    return i
}

func max(a int, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

func main() {
  sc.Split(bufio.ScanWords)
  h := nextInt()
  w := nextInt()
  squares := make([][]int, h+1)
  for i := range squares {
    squares[i] = make([]int, w+1)
  }
  for i := 1; i <= h; i++ {
    for j:= 1; j <= w; j++ {
      c := nextInt()
      squares[i][j] += squares[i][j-1]
      if (i ^ j) & 1 == 0 {
        squares[i][j] += c
      } else {
        squares[i][j] -= c
      }
    }
  }
  for j := 1; j <= w; j++ {
    for i := 2; i <= h; i++ {
      squares[i][j] += squares[i-1][j]
    }
  }
  max_ := 0
  for i := 1; i <= h; i++ {
    for j := 1; j <= w; j++ {
      for ii := i; ii <= h; ii++ {
        for jj := j; jj <= w; jj++ {
          //   h 0 □ □ □ □ □
          //  ii 0 □ ■ ■ ■ □
          //   i 0 □ ■ ■ ■ □
          //     0 □ □ □ □ □
          //   0 0 0 0 0 0 0
          //     0   j   jj w
          if (squares[ii][jj] - squares[i-1][jj] - squares[ii][j-1] + squares[i-1][j-1] == 0) {
            max_ = max(max_, (ii-i+1) * (jj-j+1))
          }
        }
      }
    }
  }
  fmt.Println(max_)
}

パフォーマンス比較

	処理時間（最大）	処理時間（最小）	メモリ使用量
Scala	629 ms	331 ms	38264 KB
Go	157 ms	1 ms	768 KB