はまやんはまやんはまやん

hamayanhamayan's blog

Flip,Flip, and Flip...... [AtCoder Regular Contest 091 C]

https://beta.atcoder.jp/contests/arc091/tasks/arc091_a

解説

https://beta.atcoder.jp/contests/arc091/submissions/2183749

  • 盤面が大きすぎるのでシミュレートできない
  • 縦も横も大きすぎるので、どちらかでなにかしらの全探索もできない
  • 300点問題である

このあたりから、場合分けによる解法かなという当たりがつく
 
N>Mの場合はスワップして、N≦Mとしておこう。
(場合分けが想定解の場合はこうすると場合分けが減って楽になったりする)
N=M=1の場合は黒が1つになる。
N=1, 1<Mの場合は、端は2回フリップでそれ以外は3回フリップとなるので、M-2が答え。
 
それ以外は、

  • 四隅は4回フリップなので白
  • 四隅以外の端は6回フリップなので白
  • それ以外は9回フリップなので黒

となるので、(N-2)*(M-2)が答えになる。

ll N, M;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    if (N > M) swap(N, M);
 
    ll ans;
    if (N == 1) {
        if (M == 1) ans = 1;
        else ans = M - 2;
    } else {
        ans = (N - 2) * (M - 2);
    }
    cout << ans << endl;
}