これは典型かな。
https://www.hackerrank.com/contests/camypapercon03/challenges/adventure-calendar-contesuto
問題
N日間に、それぞれ新たにA[i]問を出題したい。
プレイヤーは毎日新規に一定数の問題を作れる時、問題が不足しないためには最小毎日何問問題を作ればよいか。
解法
毎日の作問数を二分探索して、あとは条件を満たすか判定すればよい。
int N; int A[101010]; bool ok(int v) { ll x=0,i; FOR(i,N) { x+=v; x-=A[i]; if(x<0) return 0; } return 1; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i]; int ret=(1<<30)-1; for(i=29;i>=0;i--) if(ok(ret-(1<<i))) ret -= 1<<i; cout<<ret<<endl; }
まとめ
以下の入力に対する解は1である。
すなわち10/1から毎日1問作問すれば、Saiko~ No Contesutoは3週に1回のペースをキープできる。
53 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4