ABC128 (C問題) bit 全探索

探索系の問題をやりたくてこのサイトを見ていた。そしてbit全探索に馴染みがなかったので、今回はABC128のC問題に取り組んだ。 問題設定が自分にとっては複雑で、まずはこれを理解するのに時間がかかった。競プロには迅速な情報処理能力も求められていると改めて実感した。bit 全探索のbit[]配列に0 or 1の値を詰めていくところは先のサイトを参照した。そして以下のコードを書き、見事ACすることができた。switchは1~Nであるが、配列は0~N-1のインデックスと対応していることを忘れていて割とデバッグに時間がかかってしまったので、そこは反省。

#include <iostream>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    int k[M];
    int s[N][M];
    for (int i = 0; i < M; i++) {
        cin >> k[i];
        for (int j = 0; j < k[i]; j++) {
            cin >> s[j][i];
        }
    }
    int p[M];
    for (int i = 0; i < M; i++) {
        cin >> p[i];
    }
    int ans = 0;
    for (int i = 0; i < (1<<N); ++i) {
        int bit[N];
        int result = 0;
        // ここでbit[]配列に0,1を詰めていっている
        // Divで割ることでその桁のbitがわかる
        for (int j =0; j < N; j++) {
            int Div = (1<<j);
            bit[j] = (i / Div) % 2;
        }
        for (int j = 0; j < M; j++) {
            int tmp = 0;
            for (int q = 0; q < k[j];q++) {
                // ここの-1を忘れない！
                tmp += bit[s[q][j]-1];
            }
            if (tmp % 2 == p[j]) result++;
        }
        if (result == M){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

メモ

もはや競プロとは全く関係ないが今日学んだことがあるので、それについて。 gitにはインタラクションモードというものがあり、細かい操作はインタラクティブに行った方が楽な場合がありそう。例えばステージングする時、git add -iとすることで、インタラクティブにステージングの操作が行える。ファイル毎のステージングやパッチ毎のステージング（つまり同じファイルであっても変更箇所ごとにステージングするか否かを決めることができる）なども簡単に行えるようだ。詳しくはここを参照。

それと高速逆平方根(fast inverse square root)についての話を聞く機会があったのでメモ。詳しくはこれを参照すると良い。こんな簡単に実装できてしまうのかと驚いた。これを思いつくのは凄すぎる。プログラミングにおけるニュートン法のあり方・ユースケースをあまり理解していないので、勉強する必要性を感じた。