ARC091 C : Flip,Flip, and Flip......(300)
作成日：2018.03.14
最終更新日：2018.03.14
問題概要
$N$行$M$列のマス目にカードが表向きで置かれている。
全てのマスに対して、そのマス自身とそのマスに1点以上で接しているマスにあるカードを裏返すという操作を行う。
最終的に裏を向いているカードの枚数を求めよ。
制約
$1 \leq N,M \leq 10^9$
考え方
ある1枚のカードが最終的に裏を向いているのは、奇数回裏返された時である。
これは$8$方向に隣接しているカードの数に$1$を足したものが奇数であることと同じである。
$N,M \geq 2$の時、隣接するカードの枚数は角のカードで$3$枚、辺のカードで$5$枚、それ以外のカードで$8$枚である。
これに$1$を加えたものが奇数となるのは、角でも辺でもない位置にあるカードのみであるから、答えは$(N-2)(M-2)$である。
$(N,M)=(1,a),(a,1)$の時、$a$枚のカードのうち端にあるものに隣接するのは$1$枚、そうでないものに隣接するのは$2$枚である。
よって答えは$a-2$となる。但し$a=1$の時の答えが$1$になることに注意する。
ソースコード
マクロ等はこちら
LL N,M;
int main(){
cin >> N >> M;
if(N == 1 || M == 1){
if(N+M==2) cout << 1 << endl;
else cout << N+M-3 << endl;
} else {
cout << (N-2) * (M-2) << endl;
}
return 0;
}解法まとめ
$N,M \geq 2$の時は$(N-2)(M-2)$、$N=M=1$の時は$1$、それ以外の時は$N,M$のうち$1$出ない方を$a$とすると$a-2$が答えである。(5-11行)