TopCoder SRM 808 : Div1 Medium IOIWeirdModel1

IOIってこういうパズルっぽい問題が出るんですか…？
https://community.topcoder.com/stat?c=problem_statement&pm=17040&rd=18705

問題

整数Mを、規約の有理数列Pを用いて変換することを考える。
この変換は以下のように行う。

• M*P[i]が整数であるような最小のiを求める。なければ処理は終了。
• 上記iに対し、M=M*P[i]で更新し、再度上記処理を繰り返す。

ここで、M=2^a+3^b+5^c+7^d+11^eを初期値として与えることを考える。
a,b,c,d,eは0以上100以下の整数とする。
この時、xをa,b,c,d,eのMedianのして、最終的にM=47^xとするようなPを構築せよ。

解法

a,b,c,d,eのmedianの回数だけ47を掛けるようなPを作ることを考える。

• 分母を2,3,5,7,11の部分集合の積とする。

分子は、上記部分集合が3個以上なら47、そうでないなら1とする。
これらを、部分集合の要素数の大きい順に並べる。

上記のようにすると、a,b,c,d,eのうち3番目に大きい要素の数だけ47が掛けられる。

class IOIWeirdModel1 {
	public:
	vector <int> program(int L) {
		vector<int> V;
		int i,mask,j;
		for(i=5;i>=1;i--) {
			FOR(mask,32) if(__builtin_popcount(mask)==i) {
				int a=1;
				if(mask&1) a*=2;
				if(mask&2) a*=3;
				if(mask&4) a*=5;
				if(mask&8) a*=7;
				if(mask&16) a*=11;
				if(i>=3) V.push_back(47);
				else V.push_back(1);
				V.push_back(a);
			}
		}
		return V;
	}
}

まとめ

愚直にテストとかしてたら解くのが遅くなってしまった。