Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

A. Little Artem (Codeforces Round #632 Div. 2)

想定解を見てひっくり返りました。

問題

https://codeforces.com/contest/1333/problem/A

問題概要

n \times mのマス目がある。これの各マスを白と黒に塗り分ける。

白いマスに隣接している黒いマスが、黒いマスに隣接している白いマスの数よりひとつ多くなるように塗り分けよ。

考察

第一感、市松模様でいい感じになるんじゃない?と思って、市松模様を投げたらダメでした。

いや、そこはちゃんと考えろ自分・・・。

というわけで考え直すと、n \times mが奇数のときは、黒を一つ多く配置できるためたしかに市松模様でよいのですが、偶数の時は数が一致してしまいます。

で、もうちょっと考えると、任意の白いマスを1つだけ黒にしてしまうとよいことがわかります。この操作で「黒いマスに隣接している白いマス」は1つ減り、置き換えたあとの黒マスは黒にしか隣接していないので「白いマスに隣接している黒いマス」の数は増えないからです。

BWBW
WBWB
BWBW

BBBW
WBWB
BWBW

というような要領です。

(実戦では実装をバグらせて2WAを出しつつ)これで通しました。

実は・・・

コンテスト直後にTwitterをみてひっくり返りました。なんと左上にひとつだけ白を置き、後はすべて黒を置くと、題意を満たすというのです!

WBBB
BBBB
BBBB

ほんまや・・・。