TopCoder SRM 615 Div2 Medium LongLongTripDiv2

Div1 Mediumが難しめなのでまずは簡単なDiv2 Mediumから。
http://community.topcoder.com/stat?c=problem_statement&pm=13091

問題

小ジャンプで1mm、大ジャンプでBmm進めるとする。
T回のジャンプでちょうどDmm進むことはできるか。

なお、各ジャンプは同じ向きにしか行えない。

解法

T回中x回大ジャンプするとすると、到達距離f(x)=Bx+(T-x)=(B-1)x + Tとなる。
f(x)は単調増加なので、二分探索でf(x)-D=0となる点を探しても良いし、f(x)=Dからx=(D-T)/(B-1)が0～Tの整数となるか求めても良い。

以下のコードは二分探索で求めている。

class LongLongTripDiv2 {
	public:
	string isAble(long long D, int T, int B) {
		ll TT=T,BB=B;
		if(TT*BB<D || TT>D) return "Impossible";
		
		ll L=0,R=TT;
		int i;
		FOR(i,60) {
			ll po=(L+R)/2;
			if(po*B+(TT-po)==D) return "Possible";
			if(po*B+(TT-po)<D) L=po+1;
			else R=po;
		}
		return "Impossible";
	}
};

まとめ

二分探索より方程式解く方が簡単だったな。