【abc147-C】bit全探索

※注意
この記事は、主に自分用に執筆したものです。ので、各所にお気持ちが伝わりづらい(伝わらない)言い回しやコードが散見されるかもしれませんがご了承ください。

まえがき

AtCoder Beginner Contest 147。
あれ、このC問題むずくね？ってなったので少し身を入れてお勉強してみた。今までbit演算子とか全然使ってこなかったからすごい初歩的なとこからまとめる。
※abc147-C(HonestOrUnkind2).Difficulty: 972

本編

$1\leq N \leq 15$ とかなので、N人分の正直者or不親切な人全パターンを調べてやれる。ゆーて　$2^{15}=32768$ パターンまでなので。この全パターンをN桁の2進数に割り当てて、それをうまく操作して全探索してやろう、っていうのがbit全探索。とりあえず謙虚に簡単なとこから。

ビット演算子

ビット演算子てのはそもそも、「2進数表記の整数を操作するための演算子」って感じ。なんだけど、PCくんはもともと整数をbitで管理してるわけだから、普通にint型とかに作用させていいもの。なんかbit型とかがあんのかなーとか妄想したこともあるけどそんなことはなかった。

演算子	効能
&	ビットごとにAND
|	ビットごとにOR
^	ビットごとにXOR
~	ビットごとに反転
<<	左シフト(桁増える)
>>	右シフト(桁減る)

はいとりあえずこんな感じ。ちょいちょいとコメントも添えておく。

• XORは日本語では排他的論理和ね。響きが好き。ビットが異なるかどうかをみる。

• ~は補数表現てやつになる。符号付き整数値みたいなディジタル回路でやったやつ。細かい説明は割愛。ただまあこれつけてもちょっと処理の意味とか考えるの難しいし桁あふれ無視とかあるしあんまり使いたくないなあ。なんかこれを有効に使うアルゴリズムとかに出会うまでそういう目線で見る。

• x << nみたいに使う。1番右に0をn個追加する。10進数でいうなら、全体2倍をn回やるのと等価。

• 同じくx >> nみたいに。1番右の桁からn桁問答無用で削除。2で割って割り切れなくても切り捨てるって操作をn回やるのにあたるかな。もしくは$2^{n}$で割って切り捨て。

• 桁数が異なるもの同士を演算することもめちゃめちゃあるだろうけど、上の方は全部0だから心配しなくていいよ。ただ補数表現だけはひっくり返って1だけど。まあほっとこ。

シフトなんかはビットとあんま関係ない状況でも普通に使えそうだなあ。普通に使われてるコード読むことも多そうだし仲良くなっとこう。まあ忘れても例を見ればわかると思うのでちゃんと置いとく。

サンプル

free.cpp

  int a=9;   //1001
  int b=12;  //1100

  int ans1 = a&b;  //1100
  int ans2 = a|b;  //1101
  int ans3 = a^b;  //0101
  int ans4 = ~a;   //0110 (補数表現)
  int ans5 = a<<1;  //10010
  int ans6 = a>>1;  //100
  int ans7 = a<<3;  //1001000
  
  cout<<ans1<<endl;  //8
  cout<<ans2<<endl;  //13
  cout<<ans3<<endl;  //5
  cout<<ans4<<endl;  //-10
  cout<<ans5<<endl;  //18
  cout<<ans6<<endl;  //4
  cout<<ans7<<endl;  //72

ちなみにここで cout<<a&b<<endl; とか書くと、<<が左シフトだと勘違いされてバグります。これ以外にもちょっと軽い気持ちで書くと思わぬ挙動したりしたので、ビット演算子使うときは気をつけてみようかな。あとでまたちょっと書く。

bit全探索

というわけでbit全探索する。とは言ったものの、bit全探索ゆーても普通に全探索で、それぞれのパターンの表現、調査に2進数を使ってる、ってのが本質な気がした(いつもの解いてからだとなんかすごく簡単なことのように思えてくるやつ)。というわけでまずACコードをベタ張りして、bit特有の記法とか、思ったこととかを残していく感じにします。

ACコード

abc147/d.cpp

# include <bits/stdc++.h>
using namespace std;

using N = pair<int, int>;
using Data = vector<vector<N>>;

int main() {
  int n;
  cin>>n;

  //こんな風にデータ受け取ってみた
  Data data(n);
  for(int i=0; i<n; i++) {
    int a;
    cin>>a;
    for(int j=0; j<a; j++) {
      N claim;
      cin>>claim.first>>claim.second;
      data[i].push_back(claim);
    }
  }

  int ans = 0;
  for(int bit=0; bit<(1<<n); bit++) {
    bool ok = true;
    int num = __builtin_popcount(bit);
    for(int i=0; i<n; i++) {
      if((bit>>i)&1) {  //人i+1が正直者と仮定するなら、そいつの言い分は検証する必要がある
        for(N check : data[i]) {
          if(((bit>>(check.first-1))&1) != check.second) ok=false;
        }
      }
    }
    if(ok && num>ans) ans=num;
  }

  cout<<ans<<endl;

  return 0;
}

言っておきたいこと！

タイトルの次元低いけど、個人的にはここが有意義です。

• for(int bit=0; bit<(i<<n); i++) {... って回してるforがbit全探索そのもの。1<<nは　$2^{n}$ と完全に等価。これ絶対今後も使うから慣れとこう。

• (bit>>i)&1 ってところ。これは何をしているかというと、bitの下からi桁目が1かどうかを調べてる。&1を作用させると確かに一番下の桁が取り出せるよね。オリジナルで考えたから一般的かどうかは知らんけど、普通にスマートでいいと思ってる。

• ((bit>>(@@@))&1) != @@@ ってところ。左の方カッコが多くてちょっときもいんだけど、ビット演算子使うときは丁寧めにつけたほうがいいなと今日感じた。というのもこれ演算子の優先順位がちょっとぼくの直感と違くて、具体的には　「>>や<<」→「==や!=」→「&」(→「^」→「|」!!ここに差あるんかい) とかいう。笑　　とりあえず今回では、カッコつけないと&より先に!=が処理されて言うことを聞かなくなる。これには結構足止め食らったから二度とやられないように。

• __builtin_popcount() は、引数を2進数表記したときに1が何個あるかを返す。ライブラリノート作ったときはこんなピンポイントなのどこで使うんだとか思ってたけど、普通に出番きてて反省してます。君がいてくれて助かった。

---

ほいとりまこんな感じかな。なんか初心者が通る道を自分も大体なぞった気がする。最後ずっと取れなかったエラーはデータ受け取りのiとj逆にしてたってのは内緒。
※演算子の優先順位については→ここ←をガン見しました。今後も必要になるかもだし貼っとく。

おしまい

この問題は関係ないけどやっと緑に乗った！＼(^^)／ (遅い)(嬉しい)

あと8日ぶりくらいに外出して急に深夜ランニングしてきた。身体重かった。