ABC083-D Wide Flip

問題へのリンク

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("010");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("100000000");
            //8
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("00001111");
            //4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static string mS;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mS = InputList[0];

        // 共通区間のCharのSet
        var CommonSet = new HashSet<char>();

        int UB = mS.Length - 1;
        for (int I = 0; I <= UB; I++) {
            int RevInd = UB - I;

            if (I >= RevInd) {
                CommonSet.Add(mS[I]);
                CommonSet.Add(mS[RevInd]);

                if (CommonSet.Count > 1) {
                    Console.WriteLine(I);
                    return;
                }
            }
        }
        Console.WriteLine(mS.Length);
    }
}

解説

オセロセットを使って

○●●●●●○●
の場合で考察します。

区間の最小長さで、6の場合
最も左の区間をＬで
最も右の区間をＲで表すと

ＬＬＬＬＬＬ
　　ＲＲＲＲＲＲ
○●●●●●○●

になります。ＬとＲが被っている区間は、
必ず同時に裏返すことになるので
この区間の色が同じであることは、
解であることの必要条件と分かります。

そして、この必要条件を満たしていれば、
区間６と区間７で、任意のマスだけを反転するようにすれば、
全て同じ色にすることができます。