ARC-017-B 解像度が低い。

■■■問題■■■

大変なことになってしまった！！

なんと、我が社の次の決算報告会の発表者に僕が選ばれてしまったのだ！
我が社のイメージのためにも、そして社内での僕の地位のためにも、
なんとしても好印象を与える発表をせねばならない。

我が社の直近の業績はN個の数からなる数列で表される。
これを発表したいところだけれど・・・、
あいにく、我が社の業績はそこまで良いとは言えないのが実情だ。
一体どうすればいいんだろうか・・・。

途方に暮れた僕は、とりあえず発表会場の設備を調査した。
なんと、これが僕の生まれ持った強運か、
プロジェクターの解像度がとても低く、
画面には一度にK個の数を表示するのが限界であることがわかった。
業績の数列のうちの連続するK個をうまく選べれば、
我が社の業績がうなぎのぼりであるように見せかけられるのではないだろうか？

これは最高のアイデアだと思ったが、聴衆から
「それって業績の一部ですよね？他の部分も見せて頂けませんか？」と言われたらジ・エンドだ。
そこで用意周到な僕は、業績の数列のうち、プロジェクターで映したときに
業績が常に上昇しているように見せられるような箇所がいくつあるのか、
事前に調べておくことにした。

常に成長を続ける企業であるとアピールするためには、
ある値はその前の値より真に大きくなくてはいけない。
つまり 100,200,300 という列は常に上昇していると考えるが、 
100,200,200 という列は常に上昇しているとは考えない。

※この問題文はフィクションです。業績はきちんと発表しましょう。

■■■入力■■■

N K
A1
A2
・
・
・
AN


●1行目には、業績を表す数列の要素数 N(1 <= N <= 30万)、
  プロジェクターで一度に表示できる数の個数 K(1 <= K <= N) が半角空白区切りで与えられる。
●2行目からN行では、業績を表す数列が与えられる。
  このうちi行目がi番目の業績を表す整数 Ai(1 <= Ai <= 30万) である。

■■■出力■■■

業績を表す数列のうち、プロジェクターで画面に映せるようなK個の連続した部分で、
その部分だけ見ると業績が常に上昇しているように見えるものの個数を標準出力に1行で出力せよ。

■■■サンプルケースのイメージ■■■

入出力例2で常に上昇しているように見える箇所は以下の画像に矢印で示された5箇所となる。

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

    static List GetInputList()
    {
        var WillReturn = new List();

        if (InputPattern == "Input1") {
            WillReturn.Add("10 4");
            WillReturn.Add("100");
            WillReturn.Add("300");
            WillReturn.Add("600");
            WillReturn.Add("700");
            WillReturn.Add("800");
            WillReturn.Add("400");
            WillReturn.Add("500");
            WillReturn.Add("800");
            WillReturn.Add("900");
            WillReturn.Add("900");
            //3
            //業績を表す10個の数列から、連続する4個を抜き出してみると、
            //●(100,300,600,700)は常に上昇しているように見える
            //●(300,600,700,800)は常に上昇しているように見える
            //●(600,700,800,400)は常に上昇しているように見えない
            //●(700,800,400,500)は常に上昇しているように見えない
            //●(800,400,500,800)は常に上昇しているように見えない
            //●(400,500,800,900)は常に上昇しているように見える
            //●(500,800,900,900)は常に上昇しているように見えない
            //となるので、答えは3であることがわかる。 
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 3");
            WillReturn.Add("10");
            WillReturn.Add("40");
            WillReturn.Add("50");
            WillReturn.Add("80");
            WillReturn.Add("90");
            WillReturn.Add("30");
            WillReturn.Add("20");
            WillReturn.Add("40");
            WillReturn.Add("90");
            WillReturn.Add("95");
            //5
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8 4");
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("3");
            WillReturn.Add("4");
            WillReturn.Add("5");
            WillReturn.Add("6");
            WillReturn.Add("7");
            WillReturn.Add("8");
            //5
            //元々の業績が常に上昇しているので、
            //どこをプロジェクターに映しても大丈夫である。 
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("8 2");
            WillReturn.Add("100000");
            WillReturn.Add("90000");
            WillReturn.Add("50000");
            WillReturn.Add("30000");
            WillReturn.Add("10000");
            WillReturn.Add("4000");
            WillReturn.Add("200");
            WillReturn.Add("1");
            //0
            //元々の業績があまりに良くない場合、
            //どこを映しても業績を右肩上がりに見せかけられないことがある。 
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int K = wkArr[1];
        int[] AArr = InputList.Skip(1).Select(X => int.Parse(X)).ToArray();
        int UB = AArr.GetUpperBound(0);

        int SeqCnt = 1;
        long Answer = 0;
        for (int I = 0; I <= UB; I++) {
            if (0 < I && AArr[I - 1] < AArr[I]) {
                SeqCnt++;
            }

            if (I == UB || 0 < I && AArr[I - 1] >= AArr[I]) {
                if (SeqCnt >= K) Answer += SeqCnt - K + 1;
                SeqCnt = 1;
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

単調増加な項数を求めて、解に計上してます。