TopCoder SRM 390 Div1 Medium PaintingBoards

問題

板が一列に並んでいて、それぞれの長さはboardLength[i]である。
何人かがこの板に色を塗る。
それぞれの人が一秒間に塗る板の長さはpainterSpeed[i]である。

それぞれの人は、一枚または連続する何枚かの板を担当することができる。
全ての板の色を塗り終えるまでにかかる最短の時間を求めよ。

制約条件

boardLengthの要素の数≦50
painterSpeedの要素の数≦15
boardLength[i]≦10000
painterSpeed[i]≦10000

方針

二分探索+ビットDP.
かなり珍しいタイプの問題な気がする。

かける時間Tを一つ決めた後にビットDPにより全ての板が塗れるかどうかを判定する。
dp[mask]を、maskであらわされる人を使って塗れる板の最大の枚数とする。
状態遷移は、
「今までに塗られた板の枚数から、次の人が時間T以内で塗れる板の枚数」を考える必要があるが、
これはgreedyに計算できる。

Editorialの解法では、二分探索でTを決めるたびに、
i番の人がj枚目から塗り始めたときに何枚目までいけるかnext[i][j]を毎回前計算している。
なので自分もそれにならった。

ソースコード

int dp[1<<15];
int next[15][51];

class PaintingBoards {
  public:
  double minimalTime(vector <int> boardLength, vector <int> painterSpeed) {
    int n=boardLength.size(), m=painterSpeed.size();
    double lo=0,hi=INF,mid;
    rep(it,100){
      mid=(lo+hi)/2;
      rep(i,m)rep(j,n+1){
        int k=j,len=0;
        while(k<n&&len+boardLength[k]<mid*painterSpeed[i]+EPS)
          len+=boardLength[k++];
        next[i][j]=k;
      }
      rep(i,1<<m)dp[i]=0;
      rep(i,1<<m)rep(j,m)if(!(i&1<<j))
        dp[i^1<<j]=max(dp[i^1<<j],next[j][dp[i]]);
        
      if(dp[(1<<m)-1]==n)hi=mid; else lo=mid;
    }
    return lo;
  }
};