【AtCoder】ABC038 C. 単調増加

AtCoderの問題

C: 単調増加 - AtCoder Beginner Contest 038 | AtCoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ（初心者目線）

・考え方***

・実装**

・面白さ***

問題概要

・N個の数からなる数列が与えられる.
・が単調増加、すなわち l≦r であってa_i<a_i+1がl≦i<r を満たす全てのiに対して成り立つような(l,r)の数を求めよ.

制約
1 ≦ N ≦ 10⁵

方針

・普通にあるlに対して最大のrを求める方法だと最悪O(N²).
・あるlに対して最大のrを求めたら、l+1<rの時l+1に対しても同じrとなる.
・l+1=rとなったら再び最大のrを求める.
・よって全てのlの合計でrを探すのにN回しかループしないのでO(N)となり間に合う.

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//答え見た

int main(){
    int N;
    cin >> N;
    int a[N+1];
    FOR(i, 0, N) cin>>a[i];
    a[N] = 0;
    int l = 0, r = 0;
    ll ans = 0;
    while(l < N){
        while(a[r+1] > a[r]) r++;
        ans += r - l + 1;
        l++;
        if(l==r+1) r++;
    }
    cout << ans << endl;
}