ARC 089 D. Checker

https://beta.atcoder.jp/contests/arc089/tasks/arc089_b

この解説では、座標を（横,縦）で表している。

$(x,y)$ が黒であることと $(x \bmod 2K, y \bmod 2K)$ が黒であることは同値である。
$(x,y)$ が白であることと $(x+K,y)$ が黒であることは同値である。

図1. 同値変換によって $2K \times 2K$ の領域に条件を移動できる($K=2$)。白の条件は黒の条件に言い換えられるため、黒しかない場合に還元できる。

図2. 盤面をコピーすることで範囲が単純になる。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
  int n, k;
  cin >> n >> k;
  vector<vector<int>> s(4 * k + 1, vector<int>(4 * k + 1));

  for (int i = 0; i < n; i++) {
    int x, y;
    char c;
    cin >> x >> y >> c;
    if (c == 'W') {
      x += k;
    }
    x %= 2 * k;
    y %= 2 * k;
    s[x + 1][y + 1]++;
    s[x + 2 * k + 1][y + 1]++;
    s[x + 1][y + 2 * k + 1]++;
    s[x + 2 * k + 1][y + 2 * k + 1]++;
  }

  for (int i = 0; i + 1 < s.size(); i++) {
    for (int j = 0; j + 1 < s.size(); j++) {
      s[i + 1][j + 1] += s[i + 1][j] + s[i][j + 1] - s[i][j];
    }
  }

  auto sum = [&](int y, int x, int n) {
    return s[y + n][x + n] - s[y + n][x] - s[y][x + n] + s[y][x];
  };

  int ans = 0;
  for (int i = 0; i < 2 * k; i++) {
    for (int j = 0; j < 2 * k; j++) {
      int s1 = sum(i, j, k);
      int s2 = sum(i + k, j + k, k);
      ans = max(ans, s1 + s2);
    }
  }
  cout << ans << endl;
}

図1のコード

\documentclass[dvipdfmx,margin=1cm]{standalone}

\usepackage{newtxtext}
\usepackage{newtxmath}
\usepackage{tikz}

\usetikzlibrary{calc}
\usetikzlibrary{patterns}

\begin{document}

\begin{tikzpicture}[yscale=-1,
  foo/.style={circle,inner sep=0.07cm},
  ]

  \foreach \x/\y in {2/0, 6/0, 0/2, 4/2, 2/4, 6/4, 0/6, 4/6} {
    \draw[fill=black!10] (\x,\y) rectangle ++(2,2);
  }

  \draw[help lines] (-0.5,-0.5) grid (8.5,8.5);
  \draw[step=2] (-0.5,-0.5) grid (8.5,8.5);
  \draw[ultra thick] (0,0) rectangle (4,4);

  \node[fill=black,foo] (a) at ($(0,3) +(.5,.5)$) {};
  \node[fill=black,foo] (b) at ($(4,7) +(.5,.5)$) {};
  \draw[-latex,very thick] (b) to node [auto,xshift=-0.4cm] {$\bmod 2K$} (a);

  \node[fill=white,draw=black,foo] (c) at ($(5,1) +(.5,.5)$) {};
  \node[fill=black,foo] (d) at ($(7,1) +(.5,.5)$) {};
  \node[fill=black,foo] (e) at ($(3,1) +(.5,.5)$) {};
  \draw[-latex,very thick] (c) to node [auto] {$+K$} (d);
  \draw[-latex,very thick] (d) to [bend right=30] node [auto,xshift=-0.1cm] {$\bmod 2K$} (e);

  \draw (0,0) to [very thick,bend right=20] node [auto] {$2K$} (4,0);
  \draw (0,0) to [very thick,bend left=20] node [auto,swap] {$2K$} (0,4);

\end{tikzpicture}

\end{document}

図 2 のコード

% pgfmanual v3.0.1a
\documentclass[dvipdfmx,margin=1cm]{standalone}

\usepackage{newtxtext}
\usepackage{newtxmath}
\usepackage{tikz}

\usetikzlibrary{calc}
\usetikzlibrary{patterns}
\begin{document}

\begin{tikzpicture}[yscale=-1]
  \begin{scope}[shift={(0,2)},local bounding box=scope1]
    \draw [help lines] (-0.5,-0.5) grid (4.5,4.5);
    \draw [step=2] (-0.5,-0.5) grid (4.5,4.5);
    \draw [very thick] (0,0) rectangle (4,4);

    \foreach \dy/\dx in {0/0} {
      \foreach \x/\y in {1/0, 3/1, 2/3}{
        \draw [fill=black,circle] ($(\x,\y) + (.5,.5) + (\dx,\dy)$) circle[radius=0.1cm];
      }
    }

    % pattern=crosshatch dots -- See pgfmanual p.666
    \draw [ultra thick,pattern=crosshatch dots] (1,2) rectangle (3,4);
    \draw [ultra thick,pattern=crosshatch dots] (0,0) rectangle (1,2);
    \draw [ultra thick,pattern=crosshatch dots] (3,0) rectangle (4,2);

    \draw [-latex,line width=0.1cm] (0.5,1.5) -- (1,2);
  \end{scope}

  \begin{scope}[shift={(10,0)},local bounding box=scope2]
    \draw [fill=black!20] (0,0) rectangle (4,4);
    \draw [fill=red!20] (4,0) rectangle (8,4);
    \draw [fill=blue!20] (0,4) rectangle (4,8);
    \draw [fill=green!20] (4,4) rectangle (8,8);

    \draw [help lines] (-0.5,-0.5) grid (8.5,8.5);
    \draw [step=2] (-0.5,-0.5) grid (8.5,8.5);
    \draw [very thick] (0,0) rectangle (4,4);

    \foreach \dy/\dx in {0/0, 0/4, 4/0, 4/4} {
      \foreach \x/\y in {1/0, 3/1, 2/3}{
        \draw [fill=black,circle] ($(\x,\y) + (.5,.5) + (\dx,\dy)$) circle[radius=0.1cm];
      }
    }

    \draw [-latex,ultra thick] (2,0) to [bend right=30] node [auto] {Copy} (6,0);
    \draw [-latex,ultra thick] (0,2) to [bend left=30] node [auto,swap] {Copy} (0,6);
    \draw [-latex,ultra thick] (2,8) to [bend left=30] node [auto,swap] {Copy} (6,8);

    \draw [ultra thick,pattern=crosshatch dots] (1,2) rectangle (3,4);
    \draw [ultra thick,pattern=crosshatch dots] (3,4) rectangle (5,6);

    \draw [-latex,line width=0.1cm] (0.5,1.5) -- (1,2);
  \end{scope}

  \draw [-latex,ultra thick] ($(scope1.east)+(0.5,0)$) -- node [auto] {Transform} ($(scope2.west)-(0.5,0)$);

\end{tikzpicture}

\end{document}