Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

品質管理

会津タカダ市が生産販売する布製コースターは、対称なデザインでとても美しいことで知られている。会津タカダ市では品質管理の一環として、製造ラインにカメラを設置し、各コースターを撮影して得られた画像が対称になっているかを自動で検証している。各コースターは N &times; N ピクセルの正方形の白黒画像として表される。各ピクセルは白または黒の画像に対応して、0 または 1 の値をとる。

この度、生産ラインの機器更新にともなって、画像解析システムのソフトウェアを更新することになった。新システムでは、通信データ量を削減する工夫がなされ、以下の方法でカメラから解析システムにデータが送られてくる。

 ラインに流れてくる最初のコースターの情報は、N &times; N ピクセルの画像としてシステムに送られてくる。

 ２枚目以降のコースターの情報は、１つ前に送られた画像との差分だけが送られてくる。差分は、「0 から 1 」または「1 から 0 」へと変化したピクセルの位置の集合として与えられる。

C 枚のコースターについて、１枚目の画像のピクセル情報と続く C - 1 枚分の差分情報を入力し、上下対称かつ左右対称となっているコースターの枚数を報告するプログラムを作成せよ。

Input

入力は以下の形式で与えられる。

C N
p11p12...p1N
p21p22...p2N
:
pN1pN2...pNN
diff1
diff2
:
diffC&minus;1

１行目にコースターの枚数 C (1 ≤ C ≤ 10000) と画像の縦と横のピクセル数 N (2 ≤ N ≤ 1000 かつ N は偶数) が与えられる。２行目から N + 1 行目に最初のコースターの画像のピクセルを表す N行 &times; N 列の数字 pij (pij は 0 または 1)が与えられる。

N + 2 行目以降に、２枚目以降のコースターの情報を表す差分 diffi が次の形式で与えられる。

D
r1 c1
r2 c2
:
rD cD

１行目に変化したピクセルの数 D (0 ≤ D ≤ 100) が与えられる。続くD 行に変化したピクセルの行と列の番号をそれぞれ表す ri とci (1 ≤ ri, ci ≤ N) が与えられる。diffi の中に、同じ位置は２回以上与えられない。

Output

上下対称かつ左右対称となっているコースターの枚数を１行に出力する。

Sample Input 1

7 8
00100000
00011000
10111101
01100110
01000110
10111101
00011000
00100100
2
5 3
1 6
1
6 8
3
6 8
3 3
3 6
2
6 3
6 6
0
2
3 8
6 8

Sample Output 1

3

入力例１のコースターの画像を以下に示す。この場合、２枚目、５枚目、６枚目のコースターが上下対称かつ左右対称となるため、3と報告する。

Sample Input 2

1 6
000000
000000
010010
010010
000000
000000

Sample Output 2

1

Sample Input 3

2 2
00
00
4
1 1
1 2
2 1
2 2

Sample Output 3

2



Sample input:
7 8
00100000
00011000
10111101
01100110
01000110
10111101
00011000
00100100
2
5 3
1 6
1
6 8
3
6 8
3 3
3 6
2
6 3
6 6
0
2
3 8
6 8


Sample output:
3

Submission status: Wrong Answer

Solution code:
from copy import deepcopy as cd

def rotate90(p):
    h,w = len(p[0]),len(p)
    ret = [[0 for i in range(w)] for j in range(h)]
    for y in range(h):
        for x in range(w):
            ret[y][x] = p[w-1-x][y]
    return ret

def check(p,q):
    a,b,c = cd(q),cd(q),cd(q)
    return p == rotate90(rotate90(a)) and rotate90(b) == rotate90(rotate90(rotate90(c)))


def main():
    C,N=map(int,input().split())
    p = []
    for i in range(N):
        s=input()
        p.append([])
        for c in s:
            p[i].append(int(c))
    ans = 1 if check(p,p) else 0
    for _ in [0]*(C-1):
        D=int(input())
        q = p
        for i in range(D):
            y,x=map(int,input().split())
            q[y-1][x-1] = (q[y-1][x-1]+1)&1
            if check(p,q):
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy as cd

def rotate90(p):
    h,w = len(p[0]),len(p)
    ret = [[0 for i in range(w)] for j in range(h)]
    for y in range(h):
        for x in range(w):
            ret[y][x] = p[w-1-x][y]
    return ret

def check(p):
    a,b,c = cd(p),cd(p),cd(p)
    return p == rotate90(rotate90(a)) and rotate90(b) == rotate90(rotate90(rotate90(c)))

def main():
    C,N=map(int,input().split())
    p = []
    for i in range(N):
        s=input()
        p.append([])
        for c in s:
            p[i].append(int(c))
    ans = 1 if check(p) else 0
    for _ in [0]*(C-1):
        D=int(input())
        for i in range(D):
            y,x=map(int,input().split())
            p[y-1][x-1] = (p[y-1][x-1]+1)&1
            if check(p):
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy as cd

def rotate90(p):
    h,w = len(p[0]),len(p)
    ret = [[0 for i in range(w)] for j in range(h)]
    for y in range(h):
        for x in range(w):
            ret[y][x] = p[w-1-x][y]
    return ret

def check(p):
    a,b,c = cd(p),cd(p),cd(p)
    return p == rotate90(rotate90(a)) and rotate90(b) == rotate90(rotate90(rotate90(c)))

def main():
    C,N=map(int,input().split())
    p = []
    for i in range(N):
        s=input()
        p.append([])
        for c in s:
            p[i].append(int(c))
    ans = 1 if check(p) else 0
    for _ in [0]*(C-1):
        D=int(input())
        for i in range(D):
            y,x=map(int,input().split())
            p[y-1][x-1] = (p[y-1][x-1]+1)&1
        if check(p):
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def check(p):
    n = len(p)
    for y in range(n):
        for x in range(n):
            if p[y][x] != p[n-1-y][n-1-x] or p[x][y] != p[n-1-x][n-1-y]:
                return False
            if p[n-1-y][x] != p[y][n-1-x] or p[n-1-x][y] != p[x][n-1-y]:
                return False
    return True

def main():
    C,N=map(int,input().split())
    p = []
    for i in range(N):
        p.append(input())

    ans = 0
    if check(p):
        ans += 1
    for _ in range(C-1):
        D = int(input())
        for __ in range(D):
            y,x = map(int,input().split())
            y -= 1
            x -= 1
            p[y] = p[y][:x] + ( "0" if p[y][x] == "1" else "1" ) + p[y][x+1:]
        if check(p):
            ans += 1
            
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import copy
from pprint import pprint

def rotate90(p):
    n = len(p)
    q = [ [ 0 for _ in [0]*n ] for __ in [0]*n ]
    for y in range(n):
        for x in range(n):
            q[y][x] = p[n-1-x][y]
    return q

def check(p):
    n = len(p)
    for y in range(n):
        for x in range(n):
            if p[y][x] != p[n-1-y][n-1-x] or p[x][y] != p[n-1-x][n-1-y]:
                return False
            if p[n-1-y][x] != p[y][n-1-x] or p[n-1-x][y] != p[x][n-1-y]:
                return False
    for y in range(n):
        p[y] = list(reversed(p[y]))
    for y in range(n):
        for x in range(n):
            if p[y][x] != p[n-1-y][n-1-x] or p[x][y] != p[n-1-x][n-1-y]:
                return False
            if p[n-1-y][x] != p[y][n-1-x] or p[n-1-x][y] != p[x][n-1-y]:
                return False
    return True

def main():
    C,N=map(int,input().split())
    p = [ [ 0 for _ in [0]*N ] for __ in [0]*N ]
    for i in range(N):
        s = input()
        for j in range(N):
            p[i][j] = int(s[j])

    ans = 0
    if check(p):
        ans += 1
    for _ in range(C-1):
        D = int(input())
        for __ in range(D):
            y,x = map(int,input().split())
            y -= 1
            x -= 1
            p[y][x] = ( p[y][x] + 1 ) % 2
        if check(p):
            ans += 1
            
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import copy
from pprint import pprint

def rotate90(p):
    n = len(p)
    q = [ [ 0 for _ in [0]*n ] for __ in [0]*n ]
    for y in range(n):
        for x in range(n):
            q[y][x] = p[n-1-x][y]
    return q

def check(p):
    n = len(p)
    for y in range(n):
        for x in range(n):
            if p[y][x] != p[n-1-y][n-1-x] or p[x][y] != p[n-1-x][n-1-y]:
                return False
            if p[n-1-y][x] != p[y][n-1-x] or p[n-1-x][y] != p[x][n-1-y]:
                return False
    tmp = copy.deepcopy(p)
    for y in range(n):
        p[y] = list(reversed(p[y]))
    for y in range(n):
        for x in range(n):
            if p[y][x] != p[n-1-y][n-1-x] or p[x][y] != p[n-1-x][n-1-y]:
                return False
            if p[n-1-y][x] != p[y][n-1-x] or p[n-1-x][y] != p[x][n-1-y]:
                return False
    for y in range(n):
        for x in range(n):
            p[y][x] = tmp[n-1-y][x]
    for y in range(n):
        for x in range(n):
            if p[y][x] != p[n-1-y][n-1-x] or p[x][y] != p[n-1-x][n-1-y]:
                return False
            if p[n-1-y][x] != p[y][n-1-x] or p[n-1-x][y] != p[x][n-1-y]:
                return False
    return True

def main():
    C,N=map(int,input().split())
    p = [ [ 0 for _ in [0]*N ] for __ in [0]*N ]
    for i in range(N):
        s = input()
        for j in range(N):
            p[i][j] = int(s[j])

    ans = 0
    if check(p):
        ans += 1
    for _ in range(C-1):
        D = int(input())
        for __ in range(D):
            y,x = map(int,input().split())
            y -= 1
            x -= 1
            p[y][x] = ( p[y][x] + 1 ) % 2
        if check(p):
            ans += 1
            
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
c, n = map(int, input().split())
p = [list(input()) for _ in range(n)]
diff = []
for _ in range(c-1):
    hoge = int(input())
    diff.append([list(map(int, input().split())) for _ in range(hoge)])

def check(p, n):
    flag = True
    for i in range(n):
        for j in range(n//2):
            if p[i][j] != p[i][n-1-j]:
                flag = False
    for i in range(n//2):
        for j in range(n):
            if p[i][j] != p[n-1-i][j]:
                flag = False
    return flag

ans = 0
ans += check(p, n)
for l in diff:
    for i in l:
        p[i[0]-1][i[1]-1] = str((int(p[i[0]-1][i[1]-1])+1) % 2)
    ans += check(p, n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
c, n = map(int, input().split())
p = [list(input()) for _ in range(n)]
diff = []
for _ in range(c-1):
    hoge = int(input())
    diff.append([list(map(int, input().split())) for _ in range(hoge)])

def check(p, n):
    flag = True
    for i in range(n):
        for j in range(n//2):
            if p[i][j] != p[i][n-1-j]:
                flag = False
    for i in range(n//2):
        for j in range(n//2):
            if p[i][j] != p[n-1-i][j]:
                flag = False
    return flag

ans = 0
ans += check(p, n)
for l in diff:
    for i in l:
        p[i[0]-1][i[1]-1] = str((int(p[i[0]-1][i[1]-1])+1) % 2)
    ans += check(p, n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def check(table):
    N = len(table)
    flag = True
    for i in range(N):
        for j in range(N):
            if table[i][j] != table[N-1-i][j] or table[i][j] != table[i][N-1-j]:
                flag = False
                break
    return flag



C,N = [int(i) for i in input().split()]

table = [[0 for i in range(N)] for j in range(N)]

for i in range(N):
    s = input()
    for j in range(N):
        table[i][j] = int(s[j])
        

cnt = 0
if check(table):
    cnt = cnt + 1
    
for l in range(C-1):
    D = int(input())
    for m in range(D):
        x,y = [int(i) for i in input().split()]
        table[x-1][y-1] = 1 - table[x-1][y-1]
    if check(table):
        cnt = cnt + 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import copy
from pprint import pprint

def rotate90(p):
    n = len(p)
    q = [ [ 0 for _ in [0]*n ] for __ in [0]*n ]
    for y in range(n):
        for x in range(n):
            q[y][x] = p[n-1-x][y]
    return q

def check(p):
    n = len(p)
    for y in range(n):
        if p[y] != list(reversed(p[y])):
            return False
        for x in range(n):
            if p[y][x] != p[n-1-y][x]:
                return False
    return True

def main():
    C,N=map(int,input().split())
    p = [ [ 0 for _ in [0]*N ] for __ in [0]*N ]
    for i in range(N):
        s = input()
        for j in range(N):
            p[i][j] = int(s[j])

    ans = 0
    if check(p):
        ans += 1
    for _ in range(C-1):
        D = int(input())
        for __ in range(D):
            y,x = map(int,input().split())
            y -= 1
            x -= 1
            p[y][x] = ( p[y][x] + 1 ) % 2
        if check(p):
            ans += 1
            
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
C, n = map(int, input().split())
mp = [input() for _ in range(n)]
diff_dic = set()
def change(x, y):
  global diff_dic
  if (x, y) in diff_dic:
    diff_dic = diff_dic - {(x, y)}
  else:
    diff_dic = diff_dic | {(x, y)}

for y in range(n // 2):
  for x in range(n // 2):
    base = mp[y][x]
    if mp[y][n - 1 - x] != base:
      change(n - 1 - x, y)
    if mp[n - 1 - y][x] != base:
      change(x, n - 1 - y)
    if mp[n - 1 - y][n - 1 - x] != base:
      change(n - 1 - x, n - 1 - y)
if n % 2:
  for x in range(n // 2):
    if mp[n // 2][x] != mp[n // 2][n - 1 - x]:
      chenge(n - 1 - x, n // 2)
  for y in range(n // 2):
    if mp[y][n // 2] != mp[n - 1 - y][n // 2]:
      change(n // 2, n - 1 - y)

ans = 0
if not diff_dic:
  ans += 1

for _ in range(C - 1):
  d = int(input())
  for _ in range(d):
    r, c = map(int, input().split())
    r -= 1
    c -= 1
    if r < n // 2 and c < n // 2:
      change(c, n - 1 - r)
      change(n - 1 - c, r)
      change(n - 1 - c, n - 1 - r)
    elif n % 2 and r == n // 2 and c != n // 2:
      change(max(c, n - 1 - c), r)
    elif n % 2 and r != n // 2 and c == n // 2:
      change(c, max(r, n - 1 - r))
    else:
      change(c, r)
  if not diff_dic:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
c, n = map(int, input().split())
P = [list(map(int, input())) for i in range(n)]
S = [[0]*n for i in range(n)]
T = [[0]*n for i in range(n)]
dS = dT = 0
for i in range(n):
    for j in range(n//2):
        S[i][j] = P[i][j] ^ P[i][n-1-j]
        dS += S[i][j]
for j in range(n):
    for i in range(n//2):
        T[i][j] = P[i][j] ^ P[n-1-i][j]
        dT += T[i][j]
ans = +(dS == dT == 0)
for i in range(c-1):
    d = int(input())
    for j in range(d):
        r, c = map(int, input().split())
        S[r-1][min(c-1, n-c)] ^= 1
        if S[r-1][min(c-1, n-c)]:
            dS += 1
        else:
            dS -= 1
        T[min(r-1, n-r)][c-1] ^= 1
        if T[min(r-1, n-r)][c-1]:
            dT += 1
        else:
            dT -= 1
    if dS == dT == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
C, n = map(int, input().split())
mp = [input() for _ in range(n)]
diff_dic = {}
def change(x, y):
  global diff_dic
  if (x, y) in diff_dic:
    diff_dic.pop((x, y))
  else:
    diff_dic[(x, y)] = True
for y in range(n // 2):
  for x in range(n // 2):
    base = mp[y][x]
    if mp[y][n - 1 - x] != base:
      change(n - 1 - x, y)
    if mp[n - 1 - y][x] != base:
      change(x, n - 1 - y)
    if mp[n - 1 - y][n - 1 - x] != base:
      change(n - 1 - x, n - 1 - y)
if n % 2:
  for x in range(n // 2):
    if mp[n // 2][x] != mp[n // 2][n - 1 - x]:
      chenge(n - 1 - x, n // 2)
  for y in range(n // 2):
    if mp[y][n // 2] != mp[n - 1 - y][n // 2]:
      change(n // 2, n - 1 - y)

ans = 0
if not diff_dic:
  ans += 1

for _ in range(C - 1):
  d = int(input())
  for _ in range(d):
    r, c = map(int, input().split())
    r -= 1
    c -= 1
    if r < n // 2 and c < n // 2:
      change(c, n - 1 - r)
      change(n - 1 - c, r)
      change(n - 1 - c, n - 1 - r)
    elif n % 2 and r == n // 2 and c != n // 2:
      change(max(c, n - 1 - c), r)
    elif n % 2 and r != n // 2 and c == n // 2:
      change(c, max(r, n - 1 - r))
    else:
      change(c, r)
  if not diff_dic:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
  C, n = map(int, input().split())
  mp = [input() for _ in range(n)]
  diff_dic = {}

  def change(x, y):
    if (x, y) in diff_dic:
      diff_dic.pop((x, y))
    else:
      diff_dic[(x, y)] = True

  for y in range(n // 2):
    for x in range(n // 2):
      base = mp[y][x]
      if mp[y][n - 1 - x] != base:
        change(n - 1 - x, y)
      if mp[n - 1 - y][x] != base:
        change(x, n - 1 - y)
      if mp[n - 1 - y][n - 1 - x] != base:
        change(n - 1 - x, n - 1 - y)
  if n % 2:
    for x in range(n // 2):
      if mp[n // 2][x] != mp[n // 2][n - 1 - x]:
        chenge(n - 1 - x, n // 2)
    for y in range(n // 2):
      if mp[y][n // 2] != mp[n - 1 - y][n // 2]:
        change(n // 2, n - 1 - y)
  
  ans = 0
  if not diff_dic:
    ans += 1
  
  for _ in range(C - 1):
    d = int(input())
    for _ in range(d):
      r, c = map(int, input().split())
      r -= 1
      c -= 1
      if r < n // 2 and c < n // 2:
        change(c, n - 1 - r)
        change(n - 1 - c, r)
        change(n - 1 - c, n - 1 - r)
      elif n % 2 and r == n // 2 and c != n // 2:
        change(max(c, n - 1 - c), r)
      elif n % 2 and r != n // 2 and c == n // 2:
        change(c, max(r, n - 1 - r))
      else:
        change(c, r)
    if not diff_dic:
        ans += 1
  print(ans)
  
main()

Submission status: Accepted

Solution code:
def next(N, i):
    return ((N-i-1)+N)%N

def getState(N, G, i, j):
    return  G[i][j] == G[i][next(N, j)] and  G[i][j] == G[next(N, i)][j] and G[i][j] == G[next(N, i)][next(N, j)]

def getInit(N, G):
    dcnt = 0
    for i in range(N//2):
        for j in range(N//2):
            if not getState(N, G, i, j): dcnt += 1
    return dcnt

C, N = map(int, input().split())
#G = [[0]*N]*N
G = [['N' for _ in range(N)] for _ in range(N)]
for i in range(N):
    str = input()
    for j in range(N):
        G[i][j] = int(str[j])

ans = 0
dcnt = getInit(N, G)
if dcnt == 0: ans += 1

for i in range(C-1):
    k = int(input())
    for j in range(k):
        r, c = map(int, input().split())
        r -= 1
        c -= 1
        pre = getState(N, G, r, c)
        G[r][c] = 0 if G[r][c]== 1 else 1
        post = getState(N, G, r, c)
        if not pre and post: dcnt -= 1
        elif  pre and not post: dcnt += 1
    if dcnt == 0: ans += 1

print(ans)