Codeforces #167 Div2. A. Dima and Friends、B. Dima and Sequence

#167以降はなんとかDiv1キープ。
今回はAとBは解けたけどCは解けず。毎回そのぐらいだな。
ではDiv2から順に復習。

http://codeforces.com/contest/272/problem/A
http://codeforces.com/contest/272/problem/B

A. Dima and Friends

N人の人が円形に並んでいる。
各人が片手の指を1～5本上げたとき、１人目から初めてその指の合計分の進んだ人がハズレとなる。
自分以外の指の本数がわかっているとき、自分がハズレとならない指の上げ方を答える。

これは単純に自分が指を１～５本上げた場合のハズレの人を探せばよい。

void solve() {
	int f,r,i,j,k,l, x,y,loop,N;
	
	N=GETi();
	j = 0;
	FOR(i,N) j += GETi();
	
	k=0;
	for(i=1;i<=5;i++) if((j+i-1)%(N+1)) k++;
	_P("%d\n",k);
	
	return;
}

B. Dima and Sequence

非負整数に対し、関数fは次の特性を持つ。

• f(0) = 0
• f(2x) = f(x)
• f(2x + 1) = f(x) + 1

ここで、自然数の配列が与えられる。
この配列から２つの数値x,yを選んだ時、f(x)=f(y)となるx,yの選び方の組み合わせを答える。

解法は単純で、配列の各要素xに対しf(x)を求め、f(x)が同じ値になるxの個数を求める。
ちなみに、このf(x)ってbit countだよね。

int N;
map<int, ll> M;

int func(int x) {
	if(x==0) return x;
	return func(x/2) + (x%2);
}

void solve() {
	int f,r,i,j,k,l,x,y;
	
	N=GETi();
	FOR(i,N) {
		j=func(GETi());
		M[j]++;
	}
	
	ll res=0;
	for(map<int,ll>::iterator mit=M.begin();mit!=M.end();mit++) {
		res += mit->second*(mit->second-1)/2;
	}
	
	_P("%lld\n",res);
	return;
}

まとめ

さすがにDiv2 A,B位だと簡単だね。