ABC147-C HonestOrUnkind2

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("1");
            WillReturn.Add("2 1");
            WillReturn.Add("1");
            WillReturn.Add("1 1");
            WillReturn.Add("1");
            WillReturn.Add("2 0");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("2");
            WillReturn.Add("2 1");
            WillReturn.Add("3 0");
            WillReturn.Add("2");
            WillReturn.Add("3 1");
            WillReturn.Add("1 0");
            WillReturn.Add("2");
            WillReturn.Add("1 1");
            WillReturn.Add("2 0");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2");
            WillReturn.Add("1");
            WillReturn.Add("2 0");
            WillReturn.Add("1");
            WillReturn.Add("1 0");
            //1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct SyougenInfoDef
    {
        internal int TargetNum;
        internal bool IsHonest;
    }

    static int mN;

    // 証言リスト[人番号]なDict
    static SortedDictionary<int, List<SyougenInfoDef>> mSyougenListDict =
        new SortedDictionary<int, List<SyougenInfoDef>>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        mN = int.Parse(InputList[0]);

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        for (int I = 1; I <= mN; I++) {
            mSyougenListDict[I] = new List<SyougenInfoDef>();
        }

        int CurrNum = 0;
        int RestSyougen = 0;
        for (int I = 1; I <= InputList.Count - 1; I++) {
            if (RestSyougen == 0) {
                RestSyougen = int.Parse(InputList[I]);
                CurrNum++;
                continue;
            }
            SplitAct(InputList[I]);
            SyougenInfoDef WillAdd;
            WillAdd.TargetNum = wkArr[0];
            WillAdd.IsHonest = (wkArr[1] == 1);
            mSyougenListDict[CurrNum].Add(WillAdd);
            RestSyougen--;
        }

        foreach (var EachPair in mSyougenListDict) {
            //Console.WriteLine("{0}の証言リスト", EachPair.Key);
            //EachPair.Value.ForEach(
            //    pX => Console.WriteLine("{0}のIsHonest={1}", pX.TargetNum, pX.IsHonest));
        }

        Solve();
    }

    static void Solve()
    {
        List<int> PatternList = DerivePatternList();

        int Answer = 0;
        foreach (int EachPattern in PatternList) {
            //Console.WriteLine("IsOKPattern({0})={1}", EachPattern, IsOKPattern(EachPattern));
            if (IsOKPattern(EachPattern)) {
                Answer = Math.Max(Answer, BitOnCnt(EachPattern));
            }
        }
        Console.WriteLine(Answer);
    }

    // 矛盾の無い証言かを判定
    static bool IsOKPattern(int pPattern)
    {
        foreach (var EachPair in mSyougenListDict) {
            foreach (SyougenInfoDef EachSyougenInfo in EachPair.Value) {
                int TargetNum = EachSyougenInfo.TargetNum;
                bool IsHonest = EachSyougenInfo.IsHonest;

                if (IsBitON(pPattern, EachPair.Key) == false) {
                    continue;
                }

                if (IsHonest && IsBitON(pPattern, TargetNum) == false) {
                    return false;
                }
                if (IsHonest == false && IsBitON(pPattern, TargetNum)) {
                    return false;
                }
            }
        }
        return true;
    }

    // Int型を引数として、右からNビット目が立ってるかを返す
    static bool IsBitON(int pInt, int pN)
    {
        int TargetBit = (int)Math.Pow(2, pN - 1);
        return (pInt & TargetBit) > 0;
    }

    // Int型を引数として、ビットが立ってる数を返す
    static int BitOnCnt(int pInt)
    {
        int WillReturn = 0;
        while (pInt > 0) {
            if (pInt % 2 == 1) {
                WillReturn++;
            }
            pInt /= 2;
        }
        return WillReturn;
    }

    // ビット全探索用に0から(2のN乗)-1 までの値のListを返す
    static List<int> DerivePatternList()
    {
        var WillReturn = new List<int>();

        int Bekijyou = (int)Math.Pow(2, mN);
        for (int I = 0; I <= Bekijyou - 1; I++) {
            WillReturn.Add(I);
        }
        return WillReturn;
    }
}

解説

N人が正直かどうかの順列を、ビット全探索で列挙し、
矛盾が無いかを検証してます。