yukicoder : No.1121 Social Distancing in Cinema

これは何とか思いつけた。
https://yukicoder.me/problems/no/1121

問題

N個の格子点の座標が与えられる。
このうちN/90個を選択し、互いの距離が10以上となるようにせよ。

解法

格子点全体を何らかの条件で90個のグループに分類することを考える。
その際、同グループ内の頂点同士の距離が10以上になるようにしよう。

例えば横10個*縦9個の矩形範囲を繰り返して平面を敷き詰めたとする。
矩形内の相対位置が同じ等しい格子点同士について、横の隣の矩形内の点との距離は10保てる。
ただこれだと上下の矩形内との点との距離は9となり条件を見たさない。
そこで、矩形を敷き詰める際に1行ごとに横に5ずつずらしていこう。

そして最も数が多いグループの頂点群を答えればよい。

int N;
int X[303030],Y[303030];
vector<int> S[10][9];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		y=Y[i]%9;
		x=(X[i]+Y[i]/9*5)%10;
		S[x][y].push_back(i);
	}
	
	FOR(x,10) FOR(y,9) if(S[x][y].size()*90>=N) {
		cout<<S[x][y].size()<<endl;
		FORR(s,S[x][y]) cout<<s+1<<" ";
		cout<<endl;
		return;
	}
	assert(0);
	
		
}

まとめ

途中もっと複雑な形状も考えたけど、最終的にはシンプルなものに落ち着いた。