Tenka1 Programmer Contest 2018 E - Equilateral

はてなブログたまに写真表示されなくならないか？

問題

h*wのグリッドがあり、いくつかのマスにはコインが置かれている
相異なるコイン3つの組のうち、どの2つのコイン同士のマンハッタン距離も同じであるようなものは何個あるか

1 <= h, w <= 300

解法

マンハッタン距離ってことでとりあえず45度回転して考える
2点X, Yの max(x座標の差, y座標の差) をdとすると、3点X, Y, Zが問題の条件を満たすには、X, Yそれぞれを中心とした1辺2dの正方形の交線上にZがある必要がある
↓はX, Yのx座標とy座標が共に異なり、共通範囲が点になる場合

結局↑のように3点のうち2点のx座標かy座標は等しくなることがわかる

よってx座標 or y座標が等しい2個のコインのペアを全て見て、この↑交線上にあるコインの個数を足し合わせていけばO(h^3 + w^3)で答えが得られる
ただし同一正方形の3 or 4角にコインがある場合は同じ組を重複カウントしてしまう
3角にコインがある正方形は1個につき1、4角の正方形は1個につき4だけ答えから引けばきれいに重複を消せる
(絵描いてみればわかる)

実装

重複を消すのは、x座標が等しい2点のペアを全部試す時に「同じ正方形の3角にコインがある」ことを確認する度に1引けばok
こうすれば3角の正方形は1回、4角の正方形では4回引っかかるからちょうど重複を消せる

hs: ヨコ方向の累積和
vs: タテ方向の累積和

int h, w, a[666][666], hs[666][666], vs[666][666], res;
string s[333];

signed main() {
	cin >> h >> w;
	rep(i,h) {
		cin >> s[i];
		rep(j,w) if (s[i][j]=='#') a[i+j+1][i-j+300] = 1;
	}
	reps(i,1,600) reps(j,1,600) {
		hs[i][j] += a[i][j] + hs[i][j-1];
		vs[i][j] += a[i][j] + vs[i-1][j];
	}
	reps(i,1,600) reps(j,1,600) reps(k,j+1,600) {
		int d = k-j;
		if (a[i][j] && a[i][k]) {
			if (i-d>=0) {
				res += hs[i-d][k] - hs[i-d][j-1];
				res -= a[i-d][j] + a[i-d][k];
			}
			if (i+d<=600) {
				res += hs[i+d][k] - hs[i+d][j-1];
				res -= a[i+d][j] + a[i+d][k];
			}
		}
		if (a[j][i] && a[k][i]) {
			if (i-d>=0) res += vs[k][i-d] - vs[j-1][i-d];
			if (i+d<=600) res += vs[k][i+d] - vs[j-1][i+d];
		}
	}
	cout << res << endl;
}

後からなら何でも言えるけどD捨てれば解けてた
まあ反省するべきはそれよりDが解けなかったことだな
構築っぽくて見ただけで拒否反応が出たけど閃きが必要な問題ではなかったから冷静に考えれば解けたはず
Cで割と萎えてたのはあると思う

https://beta.atcoder.jp/contests/tenka1-2018/tasks/tenka1_2018_e