ABC-038-C 単調増加

■■■問題■■■

N個の数からなる数列が与えられます。i番目の数をaiと呼びましょう。
al,al+1,・・・,ar が単調増加、
すなわち l <= r であって ai < ai+1 が l <= i < r を満たす
全てのiに対して成り立つような(l,r)の数を求めてください。

■■■入力■■■

N
a1 a2 ・・・ aN

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

■■■出力■■■

al,al+1, ・・・ ,ar が単調増加となるような(l,r)の数を1行に出力せよ。

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("5");
            WillReturn.Add("1 2 3 2 1");
            //8
            //条件を満たす(l,r)は
            //(1,1),(1,2),(1,3),(2,2),(2,3),(3,3),(4,4),(5,5)
            //の8つです。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("1 2 3 4");
            //10
            //1 <= l <= r <= Nを満たす(l,r)全てが条件を満たします。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6");
            WillReturn.Add("3 3 4 1 2 2");
            //8
            //例えば、3,3,4はこの問題で単調増加ではないことに注意してください
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("6");
            WillReturn.Add("1 5 2 3 4 2");
            //10
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        int[] wkArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        int UB = wkArr.GetUpperBound(0);
        long SeqCnt = 0;
        long AnswerCnt = 0;

        for (int I = 0; I <= UB; I++) {
            SeqCnt++;
            if (I == UB || wkArr[I] >= wkArr[I + 1]) {
                //自然数の和の公式
                AnswerCnt += SeqCnt * (SeqCnt + 1) / 2;
                SeqCnt = 0;
            }
        }
        Console.WriteLine(AnswerCnt);
    }
}

解説

単調増加な列数を求めて
1からnまでの自然数の和の公式 n*(n+1)/2
を使ってます。