bit全探索の問題をbit全探索しないで解いたお話

始めに

今現在、このサイトの問題を解いております。

qiita.com

ここのbit全探索の練習問題を解いたのですが、自分の解法が別のアルゴリズムで解けたので少しまとめたいと思います。

AtCoder Beginner Contest 002 D - 派閥

問題の概要は次の通りになります。

• N人の人がいて、M個の関係 (x, y) が存在する
• (x, y) とは x と y が知り合いを意味する
• N人の中で全員知り合いとなるグループの最大人数を求めたい
• 1 <= N <= 12、0 <= M <= N(N - 1) / 2

自分なりの解き方（修正3月30日）

ある人物が持つ知り合いの関係をNbitで表現します。 yと知り合いであれば右からy番目は1、そうでなければ0を入れます。

例えば、５人のうちの１番目の人が2, 3番目の人と知り合いの場合、

とします。 右から1番目のbitは自分自身ですが、後々の計算上の都合で1に設定します。

次に、関係を表したbit列を使用して、bit列中で 1 となっている人の関係と論理演算をしていきます。

問題の入力例１を参考に試してみます。この例での知り合い関係は次のように表現できます。

では、

この場合、１番目の人の関係を変数 p に保存します。

このbit列では1, 2, 3番目が１となっています。1番目は自分自身なので飛ばします。次に、2番目が１となっているので2番目の人の関係と論理積を取ります。

次に、3番目も１となっているので3番目の人の関係と論理演算をします。

4, 5番目のbitは 0 となっているので、4, 5番目の人の関係とは論理積を行いません。

最終的に となり、１となっているbitの数は３つなので３人のグループが作成できます。

他の人の関係で同様の計算をしても最大は３人になります。

これだけでは少し物足りないので、入力例２を試してみます。

入力例２の関係は次のようになります。

では、２番目の人の関係を変数 p に保存して、知り合いとなっている人の関係と論理積を取っていきます。

まず、１番目のbitが 1 となっているので１番目の人との関係と論理積を取ります。

２番目は自身なので、飛ばして残りのbitはすべて 0 となるので論理積は取りません。

よって、全員知り合いとなる関係は2人となります。他のパターンでも最大で2人となるので、答えは2人となります。

実装

実装はかなりアルゴリズムを素直に実装した形となっていると思います。

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>

using namespace std;
using ll = long long;


int main() {

    int n, k;

    cin >> n >> k;

    vector<ll> v(n);

    for(int i = 0; i < k; ++i) {

        ll x, y;
        cin >> x >> y;

        x--;
        y--;

        v[y] |= 1 << x;
        v[x] |= 1 << y;

    }


    for(int i = 0; i < n; ++i)
        v[i] |= 1 << i;


    int maxTranslation = 1;
    
    for(int i = 0; i < n; ++i) {
    
        ll p = v[i];

        for(int j = 0; j < n; ++j) {

            if(i == j)
                continue;

            ll bit = 1 << j;

            if(p & bit) {
                p &= v[j];
            }

        }

        int count = bitset<32>(p).count();
        maxTranslation = max(maxTranslation, count);

    }

    cout << maxTranslation << endl;

    return 0;

}

一部解説すると、

ll bit = 1 << j;

if(p & bit) {
    p &= v[j];
 }

ここで注目している人と j 番目の人が知り合いであるかを確かめて、そうであれば論理積を計算しています。

また、

int count = bitset<32>(p).count();

これでbit列pで1の個数を求めることが出来ます。（この問題の解答で見て知りました）

Square869120Contest #4 B - Buildings are Colorful!

問題の概要は次の通りになります。

• N個の建物が存在し、それぞれ高さが決まっている
• N個の建物はそれぞれ違う色が塗られている
• 左からみたときに、K色以上の建物見えるように高さを変えたい
• 高さの変更は上げることのみ可能
• 建物の高さを上げる最小値を求めたい

自分なりの解き方

この問題は再起を使用して解きました。

左から一番目の建物は必ず見えるので、それ以降の建物で見える建物を選択していきます。

選択された建物は、1つ前の選択された建物の 高さ+1 以上になるように上げます。その際、元々の高さ+1 以上であれば、変更しません。

見える建物がK個選択された場合は、それまで上げた高さと今まで計算した最小値と比較して更新します。

初めはこのアルゴリズムで提出しましたが、WAとなりもう一度考え直すと次にケースで間違いとなることがわかりました。

5つの建物があり、3色の建物が左から見えるよう先ほどのアルゴリズムで高さを変えてみます。

すると、1, 3, 4番目が選択された場合、高さを変えることなく計算が終了してしまいます。 しかし、実際は2番目の建物で3, 4番目の建物は見えません。

そこで、1つ前の選択された建物の高さとそれまでの建物の高さの最大値を比較します。後者の方が高ければ1つ前の選択された建物の高さはそれまでの高さの最大値として計算を進める方針で行いました。

このアルゴリズムはbit全探索ではありませんが、原理としては似ているかもしれません。

実装

このプログラムもアルゴリズムをそのまま実装しています。

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <climits>
using namespace std;

using ll = long long;

int n, k;
ll minValue = LLONG_MAX;

vector<ll> b;

void Calc(int index, int kCount, ll prevHeight, ll value) {

    if(kCount == k) {
        minValue = min(value, minValue);
        return;        
    }

    ll maxHeight = -1;

    for(int i = index; i >= 0; --i)
        maxHeight = max(maxHeight, b[i]);

    if(maxHeight > prevHeight)
        prevHeight = maxHeight;

    for(int i = index + 1; i < n; ++i) {

        if(b[i] > prevHeight) {
            Calc(i, kCount + 1, b[i], value);
        }
        else {
            Calc(i, kCount + 1, prevHeight + 1, value + prevHeight - b[i] + 1);
        }
    }
}


int main() {

    cin >> n >> k;

    b.resize(n);

    for(int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    
    Calc(0, 1, b[0], 0);
    cout << minValue << endl;
    return 0;
}

一部解説します。

    ll maxHeight = -1;
    for(int i = index; i >= 0; --i)
        maxHeight = max(maxHeight, b[i]);

    if(maxHeight > prevHeight)
        prevHeight = maxHeight;

ここで、一つ前の選択された建物の高さと今までの建物の高さの最大値を比較して、後者の方が大きければ一つ前の建物の高さはその値として計算を進めます。

for(int i = index + 1; i < n; ++i) {

        if(b[i] > prevHeight) {
            Calc(i, kCount + 1, b[i], value);
        }
        else {
            Calc(i, kCount + 1, prevHeight + 1, value + prevHeight - b[i] + 1);
        }
    }

次に選択する建物は、前の建物の次からになります。前の建物よりも選択した建物の方が大きければ、高さを変えずに次の選択に移行します。

そうでなければ、高さの変化量 (前の建物の高さ - 選択された建物の高さ) + 1 を求めて変化量の合計値に加算します。

if(kCount == k) {
        minValue = min(value, minValue);
        return;        
    }

再起関数の忘れてはならない終了条件になります。

これまで選択した建物の個数がK個になれば、これまでの最小値と比較して更新して終了します。

最後に

bit全探索用の問題を別のアルゴリズムで解いてみました。

それ以外の問題ではすんなりとbit全探索のアルゴリズムが思いつきましたが、この2つだけはなかなか思いつかず、自分なりのアルゴリズムとなってしまいました。

それでも、AtCoder Beginner Contest 002 D - 派閥では初めてbit演算を活用したアルゴリズムを実装しましたし、Building Are Colorfulでも再起のいい勉強となりました。

また、別の機会ではJOI 2008 予選 5 - おせんべいの問題についてもまとめようかなと思ってます。