2012 WUPC2 : I - その味は甘くて

新年になりましたが、ようやくWUPC2のIの解説が出たのでチャレンジ。
http://wupc2nd.contest.atcoder.jp/tasks/wupc_09

ハニカム状のマス目に、指示に従って整数値（糖度）を増していき、糖度の最大値を求める。
いわゆるimos法の典型例。

部分点50は自前でもできた。
部分点50では、type=1(六角形状のマスに糖度を１追加する)だけ。
指示がN通り、六角形の最大半径がSとする。
なので、左から右にimos法を実行すると１つ六角形の糖度を追加するのにSかかるので、糖度の追加にO(NS)、最後の足し合わせがO(S^2)程度となる。

以下部分点50の回答例。
六角形の上半分と下半分の左端で+1、右端で-1して、最後に累積和を取る。

int N;
int types[3][2002][2002];


void solve() {
	int t,x,y,z,i,j,rr,TM;
	int tx,ty,dy;
	ll res,p,tp;
	
	N=GETi();
	ZERO(types);
	FOR(i,N) {
		t=GETi();
		x=GETi()+1000;
		y=GETi()+1000;
		z=GETi();
		if(t==1) {
			for(dy=-(z-1);dy<=(z-1);dy++) {
				ty=y+dy;
				if(dy>=0) {
					types[0][ty][x-(z-1)]++;
					types[0][ty][x+(z-1)-dy+1]--;
				}
				else {
					types[0][ty][x-(z-1)-dy]++;
					types[0][ty][x+z]--;
				}
			}
		}
		else return;
	}
	
	res=0;
	ll ti1;
	FOR(y,2001) {
		ti1=0;
		FOR(x,2001) {
			ti1+=types[0][y][x];
			res=max(res,ti1);
		}
	}
	_P("%lld\n",res);
	return;
}

続いて満点回答。
先と同じtype=1の高速化を試みる。
１方向のimos法だと、１つ六角形を追加するのにO(S)かかる。
ただ、解説の様に３方向のimos法を取ると、O(1)で処理できるので、N個の指示に対しO(N)または足しあわせのO(S^2)の処理で間にあう。

解説を見ると、type=2・type=3の指示をO(1)で処理する方法が書いてあるが、１処理O(S)で良ければこれより簡単に処理できる。
実際先の１方向imos法では１処理O(S)、全部でO(NS)で終わっているので、簡単な方でやってみる。
type=2・3の指示は、ピラミッド状に六角形の中心ほど高い糖度が加わるが、以下のようにtype=1の和で考えられる。

• type=2のS=3の六角形の糖度＝(S=iの大きさの六角形の範囲に糖度1を加算）
• type=2のS=3の六角形の糖度＝(S=iの大きさの六角形の範囲に糖度(S*2-i)を加算）

１つのtype=1の六角形の糖度加算がO(1)なので、これらはO(S)で処理でき、N個の指示もO(NS)で処理できる。

他の人の回答みたら、解説よりもこちらの方法を取る人が多かったね。
解説の方法は1指示O(1)、こちらはO(S)なので、時間制限がシビアだと解説の方法を取らないとだめだけどね。
でもこちらの方が解き方としてはわかりやすいと思う。

int N;
ll types[2][2002][2002];

void solve() {
	int t,x,y,z,i,j,r,k,TM;
	int tx,ty,dy;
	ll res,p,tp;
	
	N=GETi();
	ZERO(types);
	FOR(i,N) {
		t=GETi();
		x=GETi()+1000;
		y=GETi()+1000;
		r=GETi();
		for(j=1;r>0;r--) {
			types[0][x-r+1][y]+=j;		types[0][x-r+2][y]-=j;
			types[0][x+r][y]+=j;			types[0][x+r+1][y]-=j;
			types[0][x+1][y+r]+=j;		types[0][x+1][y+r-1]-=j;
			types[0][x-r+2][y+r-1]+=j;	types[0][x-r+1][y+r]-=j;
			types[0][x+r+1][y-r]+=j;		types[0][x+r][y-r+1]-=j;
			types[0][x+1][y-r+1]+=j;		types[0][x+1][y-r]-=j;
			if(t==1) break;
			if(t==3) j+=2;
		}
	}
	
	
	// 右上に累積
	FOR(x,2001) {
		p=0;
		FOR(y,2001) types[1][x][y]=(p+=types[0][x][y]);
	}
	
	// 右下に累積
	FOR(r,4001) {
		p=0;
		if(r<=2000) for(x=0,y=r;y>=0;y--,x++) types[0][x][y]=(p+=types[1][x][y]);
		else for(x=r-2000,y=2000;x<=2000;y--,x++) types[0][x][y]=(p+=types[1][x][y]);
	}
	//右に累積
	res=0;
	FOR(y,2001) {
		p=0;
		FOR(x,2001) res=max(res,types[1][x][y]=(p+=types[0][x][y]));
	}
	
	_P("%lld\n",res);
	return;
}
||>

*まとめ

複数方向に実行するimos法、まだ習得できてないので練習しないとな。