ARC179-B Between B and B

問題へのリンク

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 4");
            WillReturn.Add("2 1 2");
            //14
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 8");
            WillReturn.Add("1 2 3 4");
            //65536
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 9");
            WillReturn.Add("2 3 4 1");
            //628
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const int Hou = 998244353;

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int M = wkArr[0];
        int N = wkArr[1];

        int[] XArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        int[] BitArr = new int[M + 1];
        int BitVal = 1;
        for (int I = 1; I <= M; I++) {
            BitArr[I] = BitVal;
            BitVal *= 2;
        }

        int AllBitOn = (1 << M) - 1;

        // 場合の数[使用可能BitSet]
        int[] PrevDP = new int[AllBitOn + 1];
        PrevDP[AllBitOn] = 1;

        int XArrUB = XArr.GetUpperBound(0);
        for (int I = 1; I <= N; I++) {
            int[] CurrDP = new int[AllBitOn + 1];
            for (int J = 0; J <= AllBitOn; J++) {
                if (PrevDP[J] == 0) continue;

                for (int EachKey = 1; EachKey <= M; EachKey++) {
                    // 使用不可の場合
                    if ((J & BitArr[EachKey]) == 0) continue;

                    // 使用が必要になるもの
                    int NeedVal = XArr[EachKey - 1];

                    int NewKey = J;
                    if (NeedVal != EachKey) {
                        if ((NewKey & BitArr[EachKey]) > 0) {
                            NewKey -= BitArr[EachKey];
                        }
                    }

                    // 使用を解禁するもの
                    for (int K = 0; K <= XArrUB; K++) {
                        if (XArr[K] == EachKey) {
                            NewKey |= BitArr[K + 1];
                        }
                    }

                    CurrDP[NewKey] += PrevDP[J];
                    CurrDP[NewKey] %= Hou;
                }
            }

            PrevDP = CurrDP;
        }

        int Answer = 0;
        foreach (int EachInt in PrevDP) {
            Answer += EachInt;
            Answer %= Hou;
        }
        Console.WriteLine(Answer);
    }
}

解説

場合の数[使用可能BitSet]で解いてます。

定数倍高速化で
●Dictではなく配列を使う
●配列のGetUpperBoundメソッドの結果をキャッシュする
という手法を使ってます。