torus711 のアレ

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

TopCoder SRM 600, Division 2, Level 2 : ORSolitaireDiv2

概要

 Division 1, Level 1 とほぼ同一。ただしこちらは numbers の要素数が 20 以下。

解法

 制約以外 Division 1, Level 1 同一なので同じアルゴリズムで解けますが、N <= 20 の制約を活かす解法が存在するので書きます。
 N <= 20 であるので、numbers の各要素について 消す/消さない を全通り試すことができます。プレイヤーがクリアするまでの手数には興味が無く、クリアが可能か不可能かだけに興味があるので、使える要素が決まったときにクリア可能性だけ求められれば良いことになります。
 では、プレイヤーに与えられる numbers の部分集合が決まった状況下でクリア可能性を判定する方法について述べます。繰り返しになりますが手数には興味が無いので、立ててはいけない bit を立ててしまうような要素以外は全て使ってしまって良いことになります。そのような要素を全て使っても goal を作れないとすれば、そのとき与えられた numbers の部分集合ではクリア不可能です。
 goal を作れないような numbers の部分集合であって、最も要素数が多かったときに消去した要素の数が答えです。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class ORSolitaireDiv2
{
public:
	int getMinimum( vector <int> numbers, int goal )
	{
		const int N = numbers.size();

		int res = INT_MAX;
		REP( s, 0, 1 << N )
		{
			int x = 0;
			REP( i, 0, N )
			{
				if ( !( s & 1 << i ) && ( goal | numbers[i] ) == goal )
				{
					x |= numbers[i];
				}
			}
			if ( x != goal )
			{
				res = min( res, __builtin_popcount( s ) );
			}
		}
		return res;
	}
};