SRM644 div2 500

問題

(0,0)から(x,y)へ移動したい。
ただし、i回目の移動距離はlen[i]でなければならない。
(i回目の移動で整数の座標に移動する必要はない。)
ちょうどn回分の移動距離が与えられるとき、n回ちょうどで(x,y)にたどり着くことができるか？

考え方

移動する座標が整数でなくてもよいため、探索は難しい。
(ロボットアームの逆運動学的なイメージ)
ベクトルv_i(|v_i|=len[i])とベクトルw=(x,y)について、-w+Σv_i=0にできるか？が問題になる。

vが2つと-wがある場合を考える。
3つのうち、どれかベクトル1つを選んで、残りのベクトルの和で選んだベクトルを作れるか考えると、
「選んだベクトルの長さ＞残りのベクトルの長さの和」がある場合、作れないことがわかる。
逆に、すべてが「選んだベクトルの長さ＜＝残りのベクトルの長さの和」なら適当に折り曲げれば作れる。
vが3つ以上でも上記は成り立つので、すべてのベクトルについて、「選んだベクトルの長さ＜＝残りのベクトルの長さの和」が成り立つか確認すればよい。

実は、これは、すべてのベクトルにやる必要はなくて、「最大の長さ＜＝それ以外の長さの和」だけ見ればよい。
あと、多角形をイメージした方がわかりやすかった。