SRM 562 DIV1 Easy - PastingPaintingDivOne （復習○）

August 18, 2013

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12317&rd=15184

長方形の模様が与えられる。

模様はの各セルはＲ，Ｇ，Ｂのいずれかの色、もしくは．で表わされる透明のセルで
構成される。

最初は左上に重なるように模様がスタンプされ、次は左上の座標を右に１、下に１移動させてスタンプする。

Ｔ回スタンプしたとき、Ｒ，Ｇ，Ｂの数を求める。

解き方

Ｔが１０＾９のため、スタンプごとに全探索しては解けない。

ここでスタンプされた時のＲＧＢの変化は、
高さ分の回数スタンプした後は常に一定になることがわかれば
それ以降の回数×Ｔ×ＲＧＢそれぞれの増加数、で解くことができる。

コード

class PastingPaintingDivOne {

public: vector<long long> countColors(vector<string> clipboard, int T) {
char check[200][200];
vector<long long> ans(3,0);
int h=clipboard.size(),w=clipboard[0].size();
long long pr=0,pg=0,pb=0;

FORE(i,0,200)FORE(j,0,200)check[i][j]='.';

FORE(n,0,h){
T--;
FORE(i,n,h+n)FORE(j,n,w+n)if(clipboard[i-n][j-n]!='.')check[i][j]=clipboard[i-n][j-n];
ans[0]=ans[1]=ans[2]=0;
FORE(i,0,200)FORE(j,0,200){
if(check[i][j]=='R')ans[0]++;
if(check[i][j]=='G')ans[1]++;
if(check[i][j]=='B')ans[2]++;
}
if(T==0)return ans;
}

FORE(i,h,clipboard.size()+h)FORE(j,h,clipboard[0].size()+h)if(clipboard[i-h][j-h]!='.')check[i][j]=clipboard[i-h][j-h];
FORE(i,0,200)FORE(j,0,200){
if(check[i][j]=='R')pr++;
if(check[i][j]=='G')pg++;
if(check[i][j]=='B')pb++;
}
pr-=ans[0],pg-=ans[1],pb-=ans[2];
ans[0]+=pr*T,ans[1]+=pg*T,ans[2]+=pb*T;

return ans;
}

};

考察