ABC002D - 派閥

atcoder.jp

N 人の議員がそれぞれ派閥に参加するかどうかのパターンは 2^N なので、ビット全探索を使ってみた。仮の派閥を作っておいて、全員がお互いに知り合いかどうかを調べる。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace ABC002D
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var N = int.Parse(input[0]);
            var M = int.Parse(input[1]);
            var relations = new Vector2[M];
            for (var i = 0; i < M; i++)
            {
                var line = Console.ReadLine().Split(' ');
                var x = int.Parse(line[0]);
                var y = int.Parse(line[1]);
                relations[i] = new Vector2(x: x, y: y);
            }

            var answer = 0;
            for (var bit = 0; bit < (1 << N); bit++)
            {
                // 仮の派閥を作成する
                var faction = new List<int>();
                for (var i = 0; i <= N; i++)
                {
                    if ((bit & (1 << i)) != 0)
                    {
                        faction.Add(i + 1);
                    }
                }

                // 派閥が成り立つかチェック
                var success = true;
                for (var i = 0; (i < faction.Count) && success; i++)
                {
                    var x = faction[i];
                    for (var j = 0; j < faction.Count; j++)
                    {
                        var y = faction[j];
                        if (x == y)
                        {
                            continue;
                        }
                        // 知り合いじゃない組が存在したら派閥は成り立たない
                        if (!relations.Any(r => (r.X == x && r.Y == y) || (r.X == y && r.Y == x)))
                        {
                            success = false;
                            break;
                        }
                    }
                }
                if (success)
                {
                    answer = Math.Max(answer, faction.Count);
                }
            }

            Console.WriteLine(answer);
        }
    }
}

人間関係をビットで管理したら速くなりそうだったのでやってみたら、平均で 70ms 速くなった。

using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC002D
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var N = int.Parse(input[0]);
            var M = int.Parse(input[1]);

            // 人間関係をビットで管理
            var relations = new int[N];
            for (var i = 0; i < relations.Length; i++)
            {
                relations[i] = 1 << i;
            }
            for (var i = 0; i < M; i++)
            {
                var line = Console.ReadLine().Split(' ');
                var x = int.Parse(line[0]) - 1;
                var y = int.Parse(line[1]) - 1;
                relations[x] |= 1 << y;
                relations[y] |= 1 << x;
            }

            var answer = 0;
            for (var bit = 0; bit < (1 << N); bit++)
            {
                var faction = new List<int>();
                for (var i = 0; i < N; i++)
                {
                    if ((bit & (1 << i)) != 0)
                    {
                        // ビット演算で知り合いかどうかを判定
                        if (faction.Count == 0 ||
                            faction.All(x => (relations[i] & (1 << (x - 1))) != 0))
                        {
                            // 全員と知り合いのときだけ追加
                            faction.Add(i + 1);
                        }
                    }
                }
                answer = Math.Max(answer, faction.Count);
            }
            Console.WriteLine(answer);
        }
    }
}