AOJ 1333 - Beautiful Spacing

AOJ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1333
ICPC Asia Tokyo 2012 Problem I

問題

図1のようにN個の単語を配置する。
1行にはスペースを含めW文字入る。
入力としては、i番目の単語の長さがxiとして与えられる。
以下良い配置の条件

  1. 入力通りの順番で単語を配置する
  2. 単語の間にはスペースを1つ以上入れる
  3. 1つの単語の中に改行やスペースを入れてはいけない
  4. 各行の最初の単語を左端に配置し、（最後の行以外は）最後の単語を右端に配置する

この条件を満たしつつ最善の方法で単語を配置したとき、単語間のスペースの長さの最大をいくらまで小さく出来るか求めよ。

制約

3 ≤ W ≤ 80,000
2 ≤ N ≤ 50,000
1 ≤ xi ≤ (W−1)/2
xiの上限により必ず条件を満たす配置は存在する。

解法

答えをm以下に出来るかを判定することにより二分探索。
判定には二分探索とBITを用いたDPを利用する。
dp配列を、
dp[i+1] = i文字まで使ってちょうど行が埋まった状態にするとき、単語間のスペースの長さをx以下で埋めれられるか（可能ならTrue、不可能ならFalse）
として順番に配列を埋めていく。
更新式は、
dp[i+1] = ∪{a<=j<=b}{dp[j]}
である。
ここで、

  • aは[a,i]の単語を間にスペースを1つ以上入れて1行にうまく配置できるような最小のa
  • bは[b,i]の単語を間にスペースをm個以下入れて1行にうまく配置できるような最大のb

とする。
aとbは二分探索を使えばO(log(N))、更新式はBITを使えばO(log(N))で求まる。
dp[i]がTrueかつ[i,n]を最後の行として配置できるようなiがあれば、答えをm以下に出来ると判定できる。
計算量はO(N*log(N)*log(W))。
DPに尺取法を使うことが出来てO(N*log(W))に出来るっぽい？


追記：案外尺取法のほうが簡単にできた。
↓尺取法つかったやつのソース

bool dp[50010];

int x[50000];
int sum[50001];
int w,n;

bool ok2(int a, int b) { // [a,b]の単語をギリギリで詰めたとき1行に入るかどうか
  int num = b-a+1;
  int space = num-1;
  return sum[b+1]-sum[a] + space <= w;
}

bool ok3(int a, int b, int m) { // [a,b]の単語を間にm個のスペースを入れて詰めたときwを超えるかどうか
  int num = b-a+1;
  int space = (num-1) * m;
  return sum[b+1]-sum[a]+space >= w;
}

bool ok(int m) {
  if (ok2(0,n-1)) return 1;     // 1行に入る
  int a = 0, b = 0;
  int cnt = 0;                  // [a,b)に含まれるiでdp[i]が真であるものの数
  dp[0] = 1;
  REP(i,n) {
    while(a<=i&&!ok2(a,i)) {
      if (dp[a]) cnt--;
      a++;
    }
    while(b<=i&&ok3(b,i,m)) {
      if (dp[b]) cnt++;
      b++;
    }
    if (cnt) {
      dp[i+1] = 1;
      if (ok2(i+1,n-1)) return 1; // i+1番目以降の単語が1行に入る
    } else {
      dp[i+1] = 0;
    }
  }
  return 0;
}


int main() {
  while(scanf("%d%d",&w,&n),w||n) {
    REP(i,n) scanf("%d",x+i);
    REP(i,n) sum[i+1] = sum[i] + x[i];
    int low=0,high=w;
    while(low+1<high) {
      int mid = (low + high) / 2;
      if (ok(mid)) high = mid;
      else low = mid;
    }
    cout << high << endl;
  }
}