ゲームAI備忘録

ゲームAIに使えそうな知識を備忘録として書き留める

人助けと思って何卒インストールをば！ 詰碁/ アルコネ/ 五目並べ

SRM600 IE, IIM

SRM

問題

概要

n個の数字があり，それらの数字のorの組み合わせで，goal に一致するようにしたい．
goal を作ることができなくなるようにするためには，最小何個の数字を取り除く必要があるか？

制約条件

I = {0, 1, 2, ..., n-1} とする．

  • 1 <= n <= 20
  • 1 <= numbers[i] <= 10^9, for all i in I
  • numbers[i] != numbers[j], for all i, j in I
  • 1 <= goal <= 10^9

解法

J = {i: (goal | numbers[i]) = goal, i in I} とする．

  • numbers[i] (for i in (I - J))は，goal では立っていない場所のビットフラグが立っているので使用できない．
  • numbers[i] (for i in J) のすべての or をとった値 x が goal 未満なら，そもそもgoalを作ることができないので答えは0個となる．
  • numbers[i] (for i in J) の各ビット位置を調べていき，どのビット位置が何度使われているかを調べる．この回数が最も少ない値の場所に使われている数字を取り除けば，goal は作成できないので答えとなる．

コード

class ORSolitaire {
public:
	int getMinimum(vector <int> numbers, int goal) {
		int n = numbers.size();
		bool can_use[50]; memset(can_use, true, sizeof(can_use));
		for (int i = 0; i < n; ++i)
			if ((goal | numbers[i]) > goal)
				can_use[i] = false;
		int x = 0;
		for (int i = 0; i < n; ++i)
			if (can_use[i])
				x |= numbers[i];
		if ((x & goal) != goal) return 0;
		
		int cnt[50]; memset(cnt, 0, sizeof(cnt));
		for (int i = 0; i < n; ++i) if (can_use[i])
			for (int j = 0; j < 32; ++j)
				if ((numbers[i] & (1<<j)) > 0)
					++cnt[j];
		int Min = INF;
		for (int i = 0; i < 32; ++i)
			if (cnt[i] > 0)
				Min = min(Min, cnt[i]);
		return Min;
	}
}