TopCoder SRM 562 Div1 Easy PastingPaintingDivOne

さてDiv1のeasy。
試しに解いてみたらスコアが200点以上取れていたので、本参加してたらランク上がってたな…。
http://community.topcoder.com/stat?c=problem_statement&pm=12317

RGBで構成されるスタンプを少しずつ位置をずらしながら押した場合、最後のRGBのマスの数を答える問題。
スタンプを押す回数は最大10^9なので、シミュレーションは無理。

ここでスタンプサイズは最大50x50なので、50回目以降のスタンプ押下は１回あたりのRGBの増減分が固定される。
以下のコードでは、100回までは実際にシミュレーションし、それ以上は１回あたりのRGBの増減分から計算した。

class PastingPaintingDivOne {
	public:
	int cb[51][51];
	int sim[201][201];
	int W,H;
	ll N[102][4];
	vector<long long> countColors(vector <string> clipboard, int T) {
		vector<long long> res;
		ZERO(cb);
		H=clipboard.size();
		W=clipboard[0].size();
		
		int x,y;
		
		T--;
		FOR(y,H) FOR(x,W) {
			if(clipboard[y][x]=='.') cb[y][x]=0;
			if(clipboard[y][x]=='R') cb[y][x]=1;
			if(clipboard[y][x]=='G') cb[y][x]=2;
			if(clipboard[y][x]=='B') cb[y][x]=3;
		}
		ZERO(N);
		int loop;
		ZERO(sim);
		FOR(loop,((T>101)?102:T+1)) {
			FOR(y,H) FOR(x,W) {
				if(cb[y][x]) sim[y+loop][x+loop]=cb[y][x];
			}
			FOR(y,201) FOR(x,201) N[loop][sim[y][x]]++;
		}
		
		if(T<=101) {
			res.push_back(N[T][1]);
			res.push_back(N[T][2]);
			res.push_back(N[T][3]);
		}
		else {
			res.push_back(N[101][1] + (N[101][1]-N[100][1])*((ll)T-101));
			res.push_back(N[101][2] + (N[101][2]-N[100][2])*((ll)T-101));
			res.push_back(N[101][3] + (N[101][3]-N[100][3])*((ll)T-101));
		}
		
		return res;
		
	}

};

まとめ

すんなりアルゴリズムが思いつけて良かった。