問題
二次元平面上の(0, 0)の位置にいて,jumpLengths[i]の距離だけジャンプする. 与えられた(x, y)に到達できるかを判定する問題.
解答
解説がとても分かりやすいのでまずは,そちらを見たほうが良い. 感覚的に正解となる条件は理解できたが,その正しさはうまく説明できなかった. 解説のように問題を考えていけばよいのかと納得.
- jumpLengthsの要素数が1の時の判定は自明.
- 要素数2以上はややこしい(ように見える).
- まずjumpLengthの総和の距離以内であることが必要条件.
- この円周にどうやって到達する方法は,要素数の大きい方から順に外側にジャンプしていけばよい. もちろん,順番は関係ないが次の説明と合わせる.
- 逆に円の中心側の限界がどこなのか考えると,まず要素数の大きい円から出発し(必ずジャンプしなくてはいけないので), その後どんどん内側にジャンプをしていく.
- もし,そのようなジャンプで中心に到達(超える)事ができれば,任意の地点に到達可能. そうでなければ,その地点が内側の境界.その時の(0, 0)からの距離は最大要素 - それ以外の要素の総和.
- (x, y)がその中でどこに位置するのかを判定することで問題を解く.
class Jumping { public: string ableToGet(int x, int y, vector <int> jumpLengths) { double d = sqrt(1.0 * x*x + 1.0 * y * y); int n = jumpLengths.size(); if (n == 1) { if (d == jumpLengths[0]) return "Able"; else return "Not able"; } sort(jumpLengths.begin(), jumpLengths.end()); if (abs(d - jumpLengths[n-1]) <= accumulate(jumpLengths.begin(), jumpLengths.begin() + n-1, 0)) return "Able"; return "Not able"; } };