SRM 390 500pt: PaintingBoards

問題概要

板がN(<50)枚並んでいる。各板の長さが与えられる。塗装屋がP(<=15)人いる。各塗装屋の塗るスピードが与えられる。各塗装屋に連続する区間を割り振って一斉に仕事を始めてもらう。塗るのにかかる最小の時間を求める問題。

考えたこと

15とかビットDP臭。
連続する区間の問題なので、区間DP？
それだと状態数がN^2 * 2^Pで多すぎる。
左から見ていけばいいのか。これだと状態数N*2^Pで何とかなりそうな気がしてきた。
状態遷移は各状態からN*P通り。
全部で計算量はO(N^2 * 2^P * P)？これはちょっと多い。
しばらく考えたけど計算量が落ちないので、定数が小さいことに期待して書き始める。
N=50, P=14まではギリギリ間に合うのにP=15だと落ちる…。
何とか定数倍最適化しようとしたけどギリギリの所で間に合わない…。
どうしようもないし、そもそもSRMでギリギリになるということはそもそも解き方が怪しいので別解法を考える。
これは最大値の最小化だから二分探索を使いたい。
上限を決めたら遷移に二分探索が使える。そしてDPテーブルはbool値を持たせることになる。
そういえば蟻本にはbool値のDPは計算量を落とせる場合が多いとか書いてあった。
状態を(どの塗装屋を使ったか)にして最大どこまで塗れるか？としたら状態数減って嬉しい！
書き始める。lower_bound使ってどこまで塗れるかを高速に求めることができる。
無事通った。他の人の解法見たらTLEしたのと同じような方針でやってる人がいたのにTLEしてたりしてなかったりだった。

practiceで通ったコード

計算量O(N^3 + log X * 2^P * P * log N)。

#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_P = 15;
const int MAX_N = 50;
const int INF = 1<<29;

int dp[1<<MAX_P];
double times[MAX_P][MAX_N][MAX_N];

struct PaintingBoards {

	double minimalTime(vector <int> boardLength, vector <int> painterSpeed) {
		const int N = boardLength.size(), P = painterSpeed.size();

		//前処理
		for(int p=0; p<P; p++){
			for(int st=0; st<N; st++){
				for(int ed=st; ed<N; ed++){
					int len = 0;
					for(int i=st; i<=ed; i++){
						len += boardLength[i];
					}
					times[p][st][ed] = (double) len / painterSpeed[p];
				}
			}
		}

		//答えに関して二分探索
		//解の範囲は[low, high)
		double low = 0.0, high = 1e9;
		for(int loop=0; loop<100; loop++){
			double mid = (low + high) / 2.0;
			if(check(boardLength, painterSpeed, mid)){
				high = mid;
			}
			else{
				low = mid;
			}
		}

		return low;
	}

	bool check(const vector<int>& boards, const vector<int>& paints, double x){
		const int N = boards.size(), P = paints.size();

		//初期化
		memset(dp, 0, sizeof(dp));

		//bitだけのペインタを使ってどこまで塗れるか
		for(int bit=0; bit<(1<<P); bit++){
			int cur = dp[bit];
			for(int p=0; p<P; p++)if( !((bit>>p)&1) ){
				int next_bit = bit | (1<<p);
				int target = lower_bound(times[p][cur], times[p][cur] + N, x) - times[p][cur];
				dp[next_bit] = max(dp[next_bit], target);
			}
		}

		return count(dp, dp+(1<<P), N) > 0;
	}
};

TLEしたけどこっちの方が自然

計算量O(N^2 * 2^P * P)。

#include <vector>
#include <algorithm>
using namespace std;

const int MAX_P = 15;
const int MAX_N = 50;
const double INF = 1e20;

double dp[MAX_N+1][1<<MAX_P];

struct PaintingBoards {

	double minimalTime(vector <int> boardLength, vector <int> painterSpeed) {
		const int N = boardLength.size(), P = painterSpeed.size();

		//DPテーブルの初期化
		for(int i=0; i<=N; i++){
			fill(dp[i], dp[i] + (1<<P), INF);
		}

		//基底
		dp[0][0] = 0;

		//DP
		for(int cur=0; cur<N; cur++){
			for(int bit=0; bit<(1<<P); bit++)if(dp[cur][bit] < INF){
				for(int p=0; p<P; p++)if( !((bit>>p)&1) ){ //誰を使うか
					int next_bit = bit | (1<<p);
					int len = 0;
					for(int to=cur; to<N; to++){ //どこまで使うか
						len += boardLength[to];
						dp[to+1][next_bit] = min(dp[to+1][next_bit], max(dp[cur][bit], (double)len / painterSpeed[p]));
					}
				}
			}
		}

		return *min_element(dp[N], dp[N]+(1<<P));
	}

};

計算量を落とす

二分探索の中で前処理を丁寧にやれば、計算量の中のlog Nが消える。
- よく考えれば、同じ二分探索を何度もやっているから確かに無駄が生じている。
でも二分探索の中で前処理する、という発想は始めてみた。