AtCoder ABC #280 (デンソークリエイトプログラミングコンテスト2022 Winter) : G - Do Use Hexagon Grid 2

hexが出てくると頭が混乱する。
https://atcoder.jp/contests/abc280/tasks/abc280_g

問題

ヘックス状にセルが並んだグリッドがある。
うち、N個のセルの位置が指定されている。
N個セルの部分集合のうち、互いのセル同士の距離がD以下となるものは何通りか。

解法

X座標が最小となるセル(のうちY座標が最小となるもの)とY座標が最小となるセル(のうちX座標が最小となるもの)を総当たりしよう。
上記2セルの座標を、(X[a],Y[a])と(X[b],Y[b])とする。(なお、a=bとなることもある)。
まずこの2マスが距離D以内でないといけないので、(X[b]-X[a])+(Y[b]-Y[a])≦Dであることを確認する。

他の点vについて、X[b]≦X[v]≦X[b]+DかつY[a]≦Y[v]≦Y[a]+Dのものを列挙しよう。
あと残るは、選んだ頂点について、Y[v]-X[v]の範囲がD以下に収まるように選びたい。
そこで、列挙した頂点をY[v]-X[v]でソートし、尺取り法の要領で、条件を満たせる点の数を数えていこう。

const ll mo=998244353;
int N;
ll X[303],Y[303];
ll D;
ll p2[303];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>D;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
	}
	p2[0]=1;
	FOR(i,301) p2[i+1]=p2[i]*2%mo;
	
	ll ret=0;
	FOR(x,N) FOR(y,N) {
		if(x!=y) {
			if(Y[x]>=Y[y]||X[x]<=X[y]) continue;
		}
		ll a=Y[x]-X[x];
		ll b=Y[y]-X[y];
		if(a>b) swap(a,b);
		if(abs(a-b)>D) continue;
		vector<ll> V;
		FOR(i,N) {
			if(i==x) continue;
			if(i==y) continue;
			if(Y[i]==Y[x]&&X[i]<X[x]) continue;
			if(X[i]==X[y]&&Y[i]<Y[y]) continue;
			if(X[i]<X[y]||X[i]>X[y]+D) continue;
			if(Y[i]<Y[x]||Y[i]>Y[x]+D) continue;
			V.push_back(Y[i]-X[i]);
		}
		sort(ALL(V));
		FOR(i,V.size()) {
			ll v=V[i];
			if(v>a) break;
			if(v+D<b) continue;
			k=lower_bound(ALL(V),v+D+1)-V.begin()-i;
			ret+=p2[k-1];
		}
		k=lower_bound(ALL(V),a+D+1)-lower_bound(ALL(V),a+1);
		ret+=p2[k];
		
	}
	cout<<ret%mo<<endl;
	
}

まとめ

Hexを書くとき、横方向のセルが直線上に並ぶ書き方と、縦方向のセルが直線上に並ぶ書き方どっちが多いんだろうな。
自分は最初にHexに長時間触れた記憶が光栄の三国志の戦争シーンなので、後者の印象が強いんだよな。