ABC418-D XNOR Operation

問題へのリンク

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("110");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("0000");
            //4
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("30");
            WillReturn.Add("011011100101110111100010011010");
            //225
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        char[] CharArr = InputList[1].ToCharArray();

        // 場合の数[0の個数 , 1の個数]
        var PrevDP = new long[2 + 1, 2 + 1];
        PrevDP[0, 0] = 1;

        long Answer = 0;
        foreach (char EachChar in CharArr) {
            var CurrDP = new long[2 + 1, 2 + 1];

            Action<long, long, long> UpdateAct = (pNewI, pNewJ, pAddVal) =>
            {
                if (pNewI == 3) pNewI = 1;
                if (pNewJ == 3) pNewJ = 1;
                CurrDP[pNewI, pNewJ] += pAddVal;
            };

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

                    if (EachChar == '0') {
                        UpdateAct(I + 1, J, PrevDP[I, J]);
                    }
                    else {
                        UpdateAct(I, J + 1, PrevDP[I, J]);
                    }
                }
            }

            Answer += CurrDP[0, 1];
            Answer += CurrDP[0, 2];
            Answer += CurrDP[2, 0];
            Answer += CurrDP[2, 1];
            Answer += CurrDP[2, 2];

            PrevDP = CurrDP;
            PrevDP[0, 0]++;
        }
        Console.WriteLine(Answer);
    }
}

解説

0 と 0 が 1
0 と 1 が 0
1 と 0 が 0
1 と 1 が 1
になるので、0の個数の偶奇は不変量だと分かります。

これをふまえて、
場合の数[0の個数 , 1の個数]
でDPし、個数が3になったら、1にすり替えしてます。

DPテーブルを更新しつつ、
[0,1から2]
[2,0から2]
を解に計上してます。