読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #164 Div2. C. Beautiful Sets of Points

Codeforces

さて、気づくか気づかないかで難易度が大幅に変わる問題。
http://codeforces.com/contest/268/problem/C

2次元座標のうち長方形の領域(0,0)-(W,H)が指定される。
その中で複数の格子点を選び、その格子点同士の距離が非整数になっているような格子点群のうち、数が最大のものを求めて点列の1例を返す問題。

ぱっと見、候補となる点が多くて簡単に解けないように見える。
だが考えてみると、点同士の距離が整数値を取れないとすると、同じx座標またはy座標の点は取れないことになる。
よって、取りうる数はmin(W,H)+1である。

次にそのような点列の1例を示す必要があるが、これは45度に1列に点を並べれば、それぞれの距離は√2の整数倍になるので、いずれも無理数になる。
(0,0)は使えないので、(0,H)から右下に点を延ばせばよい。

int N,M;
int NG[10001];
void solve() {
	int f,r,i,j,k,l,x,y;
	
	ZERO(NG);
	GET2(&N,&M);
	_P("%d\n",min(N,M)+1);
	FOR(i,min(N,M)+1) {
		_P("%d %d\n",N-i,i);
	}
	
	return;
}

まとめ

これまた、一瞬考えさせられるけど気が付くと瞬殺な問題。
こういう問題を考え付く頭がうらやましい。

広告を非表示にする