kmjp's blog

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

Codeforces #394 Div2 F. Dasha and Photos

Codeforces

とにかく累積和を駆使しまくる問題。
http://codeforces.com/contest/761/problem/F

問題

N*Mの2次元グリッドで表現された写真がある。
各ピクセルは26(=W)色のいずれかで塗られている。

ここでK個のクエリが与えられる。
各クエリは、グリッドの一部の矩形範囲をある色で上書きすることを示す。

各クエリは独立であり、それぞれ異なる写真を生成する。
写真の差分とは、各ピクセルの色の値の差の絶対の総和とする。
K個の写真のうち、自身と他の(K-1)個の写真との差分の総和の最小値を求めよ。

解法

まず2次元の累積和を用いて、各ピクセルがクエリによって何色に代わるものが何枚ずつになるかを求めよう。
この手順はO(NM+K)で済む。

ここから、各ピクセルに対し以下を求める。この手順はO(NMW)である。

  1. 写真の内容が各色cに上書きされた場合に対し、そのピクセルと他のK枚の写真群色の差の総和。(愚直に行うとO(NMW^2)かかるが、TLEするので色値に対する累積和を用いO(NMW)に抑えよう)
  2. 写真の内容が上書きされない場合に対し、そのピクセルと他のK枚の写真群色の差の総和。

また、これらの結果を2次元座標に対し累積和を求めておこう。これもO(NMW)で済む。

ここまで前準備を行い、ようやく各写真と他の(K-1)枚の写真の写真との差分の総和を総当たりしていこう。
各クエリに対し、色を上書きしない部分は当然元の色のままである。
よって前述の#2の値を用い、その部分の色の差異の総和を求めよう。
色を上書きした部分は、#1を用い色の際の総和を求める。
上記処理は累積和を事前に準備しておけばクエリ毎にO(1)で済む。

よって全体ではO(K+NMW)である。
気を付けないとMLEになるので注意。64bit値をN*M*W分準備すると200MBを超えるので、そのようなデータ構造は2つまでしか取れない。

int H,W,K;
string S[1010];

int num[1010][1010][27];

int R0[303030];
int C0[303030];
int R1[303030];
int C1[303030];
char C[303030];

ll difsum[1010][1010];
ll difsum2[1010][1010];
int col[1010][1010][26];
ll colsum[1010][1010][26];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) S[y][x]-='a';
	}
	num[0][0][26]=K;
	num[H][W][26]=K;
	num[H][0][26]=-K;
	num[0][W][26]=-K;
	
	FOR(i,K) {
		cin>>R0[i]>>C0[i]>>R1[i]>>C1[i]>>C[i];
		R0[i]--;
		C0[i]--;
		R1[i]--;
		C1[i]--;
		C[i]-='a';
		num[R0[i]][C0[i]][C[i]]++;
		num[R0[i]][C1[i]+1][C[i]]--;
		num[R1[i]+1][C0[i]][C[i]]--;
		num[R1[i]+1][C1[i]+1][C[i]]++;
		
		num[R0[i]][C0[i]][26]--;
		num[R0[i]][C1[i]+1][26]++;
		num[R1[i]+1][C0[i]][26]++;
		num[R1[i]+1][C1[i]+1][26]--;
	}
	FOR(y,H) FOR(x,W) FOR(i,27) {
		if(y) num[y][x][i] += num[y-1][x][i];
		if(x) num[y][x][i] += num[y][x-1][i];
		if(y&&x) num[y][x][i] -= num[y-1][x-1][i];
	}
	
	FOR(y,H) FOR(x,W) {
		num[y][x][S[y][x]] += num[y][x][26];
		ll nu=0,sum=0;
		for(i=25;i>=0;i--) {
			col[y][x][i] += sum;
			nu += num[y][x][i];
			sum += nu;
		}
		nu=0,sum=0;
		FOR(i,26) {
			col[y][x][i] += sum;
			colsum[y+1][x+1][i]=colsum[y+1][x][i]+colsum[y][x+1][i]-colsum[y][x][i]+col[y][x][i];
			nu += num[y][x][i];
			sum += nu;
		}
	}
	FOR(y,H) FOR(x,W) {
		FOR(i,26) difsum[y][x]+=1LL*abs(S[y][x]-i)*num[y][x][i];
		difsum2[y+1][x+1]=difsum2[y+1][x]+difsum2[y][x+1]-difsum2[y][x]+difsum[y][x];
	}
	
	ll mi=1LL<<60;
	FOR(i,K) {
		ll v = difsum2[H][W];
		v -= difsum2[R1[i]+1][C1[i]+1]-difsum2[R0[i]][C1[i]+1]-difsum2[R1[i]+1][C0[i]]+difsum2[R0[i]][C0[i]];
		v += colsum[R1[i]+1][C1[i]+1][C[i]]-colsum[R0[i]][C1[i]+1][C[i]]-colsum[R1[i]+1][C0[i]][C[i]]+colsum[R0[i]][C0[i]][C[i]];
		mi=min(mi,v);
	}
	cout<<mi<<endl;
	
	
	
}

まとめ

累積和の練習になった。