TopCoder SRM 773 : Div1 Hard ChristmasCandySplit

それでいいのね…。
https://community.topcoder.com/stat?c=problem_statement&pm=15867

問題

整数集合Sが与えられる。
Sを含む集合S'のうち、以下を満たすものを1つ構築せよ。

• S'の要素は異なる。
• S'の各要素は、S'の総和の約数である。

解法

Sは1～21の部分集合である。
そこで、Sとして1～21をすべて含むものを考えてしまおう。
そうするとコーナーケースとかを考えなくてよくなる。

S'の総和をT=LCM(1,2,...21)とするようにし、あとは総和がTに到達するまで、Tの約数のうち大きい順にS'に加えていくとうまくいく。

この手続きはSによってはうまくいかない。例えばS={2,5}だとLCM(2,5)=10の10以外の約数{1,2,5}をどう足しても10にならない。
幸いSを最大ケースにしておくとうまくいく。

class ChristmasCandySplit {
	public:
	vector<long long> buyMoreBags(vector <int> B) {
		int N=B.size();
		
		ll A=1;
		int i;
		set<ll> did;
		vector<ll> ret;
		ll sum=0;
		for(i=1;i<=22;i++) {
			A=A/__gcd(A,(ll)i)*i;
			did.insert(i);
			if(count(ALL(B),i)==0) ret.push_back(i);
			sum+=i;
		}
		
		vector<ll> cand;
		for(ll a=1;a*a<=A;a++) if(A%a==0) cand.push_back(a),cand.push_back(A/a);
		sort(ALL(cand));
		reverse(ALL(cand));
		FORR(c,cand) if(did.count(c)==0 && sum+c<=A) {
			ret.push_back(c);
			sum+=c;
		}
		
		return ret;
		
	}
}

まとめ

本番は方針は合っていたものの、ここらへんのコーナーケースで落とした。
うーん、もったいない。