CODE THANKS FESTIVAL 2014 A : E - 儀式

Code thanks festivalにオープン参加。
最終問題が部分点どまりでそこそこの順位。
A～Dはやさしめなので省略。
http://code-thanks-festival-2014-a-open.contest.atcoder.jp/tasks/code_thanks_festival_14_quala_e

問題

R*C個の長方形状に石像が並んでいる。
初期状態では皆石像が南を向いている。

ここでN個のクエリが与えられる。
各クエリは長方形領域を示しており、その範囲の石像を90度時計回りに回転させることを意味する。

N個クエリを完了したつもりののち、南を向いた石像はM個であった。
ただし、ここで実はN個のクエリのうち１つスキップしていたことがわかった。
スキップしていた可能性のあるクエリ番号を列挙せよ。

解法

いわゆる巻き戻すDP。

とりあえずN個のクエリをすべて実行する。
そののち、１個クエリを巻き戻して南を向く石像の数がM個かチェックすればよい。
R*Cは小さいので、クエリに対する石像の回転は累積和など取らなくても間に合う。

int R,C,M,N;
int G[102][102];
int RR[2][10000],CC[2][10000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>R>>C>>M>>N;
	FOR(i,N) {
		cin>>RR[0][i]>>RR[1][i]>>CC[0][i]>>CC[1][i];
		RR[0][i]--;
		RR[1][i]--;
		CC[0][i]--;
		CC[1][i]--;
		for(y=RR[0][i];y<=RR[1][i];y++) for(x=CC[0][i];x<=CC[1][i];x++) G[y][x]++;
	}
	
	FOR(i,N) {
		for(y=RR[0][i];y<=RR[1][i];y++) for(x=CC[0][i];x<=CC[1][i];x++) G[y][x]--;
		j=0;
		FOR(y,R) FOR(x,C) j+=G[y][x]%4==0;
		if(j==M) cout<<i+1<<endl;
		for(y=RR[0][i];y<=RR[1][i];y++) for(x=CC[0][i];x<=CC[1][i];x++) G[y][x]++;
	}
}

まとめ

昔ARCで巻き戻すDPの問題が解けなかったけど、こちらはわかりやすいね。