プロコン初心者日記

解いたプロコンの問題を保存しておくためのブログ

【AtCoder】ABC038 C. 単調増加

AtCoderの問題

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

参考書

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

難しさ(初心者目線)

・考え方***

・実装**

・面白さ***

問題概要

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

制約
1 ≦ N ≦ 105

方針

・普通にあるlに対して最大のrを求める方法だと最悪O(N2).
・ある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;
}