TopCoder, SRM 615, Division 2, Level 2 : LongLongTripDiv2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13091&rd=15848

問題概要

　ノミは、以下の二つのタイプのジャンプを行うことができる。

• 小ジャンプ : 1 [mm] 前進する
• 大ジャンプ : B [mm] 前進する

　ノミは、同じ方向へのジャンプを T 回行なって、丁度 D [mm] だけ移動したい。そのような移動が可能ならば "Possible" 、不可能であれば "Impossible" を return せよ。

解法

　ジャンプ回数の内訳が同じならば最終的な到達位置も同じになるので、いずれかのジャンプの回数を決めれば T 回のジャンプで到達する位置が定まります。片方のジャンプの回数を全て試すことができれば D を作れるパターンが存在するかを全探索できますが、T の値が非常に大きいのでそれは無理です。もっと効率的な方法を考える必要があります。
　ところで、大ジャンプの回数から到達位置への関数を考えると、これは単調増加になっています。従って二分探索を適用可能なので、大ジャンプの回数をキーに二分探索をすることで、目標を達成できる大ジャンプの回数が存在するかを で求めることができます。

コード

using LL = long long;

class LongLongTripDiv2
{
public:
	string isAble( long long D, int T, int B )
	{
		LL lb = 0, ub = T;
		while ( lb + 1 < ub )
		{
			LL mid = ( lb + ub ) / 2;

			( mid * B + ( T - mid ) < D ? lb : ub ) = mid;
		}

		return ub * B + ( T - ub ) == D || T == D ? "Possible" : "Impossible";
	}
};