問題
http://community.topcoder.com/stat?c=problem_statement&pm=8516&rd=11124
それぞれ長さの違うボードが連続して並んでおり、すべてのボードにペンキを塗りたい。
各ボードの長さはあらかじめわかっている。
また、ペンキを塗るペインターが複数おり、各ペインターが長さ１のボードを塗る速さもわかっている。
一人のペインターは複数のボードを塗ることができるが、塗るボードは連続していないといけない。
ボードを塗るペインターの数に制限はなく同時に作業することができるとき、
すべてのボードを塗るのに必要な最小時間を求める。
解き方
時間を固定することでその条件を満たすかどうか決められそうなので、二分探索が使えそう。
ただし時間は10^13刻みで探索が必要になる。
ここで、今回長さの取りうる数はあらかじめわかっているので、
全ての長さの値と全てのペインターで割った数が今回とりうる値になる。
そうすると数はn(ボードの数)*n*m(ペインターの数)で5*10^4ほどに削減できる。
次に長さが決まったとき、ペインターの全ての塗る順番を調べなければいけない。
Ｏ（2^16）なので計算量は間に合いそう。
ペインターの数mの全てのビット列を操作し、各ビットが０のペインターから順に選んでいきビット列のｄｐを更新していけば、全てのペインターの塗る順番を調べることができる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int sum[100],memo[16][60],n,m,cnt;
double times[1<<16];
int dp[1000000];
vector<int> painter;
class PaintingBoards {
public:
int f(int x,int start,double len){
if(memo[x][start]!=-1)return memo[x][start];
int end=start;
while(end<n && painter[x]*len+1e-9>=sum[end+1]-sum[start])end++;
return memo[x][start]=end;
}
bool ispossible(double x){
memset(dp,0,sizeof(dp));
memset(memo,-1,sizeof(memo));
for(int mask=0;mask<(1<<m);mask++){
if(dp[mask]==n)return true;
for(int j=0;j<m;j++){
if((mask&(1<<j))==0){
dp[mask|(1<<j)]=max(dp[mask|(1<<j)],f(j,dp[mask],x));
}
}
}
return false;
}
double minimalTime(vector<int> board, vector<int> painterSpeed) {
n=board.size(),m=painterSpeed.size();
memset(times,0,sizeof(times));
painter=painterSpeed;
sum[0]=0;
FORE(i,1,n+1)sum[i]=sum[i-1]+board[i-1];
cnt=0;
FORE(i,0,n+1){
FORE(j,i+1,n+1){
FORE(k,0,m){
times[cnt++]=(double)(sum[j]-sum[i])/painterSpeed[k];
}
}
}
sort(times,times+cnt);
int low=-1,high=cnt-1;
while(high-low>1){
int mid=(low+high)/2;
if(ispossible(times[mid]))high=mid;
else low=mid;
}
return times[high];
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int sum[100],memo[16][60],n,m,cnt;
double times[1<<16];
int dp[1000000];
vector<int> painter;
class PaintingBoards {
public:
int f(int x,int start,double len){
if(memo[x][start]!=-1)return memo[x][start];
int end=start;
while(end<n && painter[x]*len+1e-9>=sum[end+1]-sum[start])end++;
return memo[x][start]=end;
}
bool ispossible(double x){
memset(dp,0,sizeof(dp));
memset(memo,-1,sizeof(memo));
for(int mask=0;mask<(1<<m);mask++){
if(dp[mask]==n)return true;
for(int j=0;j<m;j++){
if((mask&(1<<j))==0){
dp[mask|(1<<j)]=max(dp[mask|(1<<j)],f(j,dp[mask],x));
}
}
}
return false;
}
double minimalTime(vector<int> board, vector<int> painterSpeed) {
n=board.size(),m=painterSpeed.size();
memset(times,0,sizeof(times));
painter=painterSpeed;
sum[0]=0;
FORE(i,1,n+1)sum[i]=sum[i-1]+board[i-1];
cnt=0;
FORE(i,0,n+1){
FORE(j,i+1,n+1){
FORE(k,0,m){
times[cnt++]=(double)(sum[j]-sum[i])/painterSpeed[k];
}
}
}
sort(times,times+cnt);
int low=-1,high=cnt-1;
while(high-low>1){
int mid=(low+high)/2;
if(ispossible(times[mid]))high=mid;
else low=mid;
}
return times[high];
}
};