using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "Input5"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("4 6"); WillReturn.Add("5 5"); WillReturn.Add("2 3"); WillReturn.Add("4 4"); WillReturn.Add("1 1"); //YES } else if (InputPattern == "Input2") { WillReturn.Add("4 6"); WillReturn.Add("3 5"); WillReturn.Add("3 4"); WillReturn.Add("4 4"); WillReturn.Add("1 2"); //NO } else if (InputPattern == "Input3") { WillReturn.Add("2 4"); WillReturn.Add("0 1"); WillReturn.Add("0 1"); //YES } else if (InputPattern == "Input4") { WillReturn.Add("5 10"); WillReturn.Add("8 8"); WillReturn.Add("0 0"); WillReturn.Add("2 4"); WillReturn.Add("2 3"); WillReturn.Add("8 8"); //YES } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } struct LRDef { internal int L; internal int R; } static int M; static void Main() { List InputList = GetInputList(); int[] wkArr = { }; Action SplitAct = (pStr) => wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray(); SplitAct(InputList[0]); M = wkArr[1]; var LRList = new List(); for (int I = 1; I <= InputList.Count - 1; I++) { SplitAct(InputList[I]); LRList.Add(new LRDef() { L = wkArr[0], R = wkArr[1] }); } Console.WriteLine(ExecDFS(LRList) ? "YES" : "NO"); } struct JyoutaiDef { internal int CurrY; internal System.Collections.BitArray BanArr; //internal string FillLog; } //深さ優先探索で解の有無を判定する static bool ExecDFS(List pLRList) { var stk = new Stack(); JyoutaiDef WillPush; WillPush.CurrY = 0; WillPush.BanArr = new System.Collections.BitArray(M); //WillPush.FillLog = ""; stk.Push(WillPush); while (stk.Count > 0) { JyoutaiDef Popped = stk.Pop(); //クリア判定 if (Popped.CurrY > pLRList.Count - 1) { //Console.WriteLine(Popped.FillLog); return true; } Action PushSyori = (pLR) => { for (int I = pLR.L; I <= pLR.R; I++) { if (Popped.BanArr[I]) return; } WillPush.CurrY = Popped.CurrY + 1; WillPush.BanArr = new System.Collections.BitArray(Popped.BanArr); for (int I = pLR.L; I <= pLR.R; I++) { WillPush.BanArr[I] = true; } //WillPush.FillLog = Popped.FillLog + string.Format("{0}から{1}がピンクになります", // pLR.L, pLR.R); //WillPush.FillLog += Environment.NewLine; stk.Push(WillPush); }; PushSyori(pLRList[Popped.CurrY]); PushSyori(DeriveKaitenLR(pLRList[Popped.CurrY])); } return false; } //180度回転したLRを返す static LRDef DeriveKaitenLR(LRDef pLR) { int NewL = M - 1 - pLR.R; int NewR = M - 1 - pLR.L; return new LRDef() { L = NewL, R = NewR }; } }