torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder SRM 600, Division 1, Level 1 : ORSolitaire

概要

 次のような一人用ゲームをする。始め、プレイヤーは X = 0 を持っていて、X = goal を達成することを目標とする。一回の操作では、整数集合 numbers の中から一つの数を選び、選んだ数を n とすると X を X OR n で置き換える。
 しえるはこのゲームを邪魔したいので、numbers から要素を取り除いてクリア不可能となるようにしたい。最小いくつの要素を取り除くことでクリア不可能にできるか求めよ。

解法

 まず、余計な bit を立ててはいけないので、goal で立っていない bit が立っている要素が使われることはありません。これらの要素を取り除いたとしてもゲームクリアに支障は無いので、これらの要素は除外して考えます。
 さて、ゲームをクリアできない状況とは、goal で立っている bit の内で立てることができない bit が一つ以上存在するときです。そのような bit が出てくるように要素を取り除くとして、一つの bit を立てられなくすれば十分です。どの bit を立てられなくするか決めたとき、その bit が立っている要素を全て取り除けばクリア不可能にできるので、そのような要素の数を数えれば必要手数が分かります。まとめると、着目する bit を全て試してそれぞれの手数を計算し、最小値をとれば解けます。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

class ORSolitaire
{
public:
	int getMinimum( vector <int> numbers, int goal )
	{
		int res = INT_MAX;
		REP( i, 0, 31 )
		{
			if ( !( goal & 1LL << i ) )
			{
				continue;
			}

			int cnt = 0;
			FOR( n, numbers )
			{
				cnt += ( goal | n ) == goal && !!( n & 1LL << i );
			}
			res = min( res, cnt );
		}
		return res;
	}
};