AtCoder が提供しているABC（AtCoder Beginner Contest）002 D問題をC++で解いてみました。ABC002は、2013年10月27日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 派閥（Difficulty : 1418（参考値））
問題の詳細は、リンク先をご覧ください。
bit全探索を用いて、すべての議員の組み合わせを調べます。AtCoder Problems による Difficulty は 1418（参考値）でした。
解答案
C++ プログラム例（ABC002D）
派閥としてありえるすべての議員の組み合わせを bit 全探索で調べます。以下は補足です。
- 自分自身とは知り合いです（11ー13行目）。問題文には明記されていませんが、入力例4から確認できます。
- 全探索を行う変数 bit のうちいくつの bit が1となっているかを bitset で求めています（25行目）。
bit全探索を使うことが分かれば、解きやすい典型的な問題でした。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
int main()
{
int n, m;
cin >> n >> m;
vector<vector<bool>> rel(n, vector<bool>(n, false));
for (int i = 0; i < n; i++) {
rel[i][i] = true;
}
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
--x;
--y;
rel[x][y] = true;
rel[y][x] = true;
}
int result = 0;
for (uint bit = 0; bit < (1U << n); ++bit) {
int t = bitset<32>(bit).count();
bool is_OK = true;
for (uint i = 0; i < (uint)n; ++i) {
for (uint j = 0; j < (uint)n; ++j) {
if (((bit & (1 << i)) != 0) && ((bit & (1 << j)) != 0) &&
!rel[i][j]) {
is_OK = false;
}
}
}
if (is_OK) {
result = max(result, t);
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
ABC002としては、一番難易度が高い問題でしたが、ある意味典型的な問題となっていました。
引き続き ABC の問題を紹介していきます。
