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;
}
};