Search on the blog

2010年12月26日日曜日

ビット演算集大成の問題!?

ビット演算集大成の良問をPOJで見つけたので紹介。

実は、自分でも似たような問題を考えていてTopCoderに問題投稿しようかな・・と思ってましたが、似たような問題は既にありました。。
しかも、2次元バージョンでよりトリッキーな感じ。。

問題はこちら。

簡単に日本語訳すると、
4*4マスに+と-の文字列がある。
(i, j)マスを選択すると、(i,j)マスが
+の場合は、-に
-の場合は、+に
反転変換できる。但し、(i,j)マスを選択すると、i行のマス及びj行のマスの値もすべて反転してしまう。
すべての文字を-にするためには、最低何回のマスを選択しないといけないか?
またそのときに選択するマスを列挙せよ。

んー、これ系の問題はメジャーなんですかね。。TopCoderでも似たような問題ありました。
ビット演算を使うと解けますが、実はこの問題はビット演算の使いどころが2種類あります。
①組み合わせをビットで表現する
②状態および処理をビット演算で計算し、処理を高速化

①は、どのマスを選択するかを0, 1のビットで表すという意味。
②は、4*4マスの状態を16bitのビットで保持します。さらに、あるマスを選択した場合の処理をXORを用いて実現します。

以下ソース。


int main() {
int ch[16];
REP(i,16) {
ch[i] = 0;
REP(k, 16)
if (k/4 == i/4 || k%4 == i%4)
ch[i] |= 1<<k;
}

string in;
int ref = 0;

REP(i, 4) {
cin >> in;
REP(j, 4)
if (in[j] == '+')
ref |= 1<<(4*i+j);
}

int ret = INF, bcomb = -1;
REP(comb, 1<<16) {
int ref_t = ref, cnt=0;
REP(i, 16)
if (comb >> i & 1)
ref_t ^= ch[i], ++cnt;

if (!ref_t && ret > cnt)
ret = cnt, bcomb = comb;
}
cout << ret << endl;
REP(i, 16)
if (bcomb >> i & 1)
cout << i/4+1 << " " << i%4+1 << endl;

return 0;
}


0 件のコメント:

コメントを投稿