SRM562 Div1 Easy - PastingPaintingDivOne

問題

エディタで絵を書く
最初キャンバスは全てのマスが透明で、クリップボードにはh*wの長方形の絵sが入っている
絵の各マスの色は赤か緑か青か透明で、キャンバス上のある位置にこれを貼り付けると、絵の色付きのマスが乗るマスはその色で上書きされ、透明なマスが乗るマスは何も変わらない
キャンバスに絵をk回連続で貼り付け、i回目はマス(i,i)を左上の端とするように貼り付ける
最終的にキャンバス上の赤・緑・青のマスはそれぞれ何個になるか求めよ

1 <= h, w <= 50
1 <= k <= 10^9

解法

i回目に貼り付ける絵に影響(上書き)し得るのはi+1回目の絵からi+min(h,w)-1回目の絵まで
つまりi+min(h,w)-1 = k ∴ i = k-min(h,w)+1 回目の絵までは全て同じ影響を受ける
t: sの「左上を(i,i) (1<=i<=min(h,w)に合わせて絵を貼り付けるときに上書きされるマス」を全て'.'にしたもの
として、tでのRGBをカウントし、それらをk-min(h,w)+1倍する
更に残りmin(h,w)-1回は普通にシミュレーションすればok

bool ool(int x,int y,int h,int w) {return((x<0)||(h<=x)||(y<0)||(w<=y));}

class PastingPaintingDivOne {
public:
	vector<ll> countColors(vector<string> s, int k) {
		map<char,int> con = {{'R',0}, {'G',1}, {'B',2}};
		int h = s.size(), w = s[0].size();
		vector<string> t = s;
		reps(d,1,min(h,w)) rep(i,h) rep(j,w)
			if (s[i][j]!='.' && !ool(d+i,d+j,h,w)) t[d+i][d+j] = '.';
		vector<ll> res(3);
		each(i,t) each(j,i) if (j!='.') res[con[j]]++;
		each(i,res) i *= max(k-min(h,w)+1, 0);
		char p[111][111] = {};
		memset(p, '.', sizeof(p));
		rep(d,min(min(h,w)-1, k)) rep(i,h) rep(j,w) if (s[i][j]!='.') p[d+i][d+j] = s[i][j];
		rep(i,111) rep(j,111) if (p[i][j]!='.') res[con[p[i][j]]]++;
		return res;
	}
};

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