torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 596, Division 1, Level 1 : IncrementAndDoubling

概要

整数列に対し、次の二つの操作ができる。

  • 一つの要素を選んで、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;
	}
};