Codeforces #355 Div2 E. Vanya and Balloons

体調悪かったのでさっさと書いてデバッグせずSubmitして寝たけど、AC出来て良かった。
http://codeforces.com/contest/677/problem/E

問題

0,1,2,3のいずれかが書かれたグリッドが与えられる。
ここから＋または×型のセル群を選択する(詳細は問題分参照)。

セル群に含まれる数値の積の最大値はいくつか。

解法

0が書かれたセルを選択すると明らかに損だが、それ以外は選べば選ぶほど得をする。

まず前準備として、左右・上下・斜め方向に対し以下をそれぞれ求めよう。

• 0,1,2,3の登場回数の累積和を求め、上下左右斜めの連続セル群中の0,1,2,3の数をO(1)で求める準備をする。
• 左右上下斜めに最大何マス0以外のマスが来るか計算しておく。

あとは各マスが＋・×の中心となるようなケースを総当たりし、求める値がいくつになるか求めよう。
上下左右及び斜め方向に何マス非0セルがあるかは計算済みなので、各セルを中心と下最適な＋や×型の大きさはわかる。
また、2,3の登場回数の累積和がわかるので、選択セル群中の2,3の数もわかる。

2,3がセル群中にx,y個登場すると、それらの積は2^x*3^yとなる。
問題は、x,yは2000まで行くので64bitでは収まらず、様々な中心セルに対し、どの(2^x*3^y)が最大かわからなくなってしまう。
対策として、(2^x*3^y)ではなくその対数を覚えておいて比較するとよい。
x,yが2000以下のケースでは、対数がdouble型の誤差の範囲に収まるような異なる２値はないようだ。

int N;
int A[1010][1010];
int SH[4][1010][1010];
int SV[4][1010][1010];
int Ssl[4][1010][1010];
int Srev[4][1010][1010];
int L[1010][1010];
int R[1010][1010];
int U[1010][1010];
int D[1010][1010];
int UL[1010][1010];
int UR[1010][1010];
int DL[1010][1010];
int DR[1010][1010];
ll mo=1000000007;
string S;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) {
		cin>>S;
		FOR(x,N) A[y][x]=S[x]-'0';
	}
	FOR(i,4) {
		FOR(y,N) FOR(x,N) {
			SH[i][y+1][x+1]=SH[i][y+1][x]+(A[y][x]==i);
			SV[i][y+1][x+1]=SV[i][y][x+1]+(A[y][x]==i);
			Ssl[i][y+1][x+1]=Ssl[i][y][x+2]+(A[y][x]==i);
			Srev[i][y+1][x+1]=Srev[i][y][x]+(A[y][x]==i);
		}
	}
	FOR(y,N) FOR(x,N) {
		L[y+1][x+1]=(A[y][x]==0)?0:(1+L[y+1][x]);
		UL[y+1][x+1]=(A[y][x]==0)?0:(1+UL[y][x]);
		UR[y+1][x+1]=(A[y][x]==0)?0:(1+UR[y][x+2]);
	}
	FOR(y,N) for(x=N-1;x>=0;x--) R[y+1][x+1]=(A[y][x]==0)?0:(1+R[y+1][x+2]);
	FOR(x,N) FOR(y,N) U[y+1][x+1]=(A[y][x]==0)?0:(1+U[y][x+1]);
	FOR(x,N) for(y=N-1;y>=0;y--) D[y+1][x+1]=(A[y][x]==0)?0:(1+D[y+2][x+1]);
	for(y=N-1;y>=0;y--) FOR(x,N) {
		DL[y+1][x+1]=(A[y][x]==0)?0:(1+DL[y+2][x]);
		DR[y+1][x+1]=(A[y][x]==0)?0:(1+DR[y+2][x+2]);
	}
	
	double ma=-3;
	int p2=0,p3=0;
	FOR(y,N) FOR(x,N) if(A[y][x]!=0) {
		int mc=min(min(L[y+1][x+1],R[y+1][x+1]),min(U[y+1][x+1],D[y+1][x+1]));
		int t[4]={};
		for(i=2;i<=3;i++) t[i]=SH[i][y+1][x+1+mc-1]-SH[i][y+1][x+1-mc]+SV[i][y+1+mc-1][x+1]-SV[i][y+1-mc][x+1] - (A[y][x]==i);
		double dt=t[2]*log(2)+t[3]*log(3);
		if(dt>ma) ma=dt, p2=t[2], p3=t[3];
		
		mc=min(min(UL[y+1][x+1],UR[y+1][x+1]),min(DL[y+1][x+1],DR[y+1][x+1]));
		for(i=2;i<=3;i++) t[i]=Srev[i][y+1+mc-1][x+1+mc-1]-Srev[i][y+1-mc][x+1-mc]+Ssl[i][y+1+mc-1][x+1-(mc-1)]-Ssl[i][y+1-mc][x+1+mc] - (A[y][x]==i);
		dt=t[2]*log(2)+t[3]*log(3);
		if(dt>ma) ma=dt, p2=t[2], p3=t[3];
		
	}
	
	if(ma<-2) cout<<0<<endl;
	else {
		ll ret=1;
		FOR(i,p2) ret=ret*2%mo;
		FOR(i,p3) ret=ret*3%mo;
		cout<<ret<<endl;
	}
}

まとめ

面倒なだけだし＋と×どっちかだけで良かったんじゃないかな…。