忍者ブログ
25 September

[PR]

×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

22 December

SRM600 div2 medium

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12890

numbersの要素をいくつかOR計算して、goalと一致させる。
goalと一致できないようにするにはnumbersの要素を何個
使わないようにすれば可能か。みたいな感じだと思う。



解法

どれを使えばgoalと一致させられるかは分かったけど、
それ以降が解けなかった。

torus711さんのによると
http://d.hatena.ne.jp/torus711/20131214/p3

解答みてからしばらく考えた結果ORを足し算で考えてたから
ずっと間違ってたっぽいw
一応写経



#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#include<climits>

using namespace std;

class ORSolitaireDiv2{
public:
	int getMinimum(vector <int> numbers, int goal){
		int cnt=INT_MAX;

			for(int i=0;i < (1<<numbers.size());i++){
				int num=0;
				for(int j=0; j < numbers.size();j++){
					if(!(i & 1<<j) && (goal|numbers[j]) == goal)
						num = num | numbers[j];
				}
				
				if(num != goal){
					int cnt1=0;
					for(int j=1; j < (1<<numbers.size());j=j<<1)
						if((i & j)) cnt1++;
					cnt = std::min(cnt,cnt1);
				}
			}
		return cnt;
	}
};


PR