TopCoder SRM 697 Div1 Easy DivisibleSetDiv1、Div2 Medium DivisibleSetDiv2

久々に割といい順位が取れて良かった。
https://community.topcoder.com/stat?c=problem_statement&pm=14362
https://community.topcoder.com/stat?c=problem_statement&pm=14369

問題

N要素の整数列B[i]が与えられる。
このBに対し同じくN要素で、かつ各要素が異なる整数列A[i]を見つけたい。

P[i]をA[i]以外のAの要素の積とする。
各iに対しA[i]^B[i]がP[i]で割り切れるようにしたい。
そんなAが存在するか判定せよ。

Div2はAが2の累乗であるというヒントがある点と、P[i]がA[i]の全要素の積である点以外Div1と同じ。

解法

解法としてはどちらも同じ。Div2はヒントがある点が珍しい。
A[i]=2^C[i]とすると、A[i]^B[i]がP[i]で割り切れるという条件は(2^C[i])^B[i]が2^(sum(C)-C[i])で割り切れるということなので、C[i]*(B[i]+1)≧sum(C)であるCを満たせばよいことになる。
B[i]が小さいほどC[i]が大きい方がよさそうなのは推測がつく。

そこで、B[i]の大きい順に仮にC={1,2,3,...N}と初期値を置いてみて、C[i]*(B[i]+1)≧sum(C)を満たせないiがあったらC[i..N]を加算する、ということをしばらく繰り返し、条件を満たせるかどうか判定した。

string YY="Possible";
string NN="Impossible";
int A[55];

class DivisibleSetDiv1 {
	public:
	string isPossible(vector <int> b) {
		int N=b.size();
		sort(b.begin(),b.end());
		reverse(b.begin(),b.end());
		int i,t=0,ct=0,x;
		
		FOR(i,N) A[i]=1, t++, ct+=t;
		
		FOR(x,1000000) {
			int t=0;
			FOR(i,N) {
				t += A[i];
				if(t*(b[i]+1)<ct) {
					A[i]++;
					ct += (N-i);
					break;
				}
			}
			if(i==N) return YY;
		}
		return NN;
		
	}
}

class DivisibleSetDiv2 {
	public:
	string isPossible(vector <int> b) {
		int N=b.size();
		sort(b.begin(),b.end());
		reverse(b.begin(),b.end());
		int i,t=1,ct=0,x;
		
		FOR(i,N) A[i]=0, ct+=t;
		A[0]=1;
		
		FOR(x,1000000) {
			int t=0;
			FOR(i,N) {
				t += A[i];
				if(t*b[i]<ct) {
					A[i]++;
					ct += (N-i);
					break;
				}
			}
			if(i==N) return "Possible";
		}
		return "Impossible";
		
	}
}

まとめ

このDiv1とDiv2の分け方は珍しいね。