SRM 267 DIV1 Hard HairCuts

問題 Editorial

問題

床屋がある。
この床屋はAM 9:00に開店し、PM 5:00に閉店する。
床屋では常に1人までしかカットすることができない。
誰かのカットの最中に他の人が入ってきた場合、そのカッティングが終わるまで待たされる。キューの動作をする。
客が入ってから閉店した場合でも、最後の客のカットが終わるまでその客は出ない。
ある日、この床屋に入ってきた客の入ってきた時刻のリストenterが与えられる。
また、最後の客が出た時刻lastExitが与えられる。
カットの時間は常に5分間以上である。
このとき、可能な最大のカット時間の最小を求めよ。不可能な場合は-1を返せ。

解答

最大の最小なので二分探索。
判定を考えると、(i番目まででjの時間で可能なら、let カットし始める時間 = max(入ってきた時間[i], j) in (k=[5..最大の時間]に対して、カットし始める時間+k)が可能になる)というboolのDP的なものが立つが、これは常に凸(というのか？範囲として表現できるということ)なので、
([l, u] => [max(l, その客の入ってきた時間) + 5, max(u, その客の入ってきた時間)] + 最大の時間)
という範囲の関数ができる。それを全ての客に対してfoldし、最終的にlastExitがその範囲に含まれているかを判定すればいい

コメント

最初答えは分母が[1..n]の有理数だからDPで…と思ってて、実際累積和の逆とかやったらあと数倍高速化で通りそうになってた。
でもそのあと気づいたので、その名残りで下のコードではその有理数で二分探索している。
でも普通にdoubleでやっていいだろう。
一回二分探索でFailした。これは駄目なので、これから二分探索は常に範囲を左右に1広げるようにする。不正な値は判定側で吸収するようにする。

コード

#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define INF 0x3f3f3f3f
using namespace std;
typedef vector<int> vi;
struct HairCuts {
	int n, last; vi e;
	int parse(string s) {
		s[2] = ' ';
		stringstream ss(s);
		int h, m;
		ss >> h >> m;
		if(h<9) h = 12+h;
		return (h-9)*60+m;
	}
	bool ok(const int den, const int mx) {
		int l = 0, u = 0;
		rep(i, n) {
			l = max(l, den*e[i]) + 5*den;
			u = max(u, den*e[i]) + mx;
			if(u < l) return false;
		}
		return l <= den*last && den*last <= u;
	}
	double maxCut(vector <string> enter, string lastExit) {
		n = enter.size();
		rep(i, n) e.pb(parse(enter[i]));
		sort(all(e));
		last = parse(lastExit);
		bool possible = false;
		double r = INF;
		rer(den, 1, n) {
			int l = den * 5 - 1, u = den * 600 + 1;
			while(l+1 < u) {
				int m = (l+u) / 2;
				if(ok(den, m)) u = m, possible = true;
				else l = m;
			}
			if(possible) {
				r = min(r, u * 1. / den);
			}
		}
		return possible ? r : -1;
	}
};