Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/03/02

SRM 463 BunnyPuzzle

| 23:20

http://www.topcoder.com/stat?c=problem_statement&pm=10740&rd=14148

それぞれの Bunny について左右のジャンプ先の位置を求めて2つ以上飛び越えないか判定するだけ.位置が昇順の配列になっているので b[i] が b[i+1] を飛び越えるときは b[i+2] を超えていないか調べれればよくて判定も簡単.

b[n-1] は右に,b[0] は左に飛ぶことはないので n-1 個の Bunny をそれぞれ調べればいい.0<=i<=n-2 でループを回して同時に調べるため,左に飛ぶときは b[i+1] が b[i] を飛び越えるように考えている.

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;
#define sz(a) int((a).size())

class BunnyPuzzle
{
public:

int theCount(vector <int> b)
{
	int c = 0;
	int n = sz(b);
	for(int i=0;i<n-1;i++)
	{
		// right
		int p = 2*b[i+1] - b[i];
		if(i+2==n||b[i+2]>p) c++;
		// left
		p = 2*b[i] - b[i+1];
		if(i==0||b[i-1]<p) c++;
	}
	return c;
}
};

SRM 463 RabbitNumbering

| 23:20

http://www.topcoder.com/stat?c=problem_statement&pm=10697&rd=14148

番号をつける条件が厳しい順,つまり M[i] が小さい順に考えていくため,まずソートする.

すると 0 番目の Rabbit はM[0] 通りの番号をつけられる,1 番目の Rabbit は M[1]-1 通りの番号をつけられる,n 番目の Rabbit は M[n]-n 通りの番号をつけられる.

M[n]-n が 0 以下であった場合は番号が振れなくなる.

32 bit だと integer overflow を起こすことに注意.long long を使う.

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

#define Forall(i,v)   for(int i=0;i<(int)v.size();++i)
#define Sort(c)     sort((c).begin(),(c).end())

class RabbitNumbering
{
public:

int theCount(vector <int> M)
{
	Sort(M);
	uint64_t r = 1;
	Forall(i,M)
	{
		if(M[i]<=i)
		{
			return 0;
		}
		r *= M[i]-i;
		r %= 1000000007ul;
	}
	return (int)r;
}
};