SRM 633 Div2 Medium Jumping

問題

SRM 633 - TopCoder Wiki

二次元平面上の(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";
    }
};