Croc Champ 2013 - Final : B. Context Advertising

本番問題文を勘違いした問題。
http://codeforces.com/contest/309/problem/B

問題

N個の単語のうち、連続するいくつかの単語をR行C文字分の矩形領域におしこめたい。
単語間は１つ以上の空白が必要で、かつ単語が行間で分割されてはならない。
矩形領域に入る単語数を最大化し、例を出力せよ。

解法

本番、行内の単語が連続していれば行間では異なっていてもいいと勘違いした…。

まず尺取法を使い、各単語から開始したとき１行に何単語入るかカウントする。
この時、単語間の空白を考慮するのは面倒なので、行の先頭にも空白が必要でその代り１行(C+1)文字入ると考えると常に空白を付けたのと同じになるので行頭処理が楽。

あとは、各単語から初めてR行で何単語入るか数えるわけだが、ここでdoublingを使うことでO(R)ではなくO(logR)で数え上げ可能。
よって全体の計算量はO(N log R)ぐらい。
後は単語数が最大になる単語を出力するだけ。

int N,R,C;
int I[1000010],W[1000010];
int MW[23][1000010];
char S[7000010];


void solve() {
	int f,r,i,j,k,l,x,y,tx,ty,aa[5];
	
	cin>>N>>R>>C;
	C++;
	j=0;
	FOR(i,N) {
		string s;
		cin>>s;
		I[i]=j;
		W[i]=1+s.size();
		strcpy(S+j,s.c_str());
		j+=W[i];
	}
	
	int tl,tw=-1;
	FOR(i,N) {
		if(tw<=i) {
			if(W[i]>C) {
				MW[0][i]=i;
				continue;
			}
			tw=i+1;
			tl=W[i];
		}
		while(tw<N && tl+W[tw]<=C) tl += W[tw++];
		MW[0][i]=tw;
		tl -= W[i];
	}
	MW[0][N]=N;
	
	//doubling
	FOR(i,21) FOR(x,N+1) MW[i+1][x] = MW[i][MW[i][x]];
	int ma=0,id=-1;
	FOR(x,N+1) {
		y=x;
		for(i=20;i>=0;i--) if(R & (1<<i)) y=MW[i][y];
		if(y-x>ma) ma=y-x,id=x;
	}

	if(ma==0) return;
	for(x=id,r=0;x<id+ma && r<R;) {
		y = 0;
		while(x<id+ma && y+W[x]<=C) {
			if(y!=0) _P(" ");
			_P("%s",S+I[x]);
			y+=W[x];
			x++;
		}
		if(y==0) break;
		r++;
		_P("\n");
	}
	
	return;
}

まとめ

問題文の見落としがひどい。
まぁ見落とさなくてもdoublingがわからなくて解けなかったけどさ。
doublingは前も気づかなかったし、考える癖をつけないとな。