atcorder beginner contest の問題

Question

僕はbit全探索の勉強をしている高校生です
atcorder beginner contest 147のC問題をだれかbit全探索で解いて、
僕に解説してくれませんか？
一応ユーザー解説も見ましたが、あまり理解できませんでした
どなたかこの問題をどのように説くのか詳しい解説を教えてください
（できれば1行ずつ解説してくれるとありがたいです）

Comments

[1T2R3M4]

メンターサービス等をご検討されてはいかがでしょうか。

[busa145]

お金がないです
高校生にもなって小遣いゼロですから

[Zuishin]

> 一応ユーザー解説も見ましたが、あまり理解できませんでした

一応ではなく、理解できるまで読んでみては？
お金がない時には、人にたかるのではなく努力でどうにかするものです。
その上で理解できないところを質問すれば回答がつくのではないかと思います。

[actorbug]

ユーザー解説は、実質bit全探索を使うとしか言っておらず、後はコードを見て理解してくださいというスタンスです。
bit全探索をすでに理解している人向けの解説なので、bit全探索を学習する目的でこちらの解説を利用するのは無理があります。
bit全探索を学びたいのなら、bit全探索自体を解説している別ページを探すことをお勧めします。

あと、今後同様の質問をする際には、回答者の負担を減らすため、問題ページへのリンク・解説ページへのリンクを追加するようにしてください。
https://atcoder.jp/contests/abc147/tasks/abc147_c
https://blog.hamayanhamayan.com/entry/2019/12/13/214342

Answer 1

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int bit_count(int x)
{
	int k;
	for (k = 0; x; x &= x - 1) k++;
	return k;
}
	
int main()
{
	int n, a, x, y, max = 0;
	cin >> n;
	vector<map<int, int>> v(n);
	for (int i = 0; i < n; i++) {
		cin >> a;
		while (--a >= 0) {
			cin >> x >> y;
			v[i][x-1] = y;  // map に証言を登録
		}
	}
	for (int p = 1 << n; --p; ) {  // ビットパターン全部を試す
		bool ok = true;  // このビットパターンに矛盾が無いと仮定
		for (int i = 0; ok && i < n; i++)
			if (p >> i & 1)  // i番目の人が正直者なら
				for (auto m : v[i])  // m は正直者の証言のひとつ
					if ((p >> m.first & 1) != m.second) {
						ok = false; // 矛盾が見つかった
						break;
					}
		if (ok) {  // 矛盾が無かったら
			int k = bit_count(p);
			if (k > max) max = k;  // 正直者の最大数を更新ｎ
		}
	}
	cout << max << endl;
}

map を知らなければ理解できないでしょう。

追記
map は必要ありませんでした。証言の vector で十分です。

#include <iostream>
#include <vector>
using namespace std;

struct Testimony {  // 証言
	int x, y;
	Testimony(int x, int y) : x(x), y(y) {}
};

int main()
{
	int n, a, x, y, max = 0;
	cin >> n;
	vector<vector<Testimony>> v(n);
	for (int i = 0; i < n; i++) {
		cin >> a;
		while (--a >= 0) {
			cin >> x >> y;
			v[i].push_back(Testimony(x-1, y));  // vector に証言を追加
		}
	}
	for (int p = 1 << n; --p; ) {  // ビットパターン全部を試す
		int k = 0;  // 正直者の人数
		bool ok = true;  // このビットパターンに矛盾が無いと仮定
		for (int i = 0; ok && i < n; i++)
			if (p >> i & 1) { // i番目の人が正直者なら
				k++;
				for (auto& t : v[i])  // t は正直者の証言のひとつ
					if ((p >> t.x & 1) != t.y) {
						ok = false; // 矛盾が見つかった
						break;
					}
			}
		if (ok && k > max) max = k;  // 正直者の最大数を更新ｎ
	}
	cout << max << endl;
}

bit_count関数も不要で、正直者の人数 k をカウントアップするだけで十分でした。

ところで、もっと詳しい解説は要らないのですか？

Comments

[busa145]

本当にありがとうございます

[busa145]

んーまあこれくらいは自分で理解しようかなと。
結局自分で手を動かさないと覚えないし、
けれど模範解答はrepとか知らない知識が多すぎてよくわからないので、これくらいがちょうどいいです
これからも何かあったらよろしくお願いします

[busa145]

早速質問です
同じようなコードを書いたのですが時間制限をオーバーしてしまいます
どこに無駄があるのでしょうか
#include <iostream>
#include <bitset>
#include <vector>
#include <map>
using namespace std;
int main() {
int N;
cin >> N;
vector<map<int, int>>a(N);
for (int i = 0; i < N; i++) {
int A;
cin >> A;
for (int j = 0; j < A; j++) {
int x, y;
cin >> x >> y;
a[i][x - 1] = y;
}
}
int count = 0; //答え
for (int i = 1 << N; --i;) {
bool ok = true;
int k = 0;
for (int j = 0; ok&&j < N; j++) {
if (i >> j & 1) {
k++;
for (auto m : a[i]) {
if ((i >> m.first & 1) != m.second) {
ok = false; break;
}
}
}
}
if (ok) {
if(k>count)count = k;
}
}
cout << count << endl;
}

[kazuma-s]

> どこに無駄があるのでしょうか
for (auto m : a[i]) { が間違っています。
for (auto m : a[j]) { にしてください。

[busa145]

ありがとうございます