ARC138-B 01 Generation

問題へのリンク

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("4");
            WillReturn.Add("0 1 1 0");
            //Yes
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("1 0 0 0");
            //No
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4");
            WillReturn.Add("0 0 0 1");
            //No
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        var InsLinkedList = new LinkedList<int>(AArr);

        int FlipCnt = 0;
        while (InsLinkedList.Count > 0) {
            int FirstVal = InsLinkedList.First.Value;
            int LastVal = InsLinkedList.Last.Value;
            FirstVal = (FirstVal + FlipCnt) % 2;
            LastVal = (LastVal + FlipCnt) % 2;

            if (LastVal == 0) {
                InsLinkedList.RemoveLast();
            }
            else {
                if (FirstVal == 0) {
                    InsLinkedList.RemoveFirst();
                    FlipCnt++;
                }
                else {
                    Console.WriteLine("No");
                    return;
                }
            }
        }
        Console.WriteLine("Yes");
    }
}

解説

操作1 flipしてから、先頭に0を付与
操作2 末尾に0を付与

なので、逆の操作は、
操作1 先頭の0を削除してから、flip
操作2 末尾の0を削除
になります。

この状態でDFSで解こうとすると、TLEするので
遷移を減らすことを考えます。
操作1と操作2の両方が可能な状態では、
操作1を2回行うか
操作2を1回行うか
の遷移になります。

操作1を2回行うのは、言い換えると、先頭の01を削除
操作2を1回行うのは、末尾の0を削除
となります。

この2つの操作は、任意の順番で行っていいので
操作2を優先して、DFSでなくて、貪欲法で解くことができます。