めちゃ面白い！
問題概要
オセロにおいて、黒石が 1 個だけない状態からスタートする。
........ ........ ........ ...ox... ....o... ........ ........ ........
ここから通常のオセロルールでプレイする。今、 個のクエリが投げられ、各クエリではオセロ版のうちの長方形部分領域が指定される。オセロを通常プレイで「先手後手ともに石が置けない」という状態になったときの、長方形領域に置かれている石の個数として考えられる最大値を求めよ。
制約
解法
てんぷらたんがエスパーしてくれた！！！
下図の 'o' の部分には置けて、'.' の部分には置けない
o.o.o.o. oooooo o.o.o.o. oooooo o.o.o.o. oooooo o.o.o.o. oooooo
気づいてしまえばそれはそうで、'.' の位置に置くためには、他の '.' の位置に置かれていなければならない。実際はどの '.' の位置にも一度も置かれずにエンドとなることがわかる。
逆に 'o' の位置には置かれることがありうることは、実験なり手なりで確かめることができる。
#include <iostream> #include <vector> #include <string> using namespace std; int main() { int Q; cin >> Q; for (int q = 0; q < Q; ++q) { int a, b, c, d; cin >> a >> b >> c >> d; --a, --b, --c, --d; int res = 0; for (int i = a; i <= c; ++i) { for (int j = b; j <= d; ++j) { if (i % 2 == 0 && j % 2 == 1) continue; ++res; } } cout << res << endl; } }
