TOC13の1Bの2問目(EllysFigurines)

久々にTopCoderのアルゴリズムに参加したんですが、3問中でEasyのみしか解けなくて生きるのが辛いです。終わってからもMediumの問題が中々理解出来なかったので書いて覚えるメソッドです。問題の原文はこれです。

要はランダムで駒が置かれてる15×15以内のサイズのオセロ版みたいなのが与えられて、一回の操作でR行分かC列分の駒を消せる時、全部の駒を消すのに必要な操作回数を回答するというもの。

解いている時は2^15が途方も無い数だと言う気がしていて、全件走査はキツいから、DPで解くはずと思い込んでしまって全く手が動きませんでした。その後正解の方々のコードをチラチラ見ながら書いたのが以下のコードです。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <limits>
#include <algorithm>

using namespace std;

class EllysFigurines {
public:
    int getMoves(vector <string> board, int R, int C) {
        int ans = numeric_limits<int>::max();

        int H = board.size();
        int W = board[0].length();

        int rows[16] = {};
        for (int r = 0; r < H; r++) {
            for (int c = 0; c < W; c++) {
                if (board[r][c] != '.') {
                    rows[r] |= (1 << c);
                }
            }
        }

		// ここから全件走査
        int max = 1 << W;
        for (int mask = 0; mask < max; mask++) {
            int cnt = 0;
            for (int i = 0; i < W; i++) {
                if ((1<<i) & mask) {
                    cnt++;
                    i += C - 1;
                }
            }
            for (int i = 0; i < H; i++) {
                if (rows[i] & ~mask) {
                    cnt++;
                    i += R - 1;
                }
            }
            ans = min(ans, cnt);
        }

        return ans;
    }
};

最初何をしてるのか分からなかったのですが、ビットマスク作って全件走査しています。個々のビットマスクがスウィープする行の組合せを表現していて、行の組合せが決まると列の組合せが一意に決まるんですね。
行の組合せをビットマスクで表現するというのが競技プログラミング特有な感じがしますね。

今週の水曜日にSRMがあるようなので、次はもうちょっと頑張りたいです。