Submission #2482856

---

Source Code Expand

package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func nextString() string {
  sc.Scan()
  return sc.Text()
}

func main() {
  var n int
  var k int
  fmt.Scan(&n, &k)
  k2 := k*2
  // 0 ≦ x,y ≦ 2K に圧縮
  squares := make([][]int, k2)
  for i := range squares {
    squares[i] = make([]int, k2)
  }
  sc.Split(bufio.ScanWords)
  for i := 0; i < n; i++ {
    x := nextInt()
    y := nextInt()
    color := nextString()
    // 'W'はY方向にKずらした'B'と同値
    if color == "W" {
      y += k
    }
    squares[x % k2][y % k2]++ 
  }
  // 計算量削減のために累積和を事前算出
  for i := 0; i < k2; i++ {
    for j := 1; j < k2; j++ {
      squares[i][j] += squares[i][j-1]
    }      
  }
  for j := 0; j < k2; j++ {
    for i := 1; i < k2; i++ {
      squares[i][j] += squares[i-1][j]
    }
  }  
  max_ := 0
  end := k2-1
  for i := 0; i < k; i++ {
    for j := 0; j < k; j++ {
      // ex) k = 2
      //      ■ □ □ ■ 
      //  j+k □ ■ ■ □
      //      □ ■ ■ □
      //    j ■ □ □ ■
      //      i   i+k
      cnt :=
        (squares[i][j]) +
        (squares[end][j] - squares[i+k][j]) +
        (squares[i+k][j+k] - squares[i+k][j] - squares[i][j+k] + squares[i][j]) +
        (squares[i][end] - squares[i][j+k]) +
        (squares[end][end] - squares[end][j+k] - squares[i+k][end] + squares[i+k][j+k])
      max_ = max(max(cnt, n - cnt), max_)
    }
  }  
  fmt.Print(max_)
}

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

Submission Info

Judge Result