ABC199-E Permutation

問題へのリンク

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 1");
            WillReturn.Add("2 2 1");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 2");
            WillReturn.Add("3 3 2");
            WillReturn.Add("4 4 3");
            //90
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("18 0");
            //6402373705728000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct XYZInfoDef
    {
        internal long X;
        internal long Y;
        internal long Z;
    }
    static List<XYZInfoDef> mXYZInfoList = new List<XYZInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();

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

        SplitAct(InputList[0]);
        long N = wkArr[0];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            XYZInfoDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            WillAdd.Z = wkArr[2];
            mXYZInfoList.Add(WillAdd);
        }

        long AllBitOn = (1 << (int)N) - 1;

        // 場合の数[登場した数字のBitSet]
        long[] PrevDP = new long[AllBitOn + 1];
        PrevDP[0] = 1;

        for (long I = 1; I <= N; I++) {
            long[] CurrDP = new long[AllBitOn + 1];

            for (long J = 0; J <= AllBitOn; J++) {
                if (PrevDP[J] == 0) continue;

                for (long K = 1; K <= N; K++) {
                    long CurrBit = (1 << (int)(K - 1));

                    // 再選択は不可
                    if ((J & CurrBit) > 0) {
                        continue;
                    }

                    long NewJ = J | CurrBit;
                    if (IsOKBit(NewJ)) {
                        CurrDP[NewJ] += PrevDP[J];
                    }
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP[AllBitOn]);
    }

    static Dictionary<long, bool> mMemoDict = new Dictionary<long, bool>();

    // OKのBitかを判定
    static bool IsOKBit(long pBit)
    {
        if (mMemoDict.ContainsKey(pBit)) {
            return mMemoDict[pBit];
        }

        // ビットの数を求める
        long BitOnCnt = 0;
        long CopiedBit = pBit;
        while (CopiedBit > 0) {
            if (CopiedBit % 2 == 1) {
                BitOnCnt++;
            }
            CopiedBit /= 2;
        }

        foreach (XYZInfoDef EachXYZInfoDef in mXYZInfoList) {
            if (EachXYZInfoDef.X != BitOnCnt) continue;

            long Y = EachXYZInfoDef.Y;
            long Z = EachXYZInfoDef.Z;

            long YBit = 1 << (int)(Y - 1);

            long LowerCnt = 0;
            while (YBit > 0) {
                if ((pBit & YBit) > 0) {
                    LowerCnt++;
                }
                YBit /= 2;
            }
            if (LowerCnt > Z) return mMemoDict[pBit] = false;
        }
        return mMemoDict[pBit] = true;
    }
}

解説

場合の数[登場した数字のBitSet]
をBitDPで更新してます。