TopCoder SRM 790 : Div1 Medium ProposalOptimization

ちょいミスで落としてもったいない。
https://community.topcoder.com/stat?c=problem_statement&pm=16106&rd=18194

問題

R*Cのグリッドが与えられる。
左上と右下を除く各マスには、R,T,Cの3つの値が設定されている。
左上マスから、右または下への隣接マスをたどり、右下マスに到達したい。
その際、移動経路上のCの総和はK以下でなければならない。
この時、経路上の(Rの総和)/(Tの総和)の最大値を求めよ。

解法

解Xを二分探索することを考える。
各マスのスコアをS=R-X*Tとおくと、Sの総和が0以上なら解をX以上とできることになる。

あとは、経由したSの総和とCの総和を計算しながらDPしていくことになる。
ただ、愚直にDPすると状態が増え間に合わない。
そこで半分全列挙で行う。
左上から右下に移動した際に経路毎にSの総和とCの総和を列挙し、同様に右下から左上に移動した場合も列挙して、両者の中間点で合流したとする。
右下から左上に来たケースについて、全経路の(Sの総和,Cの総和)をSが昇順、Cが降順となるようにソートしておけば、左上から右下に来たケース毎に二分探索でSの和が0以上となる最小のCの和を求められる。

int R,C,K;
int cost[303][303];
double S[303][303];
vector <int> roses, tulips;
vector<pair<double,int>> cand[2][303][303];

class ProposalOptimization {
	public:
	int ok2(vector<pair<double,int>>& A,vector<pair<double,int>>& B) {
		sort(ALL(A));
		sort(ALL(B));
		vector<pair<double,int>> C;
		FORR(b,B) {
			while(C.size() && C.back().second>=b.second) C.pop_back();
			if(C.size()&&C.back().first==b.first) continue;
			C.push_back(b);
		}
		FORR(a,A) {
			auto b=lower_bound(ALL(C),make_pair(-a.first,0));
			if(b!=C.end() && a.second+b->second<=K) {
				return 1;
			}
		}
		return 0;
	}
	
	int ok(double v) {
		int y,x;
		FOR(y,R) FOR(x,C) S[y][x]=roses[y*C+x]-v*tulips[y*C+x];
		FOR(y,R) FOR(x,C) cand[0][y][x].clear(),cand[1][y][x].clear();
		cand[0][0][0].push_back({0,0});
		cand[1][R-1][C-1].push_back({0,0});
		int i;
		for(i=0;;i++) {
			int did=0;
			FOR(y,R) {
				x=i-y;
				
				if(x>=0&&x<C) {
					if(cand[1][y][x].size()) {
						did++;
						FORR(c,cand[1][y][x]) c.first-=S[y][x], c.second-=cost[y][x];
						if(ok2(cand[0][y][x],cand[1][y][x])) return 1;
						cand[0][y][x].clear();
						cand[1][y][x].clear();
					}
					else {
						if(did) continue;
						if(y+1<R) {
							FORR(c,cand[0][y][x]) cand[0][y+1][x].push_back({c.first+S[y+1][x],c.second+cost[y+1][x]});
						}
						if(x+1<C) {
							FORR(c,cand[0][y][x]) cand[0][y][x+1].push_back({c.first+S[y][x+1],c.second+cost[y][x+1]});
						}
					}
				}
			}
			if(did) return 0;
			FOR(y,R) {
				x=R+C-2-i-y;
				if(x>=0&&x<C) {
					if(cand[0][y][x].size()) {
						did++;
						FORR(c,cand[1][y][x]) c.first-=S[y][x], c.second-=cost[y][x];
						if(ok2(cand[0][y][x],cand[1][y][x])) return 1;
						cand[0][y][x].clear();
						cand[1][y][x].clear();
					}
					else {
						if(did) continue;
						if(y) {
							FORR(c,cand[1][y][x]) cand[1][y-1][x].push_back({c.first+S[y-1][x],c.second+cost[y-1][x]});
						}
						if(x) {
							FORR(c,cand[1][y][x]) cand[1][y][x-1].push_back({c.first+S[y][x-1],c.second+cost[y][x-1]});
						}
					}
				}
			}
			if(did) return 0;
		}
		return 0;
		
	}
	
	double bestPath(int R, int C, int K, vector <int> roses, vector <int> tulips, vector <int> costs) {
		int x,y;
		::R=R;
		::C=C;
		::K=K;
		::roses=roses;
		::tulips=tulips;
		FOR(y,R) FOR(x,C) cost[y][x]=costs[y*C+x];
		
		double VL=0,VR=1e9;
		if(!ok(VL)) return -1;
		FOR(x,100) {
			if(VR-VL<=1e-10) break;
			double VM=(VL+VR)/2;
			if(ok(VM)) VL=VM;
			else VR=VM;
		}
		return VL;
		
	}
}

まとめ

本番ソートの仕方が甘くて二分探索に失敗。