概要
整数列に対し、次の二つの操作ができる。
- 一つの要素を選んで、1 を加算する
- 全ての要素を二倍する
はじめ、全ての要素は 0 である。
ある数列が与えられるので、最小何回の操作でこれを作ることができるか求めよ。
解法
一つの要素について、それを目標の値 a にするために必要な操作回数について考えます。
二進数で考えると、二倍する操作は 1 bit の左シフトです。
この操作では立っているビットの数は変わらないので、少なくとも a で立っている bit の数だけ 1 を加算する必要があります。
二倍する操作の必要数は、a の立っている最も左側の bit の位置（ 1-indexed ） - 1 と等しくなります。
一連のシフト操作の合間に適切なタイミングで 1 を加算することで、立っている bit の数と等しい回数の加算操作で a を作れます。
次に、数列全体について考えます。
上位の桁から順に作っていくと考えると、その桁の bit を立てるべき要素に 1 を加算 → （終わりでなければ）左シフト という操作の繰り返しになります。
0 へのシフト操作では値が変わらないので、余剰なシフト操作は吸収されます。
なので、立っている bit の数の総和 + 必要なシフト操作の回数の最大値 が答えになります。
コード
#define FOR( v, c ) for ( auto &v : c ) class IncrementAndDoubling { public: int getMin( vector <int> desiredArray ) { int res = 0, maxbit = 0; FOR( a, desiredArray ) { res += __builtin_popcount( a ); maxbit = max( maxbit, a ? 31 - __builtin_clz( a ) : 0 ); } return res + maxbit; } };
