CSAcademy Round #59 : D. Editor

こっちは割とすんなり。
https://csacademy.com/contest/round-59/task/editor/

問題

N個の単語S[i]がある。
これらを順にH*Wの２次元領域に埋めていくことを考えよう。
各単語は行の先頭から順にマスを埋めるように配置される。
単語の間は１マスの空白を入れ、また単語が行内に入りきらない場合、次の行から再開する。

N個単語を埋めてもまだ空きマスがあるなら、また単語の先頭から埋めていく。
領域内に最大何個の単語を埋められるか。

解法

ダブリングで解く。
まず尺取り法や二分探索で、各単語を先頭に配置した場合、その行に最大何個の単語を詰められるか求めよう。
あとはダブリングで２，４，８…行に詰められる単語数がわかるので、それらを合わせてH行に詰められる単語数を求められる。

int N;
ll W,H;
ll L[301010];
ll S[301010];
ll from[301010],to[301010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cin>>W>>H;
	FOR(i,N) {
		cin>>L[i];
		S[i+1]=S[i]+L[i]+1;
	}
	FOR(i,N) S[N+i+1]=S[N+i]+L[i]+1;
	FOR(i,N) S[2*N+i+1]=S[2*N+i]+L[i]+1;
	
	FOR(i,N) from[i]=W/S[N]*N;
	W%=S[N];
	x=0;
	FOR(i,N) {
		while(S[x+1]-S[i]-1<=W) x++;
		from[i]+=x-i;
	}
	
	ll ret=0;
	while(H) {
		
		if(H%2) ret += from[ret%N];
		FOR(i,N) to[i]=from[(i+from[i])%N]+from[i];
		swap(from,to);
		
		H>>=1;
	}
	cout<<(ret+N-1)/N<<endl;
	
}

まとめ

単語間の空白のせいで苦労した人も多かった様子。
先に各行１文字幅を増やしておくと、単語あたり|S[i]|+1文字と簡単に考えられていいかもね。