AGC-013-A Sorted Arrays

■■■問題■■■

長さNの配列Aが与えられます。
Aを何箇所かで切って、Aの連続した部分であるようないくつかの数列に分けます。

この時、分けられたあとの数列は全て、
単調非減少または単調非増加な列になっている必要があります。
最小で何個の数列に分ければ良いかを求めて下さい。

■■■入力■■■

N
A1 A2 ・・・ AN

●1 <= N  <= 10万
●1 <= Ai <= 10億
●Aiは全て整数である

■■■出力■■■

最小で何個の数列に分ければよいか出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("6");
            WillReturn.Add("1 2 3 2 2 1");
            //2
            //[1,2,3] と [2,2,1] に分ければよいです
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("9");
            WillReturn.Add("1 2 1 2 1 2 1 2 1");
            //5
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("7");
            WillReturn.Add("1 2 3 2 1 999999999 1000000000");
            //3
        }
        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(X => int.Parse(X)).ToArray();

        int SuuretuCnt = 1;
        int KouSuu = 0;
        int PrevInt = -1;
        bool CanZouka = true;
        bool CanGensyou = true;
        foreach (int EachA in AArr) {
            bool WillCreateNewSuuretu = false;
            KouSuu++;

            if (KouSuu >= 2) {
                //前の項より大きい場合
                if (PrevInt < EachA) {
                    CanGensyou = false;
                    if (CanZouka == false) {
                        WillCreateNewSuuretu = true;
                    }
                }
                //前の項より小さい場合
                if (PrevInt > EachA) {
                    CanZouka = false;
                    if (CanGensyou == false) {
                        WillCreateNewSuuretu = true;
                    }
                }
            }

            if (WillCreateNewSuuretu) {
                SuuretuCnt++;
                CanZouka = CanGensyou = true;
                KouSuu = 1;
            }
            PrevInt = EachA;
        }
        Console.WriteLine(SuuretuCnt);
    }
}

解説

広義単調増加 → 広義単調減少 → 広義単調増加 → 広義単調減少 → 省略
と繰り返すか、
広義単調減少 → 広義単調増加 → 広義単調減少 → 広義単調増加 → 省略
と繰り返すのが最善ですので、
貪欲法を使ってます。