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";
    }
};