Atcoder Beginner Contest 139 の問題F Engines について書きます．
問題概要
平面上のベクトル $v_i = (x_i, y_i)$ ($1 \leq i \leq N$) が与えられる．$A \subseteq \{1,\ldots,N\}$ に対して $w_A = \sum_{i \in A} v_i$ とするとき，$\max \{|w_A| : {A \subseteq \{1,\ldots,N\}}\}$ を求めよ．
制約: $N \leq 100$
考えたこと
コンテストの時には，次のように考えました．$v_i$ を偏角の順に並べておけば，最大値を与える$A$は，ある偏角からある偏角まで，となるだろう．そうすれば，$A$の候補は，$N^2$ くらいしかない．$w_A$ は累積和を使えば前計算$O(N)$で各$A$について$O(1)$で計算できるので，全体で$O(N^2)$なので，楽々間に合う．
ところが，証明ができません．単に区間になるというだけでなく，角度$\pi$以内に入っているベクトルの和だろう，とも思ったのですが，いずれにせよできません．時間が無いので，とりあえず成り立つと信じてコードを書いて提出しました．通ったので，結果オーライではありますけれど．
翌日検索してみた範囲では，納得できる説明が書いてある記事は見つからなかったのですが，だいぶたってから togetter を読んでみたら，beetさんが，証明が載っているページ を紹介していました．以下にその内容 (少し変えていますが) を書きます．
区間になることの証明
すべての$i$について $|v_i| > 0$ として良い．最大値を与える$A$をとる．$w = w_A$ と書く．ベクトル$p$, $q$の内積を$(p, q)$と書くことにする．次を言えば十分である．
- $(v_i, w) > 0 \Rightarrow i \in A$
- $(v_i, w) \leq 0 \Rightarrow i \not\in A$
上は，$(v_i, w) > 0$ かつ $i \not\in A$ とすると，$B = A \cup \{i\}$ としたときに，$|w_B|^2 = |w + v_i|^2 = |w|^2 + 2(w, v_i) + |v_i|^2 > |w|^2$ となって，$A$の最大性に反する．下も同様で，$(v_i, w) \leq 0$ かつ $i \in A$ とすると，$B = A \setminus \{i\}$ としたときに，$|w_B|^2 = |w - v_i|^2 = |w|^2 - 2(w, v_i) + |v_i|^2 > |w|$ となって，$A$の最大性に反する．(終)
反省
証明ができずに，適当な$A$に対して，$w_A$ と $v_i$ のなす角が $\pi/2$ より大きかったとしても，$|w_A + v_i|$の方が $|w_A|$ よりも大きくなることがあるよなあ．うーん．と，うなっていたのでした．$w_{A\cup\{i\}}$ と $v_i$ のなす角を考えなくちゃいけなかったんですね．