AtCoderのAGC    次のAGCの問題へ    前のAGCの問題へ

AGC034-A Kenken Race


問題へのリンク


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

    static string mS;

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int A = wkArr[1] - 1;
        int B = wkArr[2] - 1;
        int C = wkArr[3] - 1;
        int D = wkArr[4] - 1;
        mS = InputList[1];
        int UB = mS.Length - 1;

        bool IsOK = true;
        if (ExistsSeqIwa(A, C)) IsOK = false;
        if (ExistsSeqIwa(B, D)) IsOK = false;

        // ABDC
        if (A < B && B < D && D < C) {
            bool CanJump = false;
            for (int I = B; I <= D; I++) {
                if (0 < I && I < UB) {
                    if (mS[I - 1] == '.' && mS[I] == '.' && mS[I + 1] == '.') {
                        CanJump = true;
                        break;
                    }
                }
            }

            if (CanJump == false) {
                IsOK = false;
            }
        }

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

    // 開始Indと終了Indを引数として、連続した岩があるかを返す
    static bool ExistsSeqIwa(int pStaInd, int pEndInd)
    {
        for (int I = pStaInd; I <= pEndInd - 1; I++) {
            if (mS[I] == '#' && mS[I + 1] == '#') {
                return true;
            }
        }
        return false;
    }
}


解説

制約で a < b なので
3つの場合に分けて考えます。
場合1 a < b < c < d
場合2 a < b < d < c
場合3 a < c < b < d

場合2と場合3は、
aからcまでの間に連続した岩がなく
bからdまでの間に連続した岩がなければOKと分かります。

場合1は、
場合2と場合3での判定に加えて、
ふぬけ君がBからDまでの位置のどこかにいる時に
すぬけ君が、ふぬけ君を飛び越える必要があるので、
その判定を行ってます。