ABC038_C

二重ループの効率化の問題

TLEだったやつ

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 100000;
int main()
{
    int n,a[MAX_N+1],l,r,ans = 0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        l = i;
        for(int j=l+1;j<=n;j++){
            if(a[l++]<a[j]){
                ans++;
            }else{
                break;
            }
        }
    }
    cout<<ans+n<<endl;
    return 0;
}

しゃくとり法を用いた解法

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 1000100;
int main()
{
    int n,l,r,a[MAX_N];
    long long int ans = 0;
    cin >> n;
    for(int i=0;i<n;i++)cin>>a[i];
    l = 0;
    r = 1;
    ans = 0;
    if(n>=2){
        while(l<n-1){
            if(r==l)r++;
            while(a[r-1]<a[r])r++;//(l,r)を満たす最大のrを見つける
            ans += (r-l-1);
            l++;
        }
    }
    ans += n;
    cout<<ans<<endl;
    return 0;
}

数列の和の計算を使った解法(本質的には上と同じ)
例えば1,2,3という数列に含まれる部分単調増加数列の個数は{1,12,123,2,23,3}の6つ
これは要素数1の数列が{1,2,3}の3個, 要素数2の数列が{12,23}の2個, 要素数3の数列が{123}の1個となるので1+2+3=6となる.
よって和の公式を使ってlength = 数列の長さ, length * (length+1)/2で部分単調増加数列の個数が出る.
あとはleftの位置を更新していけばよい.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
static const int MAX_N = 1000100;

int main()
{
    int n,l,r,a[MAX_N];
    ll ans=0,length;
    cin >> n;
    for(int i=0;i<n;i++)cin>>a[i];
    ans = 0;
    length = 1;
    for(int i=0;i<n;i++){
        if(a[i]<a[i+1]){
            length++;
        }
        else{//今tmpは単調増加列の長さを示している.
            ans += length*(length+1)/2;
            length = 1;
        }
    }

    cout<<ans<<endl;
    return 0;
}