ABC090 C - Flip,Flip, and Flip...... - ペンギンかっこいい

備忘録

問題

回答

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()

    if N == 1 and M == 1:
        print(1)
    elif N == 1:
        print(M - 2)
    elif M == 1:
        print(N - 2)
    else:
        print((N - 2) * (M - 2))


if __name__ == '__main__':
    main()

考え方

各カードは自身に接しているカードの枚数+1(自分自身）だけ裏返される、
このことを元に、起こり得るパターンを列挙する。

まず、操作終了時にカードが裏返しの場合について考える。
カードは表から始まり、1度の操作で裏返され（裏向き）、
もう一度操作されると裏返される（表向きに戻る）。
このことから、カードに対する操作が偶数回の場合には表向き、奇数階の場合には裏向きになることがわかる。

次に、並べられた各カードが何度操作されるかについて考える。
実際に手元で書いてシミュレートしてみるとわかりやすいが、
各カードは自身の周囲に置かれたカード+1回だけ操作される。
そのため、N = 3, M = 3などの場合には、

# 各数字の配置はカードの位置
# 数値は操作された回数
# 操作開始前
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
#操作終了後
[[4, 6, 4],
 [6, 9, 6],
 [4, 6, 4]]

のように、4つの隅は4回操作され、1辺は6回、それ以外のマスは9回操作される。
このことから回答は(N-2)*(M-2)となる。
ただし、N=1またはM=1（あるいはその両方）のときは回答に注意が必要となる。