ABC265-E Warp

問題へのリンク

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

    const long Hou = 998244353;

    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];
        long UB = N;

        SplitAct(InputList[1]);
        long A = wkArr[0];
        long B = wkArr[1];
        long C = wkArr[2];
        long D = wkArr[3];
        long E = wkArr[4];
        long F = wkArr[5];

        var NGPosSetDict = new Dictionary<long, HashSet<long>>();
        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            long X = wkArr[0];
            long Y = wkArr[1];

            if (NGPosSetDict.ContainsKey(X) == false) {
                NGPosSetDict[X] = new HashSet<long>();
            }
            NGPosSetDict[X].Add(Y);
        }

        // 場合の数[移動1の回数 , 移動2の回数] なDP表
        long[,] PrevDP = new long[UB + 1, UB + 1];
        PrevDP[0, 0] = 1;

        for (long I = 1; I <= N; I++) {
            long[,] CurrDP = new long[UB + 1, UB + 1];
            for (long J = 0; J <= I - 1; J++) {
                for (long K = 0; K <= I - 1; K++) {
                    if (PrevDP[J, K] == 0) continue;

                    Action<long, long> AddAct = (pNewJ, pNewK) =>
                    {
                        long NewL = I - pNewJ - pNewK;
                        long NewX = pNewJ * A + pNewK * C + NewL * E;
                        long NewY = pNewJ * B + pNewK * D + NewL * F;

                        if (NGPosSetDict.ContainsKey(NewX)) {
                            if (NGPosSetDict[NewX].Contains(NewY)) {
                                return;
                            }
                        }

                        CurrDP[pNewJ, pNewK] += PrevDP[J, K];
                        CurrDP[pNewJ, pNewK] %= Hou;
                    };

                    AddAct(J, K);
                    AddAct(J, K + 1);
                    AddAct(J + 1, K);
                }
            }
            PrevDP = CurrDP;
        }

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

解説

移動1の回数と、移動2の回数を状態に持ってDPしてます。

移動3の回数は、引き算で分かるので
移動3の回数を持たないことで、状態数を減らしてます。