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