はまやんはまやんはまやん

hamayanhamayan's blog

DivisibleSetDiv1 [SRM 697 : Easy]

競技プログラミング

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14362

n要素の配列bが与えられる
この時、以下の条件を満たすn要素の配列aが存在するか判定せよ

  • 全ての要素はバラバラ（distinct）である
  • 全ての要素は1より大きい
  • a[i]^b[i]はp[i]で割り切れる

（p[i] = a[1]*...*a[i-1]*a[i+1]*...*a[n-1]）

存在するなら"Possible"しないなら"Impossible"

2 <= n <= 50
1 <= b[i] <= 10

帰納的考察（TwitterやEditorial見た）

1. b[i]がとても小さいのが気になる
2. とりあえず、配列bは昇順ソートしても答えに影響しないのでする
3. …でどうするん？？？

――壁――

4. Twitterまとめ見てたらこんな一節が
5. 圧倒的地頭力
6. Editorialにも同じようなことが書いてある
https://apps.topcoder.com/wiki/display/tc/SRM+697#DivisibleSetDiv1

7. これが分かってもまだ解けない鬼畜仕様
8. この数式を前提としてkmjpさんの解答見たら分かった
9. kmjpさんの解法では全探索してる

10. 「bを降順ソートしておくと、答えのaは昇順になる」が満たされるっぽい
11. これを元にa[i]を小さい方から順に決定していく
12. 答えがあれば10^6以内に解が見つかるみたい

実装

int n;
int a[50];
struct DivisibleSetDiv1 {
	string isPossible(vector<int> b) {
		n = b.size();

		sort(b.begin(), b.end(), greater<int>());

		int sum = 0;
		rep(i, 0, n) a[i] = i + 2, sum += a[i];

		rep(loop, 0, 1000000) {
			bool ok = true;
			rep(i, 0, n) {
				if (a[i] * (b[i] + 1) < sum) {
					rep(j, i, n) a[j]++, sum++;
					ok = false;
					break;
				}
			}
			if (ok) return "Possible";
		}

		return "Impossible";
 	}
};