POJ 3185 The Water Bowls

解法

greedy
左端をflipするかの2通りを試す
位置iが1である場合、iをひっくり返すにはi, i + 1, i + 2をひっくり返す必要があるのでgreedyにやる

別解
反転パターンを全探索。bit + 無駄な探索しない高速化をしないとTLEする

ソースコード

greedy

int main()
{
    int b[25] = {};
    rep(i, 20)
	cin >> b[i + 1];

    int res = 3333;
    rep(_, 2)
    {
	int a[25];
	COPY(a, b);
	if (_)
	    a[0] = 1;

	int f = 0;
	rep(i, 20)
	{
	    if (a[i])
	    {
		++f;
		rep(j, 3)
		    a[i + j] ^= 1;
	    }
	}
	if (count(a, a + 21, 1) == 0)
	    chmin(res, f);
    }
    cout << res << endl;
}

全探索

int main()
{
    int b = 0;
    rep(i, 20)
    {
	int f;
	scanf("%d", &f);
	b |= f << i;
    }
    b <<= 1;

    const int rev = (1 << 3) - 1;
    const int filter = ((1 << 20) - 1) << 1;
    int res = 3333;
    rep(s, 1 << 20)
    {
	int flips = __builtin_popcount(s);
	if (flips < res) // 刈る
	{
	    int a = b;
	    rep(i, 20)
		if (s >> i & 1)
		    a ^= rev << i;

	    a &= filter;
	    if (a == 0)
		res = flips;
	}
    }
    printf("%d\n", res);
}