AOJ 1333 Beautiful Spacing

AOJ 動的計画法 データ構造

問題

n個の単語を、幅wのフィールドに、好きな行数にわけて書く。

  • 一つの単語は、間をあけずに、行をまたがずに書く。
  • 単語と単語の間は一つ以上のスペースを空けて書く
  • 行の先頭および末尾にはスペースを空けずに書く。
  • ただし、最後の1行の末尾はスペースを空けてよい。

このとき、単語と単語の間のスペースの最大値をなるべく小さくしたい。
その値を求めよ。

制約条件

n≦50000
w≦80000
単語は必ず一行に二つ以上書ける

方針

無理やり動的計画法で解いた。
普通は二分探索をするらしい。


単語をi個ちょうど使ったときの今までのスペースの最大値の最小値を、dp[i]とおく。
これを更新していくDPをするが、愚直に更新するとO(n^2).
（単語iからjを一行に入れるコストがO(1)で求まるとして）


これを高速化したい。
コストの関数に注目すると、
cost(i, j)は、jが増えると単調非増加になっている。
また、iが増えると単調非減少になっている。


dp[j] = min(dp[j], max(dp[i], cost(i, j))と更新されるので、
max(dp[i], cost(i, j)はあるところまでは非増加で、途中から横ばいになる。
iが1増えたとき、横ばいのところまでは、cost(i + 1, j) > cost(i, j)であるので、
見る必要がない。
つまり、前回の横ばいになる直前のところを覚えておくことで、
しゃくとり法で更新ができる。


横ばいのところは、別に更新しなくてはならない。
これは、範囲に対してminの更新ができればいいので、
遅延評価segment treeを使ってやればよい。

ソースコード

int w, n, x[50000], dp[50010];
ll s[50010];

inline int cost(int i, int j){
	assert(i + 1 < j);
	ll len = s[j] - s[i];
	if(len + j - i - 1 > w) return inf;
	return (w - len + j - i - 2) / (j - i - 1);
}
const int MX = 65536;
int dat[2 * MX], same[2 * MX];

inline int query(int a, int b, int k, int l, int r){
	if(b <= l || a >= r) return inf;
	if(a <= l && r <= b) return dat[k];
	if(same[k]){
		same[k] = 0;
		same[2 * k + 1] = same[2 * k + 2] = 1;
		dat[2 * k + 1] = min(dat[2 * k + 1], dat[k]);
		dat[2 * k + 2] = min(dat[2 * k + 2], dat[k]);
	}
	return min(query(a, b, k * 2 + 1, l, (l + r) / 2),
		query(a, b, k * 2 + 2, (l + r) / 2, r));
}
inline void fix(int a, int b, int k, int l, int r, int x){
	if(b <= l || a >= r) return;
	if(a <= l && r <= b){
		same[k] = 1;
		dat[k] = min(dat[k], x);
		return;
	}
	if(same[k]){
		same[k] = 0;
		same[2 * k + 1] = same[2 * k + 2] = 1;
		dat[2 * k + 1] = min(dat[2 * k + 1], dat[k]);
		dat[2 * k + 2] = min(dat[2 * k + 2], dat[k]);
	}
	fix(a, b, k * 2 + 1, l, (l + r) / 2, x);
	fix(a, b, k * 2 + 2, (l + r) / 2, r, x);
}
int main(){
	while(cin >> w >> n, w){
		rep(i, n){
			cin >> x[i];
			s[i + 1] = s[i] + x[i];
			dp[i + 1] = inf;
		}
		rep(i, MX * 2) dat[i] = inf, same[i] = 1;
		
		dp[0] = 1;
		int j = 0, ans = inf, co;
		rep(i, n){
			dp[i] = min(dp[i], query(i, i + 1, 0, 0, MX));
			
			if(i >= n - 1 || cost(i, n) < inf){
				ans = min(ans, dp[i]);
				continue;
			}
			while(j <= i + 1) j++;
			
			int lo = j - 1, hi = n + 1, mid;
			while(lo + 1 < hi){
				mid = (lo + hi) / 2;
				if(cost(i, mid) < inf) lo = mid;
				else hi = mid;
			}
			while(j <= n){
				if((co = cost(i, j)) >= inf) break;
				if(co < dp[i]) break;
				dp[j] = min(dp[j], max(dp[i], co));
				j++;
			}
			fix(j, hi, 0, 0, MX, dp[i]);
		}
		cout << ans << endl;
	}
	return 0;
}