kmjp's blog

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

Codeforces #161 Div2. A. Beautiful Matrix、B. Squares

Codeforcesにも手を出してみた。
#162開催中に申し込んで、横で#161 Div2の問題にトライ。
http://codeforces.com/contest/263/problem/A
http://codeforces.com/contest/263/problem/B

A. Matrix

5x5の行列が与えられる。1が1か所だけあるので中心からの距離を答える。
abs(X-2)+abs(Y-2)を答えるだけだね。

void solve() {
	int f,r,i,j,k,l;
	char str[10];
	int x,y;
	
	FOR(y,5){
		FOR(x,5) if(GETi()==1) goto out;
	}
	out:
	_P("%d\n",abs(y-2)+abs(x-2));
	return;
}

B. Squares

(0,0)-(Ai,Ai)で構成されるような正方形がN個与えられる。
そのうちK個に含まれるような座標を答える問題。

2次元だけど、Y=0な点を考えればいいので、実際は1次元だけ考えればよい。
Aiを大きい順にソートすると、(A_{K-1},A_{K-1})を選ぶとK個の正方形に囲まれた点になる。
ただしA_{K-1}=A_{K}の時はK+1個選択されてしまうので、-1を返せばよい。

int N,K;
vector<int> A;

void solve() {
	int f,r,i,j,k,l;
	char str[100];
	
	GET2(&N,&K);
	FOR(i,N) A.push_back(GETi());
	sort(A.begin(),A.end());
	reverse(A.begin(),A.end());
	
	if(K>N) {
		_P("-1\n");
	}
	else if(K!=N && A[K-1] == A[K]) {
		_P("-1\n");
	}
	else {
		_P("%d %d\n",A[K-1],A[K-1]);
	}
	
	return;
}

まとめ

数の上限がTopCoderの50より多いのでなんか斬新。
ただ、Codeforcesはサーバ周りが不安定だな…。
本番開催中でなくてもsubmitした回答がずっとin queueになったり、too busyが返ってきたり。