ARC119-B Electric Board

問題へのリンク

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("7");
            WillReturn.Add("1110110");
            WillReturn.Add("1010111");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("20");
            WillReturn.Add("11111000000000011111");
            WillReturn.Add("11111000000000011111");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6");
            WillReturn.Add("111100");
            WillReturn.Add("111000");
            //-1
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("119");
            WillReturn.Add("10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011");
            WillReturn.Add("11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011");
            //22
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[1];
        string T = InputList[2];

        int ZeroCntS = S.ToCharArray().Count(pX => pX == '0');
        int ZeroCntT = T.ToCharArray().Count(pX => pX == '0');

        if (ZeroCntS != ZeroCntT) {
            Console.WriteLine(-1);
            return;
        }

        var ZeroIndListS = new List<long>();
        var ZeroIndListT = new List<long>();
        for (int I = 0; I <= S.Length - 1; I++) {
            if (S[I] == '0') ZeroIndListS.Add(I);
        }
        for (int I = 0; I <= T.Length - 1; I++) {
            if (T[I] == '0') ZeroIndListT.Add(I);
        }

        int Answer = 0;
        for (int I = 0; I <= ZeroIndListS.Count - 1; I++) {
            if (ZeroIndListS[I] != ZeroIndListT[I]) {
                Answer++;
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

最初に、SとTで、0の数が不一致だったら
どうやっても一致できないと判定できます。

正規表現で表現すると
01+ の、先頭と末尾が交換可能
1+0 の、先頭と末尾を交換可能
と表現できます。

0に番号を付けて考えると
番号を飛び越すような移動はできないので

SとTの0を昇順に見ていき
不一致な数が解になります。