SRM612 Div2 Hard "PowersOfTwo"
問題
TopCoder Statistics - Problem Statement
訳
キツネのシエルは2のべき乗が好きである。彼女は正の2のべき乗が入ったバッグを持っていた。同じべき乗が複数入っている事もある。あなたはlong[] powersが与えられる。それはシエルのバッグに入っているべき乗を表している。
シエルはバッグに入っているべき乗を足し合わせた数も好きであった。
例えば、彼女のバッグに{2, 4, 4, 64}が入っていたとする。シエルは10(10=2+4+4)、64(64=64)、0(何も足さない)が好きである。彼女は1、12(バッグに4は2つしかないので、4+4+4とはできない)は好きではない。
シエルが好きな数がいくつあるかを返せ。
制約
1 <= バッグの中に入っているべき乗の数 <= 50
1 <= バッグの中に入っているべき乗 <= 2^50
考えたこと
まずバッグの中のべき乗を指数に直し、指数ごとの数を出す。
1, 4, 4, 4, 4, 8, 8, 16, 64 ↓ 0, 2, 2, 2, 2, 3, 3, 4, 6 ↓ 1(0), 0(1), 4(2), 2(3), 1(4), 0(5), 1(6)
各指数は1個あればその指数を使うか・使わないかを決めることができる。
なので余計な分は2つ消費して1つ親に渡してしまう。
1, 0, 4, 2, 1, 0, 1 ↓ 1, 0, 2(-2), 3(+1), 1, 0, 1 ↓ 1, 0, 2, 1(-2), 2(+1), 0, 1
これで0, 1, 2のどれかのシーケンスになる。
このシーケンスを前から順番に見ていってパターン数を出していく。
その時、このシーケンスを3つのパターンで考える
1. 0の要素 2. 1の要素 3. 2からその次の0のグループ
1. 0の要素
いきなりポツンと0が出てきた場合がこれにあたる。
1, 0, 2, 1, 2, 0, 1 ↑
この場合、下からの繰上げはなく、また1にすることはないためパターン数は増えない。
2. 1の要素
いきなりポツンと1が出てきた場合がこれにあたる。
1, 0, 2, 1, 2, 0, 1 ↑ ↑
この場合、下からの繰上げはなく、上へ繰り上がることもできない。
独立していて0か1好きなほうを選ぶことができるため、パターン数に * 2する。
3. 2からその次の0のグループ
下記のような要素は繰り上がりによって数が変動するので1つのグループとして考える。
1, 0, 2, 1, 2, 0, 1 ^^^^^^^^^^^
一番右の0をそのままにして何パターン取れるか = 2^3
2, 1, 2, 0 ^^^^^^^^
一番右の0を1にしてみる
2, 1, 0, 1
一番右の0をそのままにして何パターン取れるか = 2^2
2, 1, 0, 1 ^^^^^
一番右の0を1にしてみる
0, 0, 1, 1
一番右の0をそのままにして何パターン取れるか = 2^0
0, 0, 1, 1 ^^
よってこのグループでのパターン数は2^3 + 2^2 + 2^0となり、それを結果のパターン数にかけてあげればよい。
ソースコード
class PowersOfTwo { public: long long count(vector<long long> powers) { int cnt[55]; memset(cnt, 0, sizeof(cnt)); // 指数のそれぞれの数にする int n = powers.size(); for (int i = 0; i < n; i++) { int c = 0; long long a = 1; while (a != powers[i]) { a *= 2; c++; } cnt[c]++; } // 余計なものは親に渡す for (int i = 0; i < 55; i++) { if (cnt[i] >= 3){ int t = cnt[i] % 2 == 0 ? 2 : 1; int up = cnt[i] - t; cnt[i] -= up; cnt[i + 1] += up / 2; } } long long res = 1; int p = 0; while (p < 55) { if (cnt[p] == 0) { // 1. 0の要素 // 何もしない } else if (cnt[p] == 1) { // 2. 1の要素 res *= 2; } else if (cnt[p] == 2) { // 3. 2から次の0までのグループ long long m = 0; int s = p; while (true) { if (cnt[p] != 1) { int pow = p - s; long long add = 1; for (int i = 0; i < pow; i++) { add *= 2; } m += add; } if (cnt[p] == 0) break; p++; } res *= m; } p++; } return res; } };