kmjp's blog

競技プログラミング参加記です

yukicoder : No.606 カラフルタイル

ちょっと手間取った。
https://yukicoder.me/problems/no/606

問題

N*NのグリッドをK色で塗っていく。
初期状態で全セルは色1で塗られている。

ここにQ個のクエリが与えられる。
各クエリは、どこかの列か行を指定された色で上書きすることを意味している。

全クエリを処理したのち、各色のセル数はいくつかを答えよ。

解法

塗りつぶす問題は逆向きに処理すると簡単になることが多い。
この問題もそうである。
まず、同じ列・行を複数回塗る場合、そのようなクエリは最後の物だけ考えることにしよう。

あとはクエリを逆向きに考えていく。
列クエリを1個処理したとすると、それより前の行クエリは塗りつぶせる列の数が1個減る(後で1列塗りつぶされるから)。
行クエリに対しても逆にそれより前の列クエリは塗りつぶせる列の数が1個減る。

このように、最後まで塗った色が残るマスの数を考えつつクエリを逆向きに実行し、各色のマス数を数え上げよう。

int N,K,Q;
string A[201010];
int B[201010],C[201010];
int la[2][201010];

ll ret[201010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>Q;
	FOR(i,Q) {
		cin>>A[i]>>B[i]>>C[i];
		B[i]--;
		C[i]--;
		la[A[i]=="C"][B[i]]=i;
	}
	
	ll rc=N,rr=N;
	for(i=Q-1;i>=0;i--) {
		if(la[A[i]=="C"][B[i]]==i) {
			if(A[i]=="C") {
				ret[C[i]]+=rr;
				rc--;
			}
			else {
				ret[C[i]]+=rc;
				rr--;
			}
		}
	}
	ret[0]+=rc*rr;
	
	FOR(i,K) cout<<ret[i]<<endl;
	
	
}

まとめ

塗りつぶす系は逆順に処理、というテクは覚えておいて損はなさそう。