kmjp's blog

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

TopCoderOpen 2014 Round1C Medium FizzBuzzTurbo

TCO R1C Parallelに参加。一応全完したけどHardに手こずってそこそこの速度。
まぁ想定解を思い浮かばなかったので解けただけいいけどね。
http://community.topcoder.com/stat?c=problem_statement&pm=13062

問題

FizzBuzz問題を考える。
ある数xが

  • 3の倍数ならFizzと答える
  • 5の倍数ならBuzzと答える
  • 3の倍数かつ5の倍数ならFizzBuzzと答える

整数A,Bが与えられたとき、A~Bの整数に対しFizzBuzz問題の答えを求めると、Fizz, Buzz, FizzBuzzの数を答えよ。

解法

0~Bの範囲の数を求めて、0~(A-1)の範囲の数を引くだけ。

class FizzBuzzTurbo {
	public:
	vector<long long> counts(long long A, long long B) {
		vector<ll> V1,V2;
		A--;
		V1.push_back(4*(A/15)+(A%15)/3);
		V1.push_back(2*(A/15)+(A%15)/5);
		V1.push_back(A/15);
		V2.push_back(4*(B/15)+(B%15)/3);
		V2.push_back(2*(B/15)+(B%15)/5);
		V2.push_back(B/15);
		V2[0]-=V1[0];
		V2[1]-=V1[1];
		V2[2]-=V1[2];
		return V2;
	}
};

まとめ

R1Cは意図的に簡単にしてるらしいけど、これはDiv2 Mediumより簡単だな…。