[Codeforces] Round #529 C. Powers Of Two

Powers Of Two

https://codeforces.com/contest/1095/problem/C

考え方

題意

\( n = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_k} \ ( 0 \leq a_i) \) となるような\( a_i \) が存在するかどうかを調べます。存在するとき、\( 2^{a_i} \) を全て出力します。

方針

\( n \) を \( 2 \) 進数で表記したときの\( 1 \) の個数 (ビットカウント) を \( t \) とすると、\( t > k\) ならば解は存在しません。これは、ビットカウントは冗長でない表現なので、\( 1 \) の個数を減らす操作はできないからです。一方で、\( k > n \) のときも解は存在しません。\( n \) の一番冗長な表現は、\( n = 1 + 1+ \cdots + 1 \) なので、\( k \) は最大で \( n \) であるからです。

解が存在するときを考えます。\( n \) を\( 2\)進数で表現したとき、\( b_i = 2^{a_i} \) とすると、\( b_i = 2^{a_i} ( 0 \leq a_i, 1 \leq i \leq m) \)、\(b_j = 0 \ (m + 1 \leq j \leq k)\) と表現できます。\( b_j \) が全て \( 0 \) でなければ良いので、\( b_i  \neq 1 \) に対して、\( b_i = \dfrac{b_i}{2} \)、\( b_j = \dfrac{b_i}{2}\) と分配します。これを繰り返すことにより答えが得られます。

コード

感想

実装よりの問題でしたが難しかったです。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする