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

kmjp's blog

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

Codeforces #165 Div2. A. Fancy Fence, B. Multithreading

次回はDiv2になってしまったので、Div2の問題も復習。
http://codeforces.com/contest/270/problem/A
http://codeforces.com/contest/270/problem/B

A. Fancy Fence

1~179の整数値Aが与えられるので、1つの内角がその数値になるような正多角形が作れるかを答える。
正N角形の内角の式から\frac{N-2}{N}\times 360 = Aを満たすNがあるか探せばよい。
方程式で求めなくても、Nを3~360まで探すだけで良いので力技で答えられる。

int N;
vector<pair<ll, ll> > box;

void solve() {
	int f,r,i,j,k,l;
	int x,y;
	
	N=GETi();
	FOR(i,N) {
		j=GETi();
		for(k=3;k<=360;k++) {
			if((k-2)*180==k*j) break;
		}
		if(k==361) _P("NO\n");
		else _P("YES\n");
	}
	
	return;
}

B. Multithreading

1~Nの数値を並べ替えた数列が与えられる。
この数列は、もともと1~Nが順に並んでいたものから、1つを抜き出して先頭に加える、という処理を繰り返したものである。
この処理を繰り返して与えられた数列の形にするのに、必要な抜き出し処理の回数を答える。

一番右に残っている単調増加数列は元々あった数列で、それ以外は右から順に抜き出した数値が来ている、と考える。
とすると右端の単調増加数列以外の数が答え。

int N;
int A[100001];

void solve() {
	int f,r,i,j,k,l;
	
	N=GETi();
	FOR(i,N) A[i]=GETi()-1;
	j=0;
	for(i=N-1;i>=1;i--) {
		if(A[i-1]<A[i]) j++;
		else break;
	}
	
	_P("%d\n",N-1-j);
	return;
}

まとめ

微妙な計算ミスでAもBも1発Accept取れてない。
Div2に備えてミスを減らす癖を身に着けないとな…。

広告を非表示にする