ABC338-E Chords

問題へのリンク

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

    // 区間情報
    struct RangeInfoDef
    {
        internal int Sta;
        internal int End;
    }
    static List<RangeInfoDef> mRangeInfoList = new List<RangeInfoDef>();

    // 括弧情報
    struct BracketInfoDef
    {
        internal int ID;
        internal int Pos;
        internal char CharVal;
    }
    static List<BracketInfoDef> mBracketInfoList = new List<BracketInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);
        int N2 = N * 2; // 円環の対応

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);

            int Sta = wkArr.Min();
            int End = wkArr.Max();

            Action<int, int> AddAct = (pSta, pEnd) =>
            {
                RangeInfoDef WillAdd;
                WillAdd.Sta = pSta;
                WillAdd.End = pEnd;
                mRangeInfoList.Add(WillAdd);
            };

            if (Sta <= End) {
                AddAct(Sta, End);
                AddAct(Sta + N2, End + N2);
            }

            if (Sta > End) {
                AddAct(Sta, End + N2);
            }
        }

        // 開始位置の昇順にソート
        mRangeInfoList = mRangeInfoList.OrderBy(pX => pX.Sta).ToList();

        for (int I = 0; I <= mRangeInfoList.Count - 1; I++) {
            BracketInfoDef WillAdd;
            WillAdd.ID = I;
            WillAdd.Pos = mRangeInfoList[I].Sta;
            WillAdd.CharVal = '(';
            mBracketInfoList.Add(WillAdd);

            WillAdd.ID = I;
            WillAdd.Pos = mRangeInfoList[I].End;
            WillAdd.CharVal = ')';
            mBracketInfoList.Add(WillAdd);
        }

        // 位置の昇順にソート
        mBracketInfoList = mBracketInfoList.OrderBy(pX => pX.Pos).ToList();

        //mBracketInfoList.ForEach(pX=>
        //    Console.WriteLine("Pos={0},ID={1},CharVal={2}", pX.Pos, pX.ID, pX.CharVal));

        // 括弧が全て入れ子になってるかを判定
        var Stk = new Stack<int>();

        bool IsCross = false;
        foreach (BracketInfoDef EachBracketInfo in mBracketInfoList) {
            if (EachBracketInfo.CharVal == '(') {
                Stk.Push(EachBracketInfo.ID);
                continue;
            }
            if (EachBracketInfo.CharVal == ')') {
                if (Stk.Count == 0) {
                    IsCross = true;
                    break;
                }
                int Popped = Stk.Pop();
                if (Popped != EachBracketInfo.ID) {
                    IsCross = true;
                    break;
                }
            }
        }

        if (IsCross) Console.WriteLine("Yes");
        else Console.WriteLine("No");
    }
}

解説

例えば、正六角形の外接円であれば
1 2 3 4 5 6
の数直線で考えることができます。

さらに、円環の対応で、2倍に伸ばした下記で考えることができます。
1 2 3 4 5 6 7 8 9 10 11 12

後は、区間の開始を開き括弧
区間終了を閉じ括弧として、
Stackを使い、ネストした括弧のみからなるかを判定すれば良いです。