読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

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;
}