天下一プログラマーコンテスト2018 : E - Equilateral

45度回転はしなかったね…。
https://beta.atcoder.jp/contests/tenka1-2018/tasks/tenka1_2018_e

問題

グリッド上の一部に黒マスがある。
黒マスの３つの組で、互いのマンハッタン距離が一致するものは何組あるか。

解法

あるセルに対し、そこまでのマンハッタン距離がLである黒マスの３つ組のうち、黒マス通りの最短路のうち元のセルを通るものがあるケースを考える。
この場合、黒マス間の距離は2Lとなり条件を満たす。
３マスが元のセルを共通して最短路に含むには、３マスの位置関係が以下のいずれかでなければならない。

• 「*」マスを中心とし、３つの黒マスA,B,Cが一つは斜め、２つは縦か横の位置にある。

AAA....
AAA....
AAA....
...*BBB
...C...
...C...
...C...

• 「*」マスを中心とし、３つの黒マスA,B,Cはそこから上下左右の位置にある。

...A...
...A...
...A...
...*BBB
...C...
...C...
...C...

中央マス「*」と距離Lを総当たりし、A,B,Cに含まれる黒マスを数え上げよう。

int H,W;
string S[303];

int R[2003][2003];
int L[2003][2003];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	FOR(y,2000) FOR(x,2000) {
		if(y&&x) R[y][x]=R[y-1][x-1];
		if(y) L[y][x]=L[y-1][x+1];
		if(y-700>=0 && y-700<H && x-700>=0 && x-700<W) {
			R[y][x]+=S[y-700][x-700]=='#';
			L[y][x]+=S[y-700][x-700]=='#';
		}
		
	}
	
	ll ret=0;
	FOR(y,H) FOR(x,W) {
		for(l=1;l<=300;l++) {
			int num[11]={};
			if(y-l>=0) num[8]=S[y-l][x]=='#';
			if(y+l<H) num[2]=S[y+l][x]=='#';
			if(x-l>=0) num[4]=S[y][x-l]=='#';
			if(x+l<W) num[6]=S[y][x+l]=='#';
			num[7]=L[y+700][x-l+700]-L[y-l+700][x+700]-num[4];
			num[3]=L[y+l+700][x+700]-L[y+700][x+l+700]-num[2];
			num[9]=R[y+700][x+l+700]-R[y-l+700][x+700]-num[6];
			num[1]=R[y+l+700][x+700]-R[y+700][x-l+700]-num[2];
			ll p=ret;
			ret+=num[2]*(num[6]*num[8]+num[4]*num[8]+num[4]*num[6]);
			ret+=num[4]*num[6]*num[8];
			ret+=num[1]*num[6]*num[8];
			ret+=num[3]*num[4]*num[8];
			ret+=num[9]*num[2]*num[4];
			ret+=num[7]*num[2]*num[6];
		}
	}
	
	cout<<ret<<endl;
}

まとめ

45度回すのは特に考えなかったなぁ。