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位でもよさそう。