Codeforces #345 Div1. B. Image Preview

問題の理解にちょっと手間取った。
http://codeforces.com/contest/650/problem/B

問題

N枚の写真を持つ携帯がある。
画面には同時に1枚の写真が表示され、左右にスワイプすると隣の写真が表示される。
写真は円周状に並んでおり、1枚目からN枚目にスワイプで移動することもできる。
写真1枚分のスワイプはa秒かかる。

この携帯でN枚の写真を確認したい。
まだ確認してない写真を確認するのに1秒かかる。
また、横になっている写真があると縦にしなければいけない。この操作に3秒かかる。

最適な順でスワイプする場合、T秒以内に最大何枚の写真を確認できるか。

解法

スワイプ順の戦略は次のいずれかである。

• ひたすら右に1周回す
• ひたすら左に1周回す
• 途中まで右に回し、その後左に回して最初に戻ってから、さらに残りを左に回して全部見る
• 途中まで左に回し、その後右に回して最初に戻ってから、さらに残りを右に回して全部見る

初期位置から左もしくは右に何枚分スワイプ＋確認するとき、何秒かかかるかの累積和をもっておく。
それを用いて、後ろの2つのケースについて折り返し位置を総当たりし、それぞれ折り返して最初の位置に戻ったとき、あと何枚見れるかを計算できる。
尺取法ならO(N)、二分探索でO(NlogN)かな。

int N;
ll A,B,T;
string S;
ll R[505050],L[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B>>T;
	cin>>S;
	FORR(r,S) r=r=='w';
	
	for(i=1;i<N;i++) R[i]=R[i-1]+1+A+B*S[i];
	for(i=1;i<N;i++) L[i]=L[i-1]+1+A+B*S[N-i];
	L[N]=R[N]=1LL<<60;
	
	T-=1+B*S[0];
	if(T<0) return _P("0\n");
	int ret=1;
	ret=max(ret,1+(lower_bound(R,R+N,T+1)-R)-1);
	ret=max(ret,1+(lower_bound(L,L+N,T+1)-L)-1);
	for(i=1;i<N;i++) if(T-R[i]-A*i>0) ret=max(ret,1+i+(lower_bound(L,L+N,T-R[i]-A*i+1)-L-1));
	for(i=1;i<N;i++) if(T-L[i]-A*i>0) ret=max(ret,1+i+(lower_bound(R,R+N,T-L[i]-A*i+1)-R-1));
	ret=min(ret,N);
	
	cout<<ret<<endl;
	
}

まとめ

イマドキっぽい？問題。