kmjp's blog

競技プログラミング参加記です

Saiko~ No Contesuto #03 : Adventure Calendar Contesuto

これは典型かな。
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