AtCoder RC091 C: Flip,Flip, and Flip......

実際にカードの反転処理をシミュレートして解こうとすると、計算量がO(N²)になってしまって現実的では無いです。

そのため、計算で解くことにします。

まず基本的な考え方です。最初はカードは表を向いているので、全ての操作を終えた後に「カードを偶数回操作していたら表」「カードを奇数回操作していたら裏」となります。

カードの操作回数＝カードが隣接（上下左右と斜め方向）するカードの枚数＋1（自分）

これをカードの場所毎に場合分けして考えると、

・周囲が全て囲まれている場合：9回（奇数）・四隅：4回（偶数）・端：6回（偶数）

具体例として5x5のケースのを見てみると、以下のようになります。

偶偶偶偶偶
偶奇奇奇偶
偶奇奇奇偶
偶奇奇奇偶
偶偶偶偶偶

つまり、5ｘ5の場合は、(5 - 2) x (5 - 2) = 9 となります。よって、NとMが3以上の場合は、(N - 2) x (M - 2)で一般化できます。

これを表にまとめると、以下のようになります。

あとは、NとMの場合分けで実装・・・ということになるのですが、もっとシンプルにすることが出来ます。

まず、NまたはMが2の場合、(N - 2) x (M - 2) は0になります。また、N=1かつM=1の場合は、(-1) x (-1) = 1になります。よってこの場合は一般化した式がそのまま使えます。

残りの「N=1かつMが3以上」と「Nが3以上かつM=1」の場合ですが、これはそのまま一般化した式で計算すると値が負になるのですが、符号を反転させればそれが正解になります。

よって、全てのケースについて、(N - 2) x (M - 2) の絶対値を返すことで結果が得られます。

ほぼワンライナーのようなコードになりました。

n, m = gets.split.map{|v|
  v.to_i
}

p ((n - 2) * (m - 2)).abs