CODE FESTIVAL 2016 Qual B : D - Greedy customers

700ptにしては簡単？
http://code-festival-2016-qualb.contest.atcoder.jp/tasks/codefestival_2016_qualB_d

問題

N要素の正整数列A[i]がある。
ここから以下の処理を何回行えるか。

• 各処理では、ある1要素A[i]から以下の条件を満たす整数xを減算する。
  • 減算後のA[i]は正でなければならない。
  • A[j] (j＜i)となるA[j]でx以下のものがあってはならない。

解法

A[0]は1になるまで1回ずつ処理を行えばよい。
以下、A[i]を順に出来るだけ小さいところまで減らしていく。

A[0..(i-1)]のうちの最大値をPとする。

• xは(P+1)以上でなければならない。
  • よってA[i]≦P+1であれば、減算できない。なお、A[i]=P+1の場合、次にA[i+1]を処理するときにPが1増えていることになる。
  • A[i]≧xであれば、x=P+1とし、(A[i]-1)/x回処理を行えばよい。 処理後は1≦A[i]≦Pを満たせるので、Pは更新されない。

int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=0;
	int pre=0;
	
	FOR(i,N) {
		cin>>x;
		if(pre==0) {
			ret += x-1;
			pre=1;
		}
		else if(x==pre+1) {
			pre++;
		}
		else if(x>pre+1) {
			ret += (x-1)/(pre+1);
		}
	}
	cout<<ret<<endl;
}

まとめ

考察が若干面倒とはいえ、500pt位でもよさそう。