SRM505 Div2 Medium - PerfectSequences
問題
与えられた数列の1要素だけ変えて全要素の積と和が同じ値であるようにできるか判定
(1要素は必ず変更しないといけない 何もしないのはダメ)
解法
各要素について条件を満たすような数字が存在するかを二分探索する
解法自体よりコーナーケースとかオーバーフローとかが厄介
実装
数列のサイズが1なら何をしても条件が成り立つからYes
積がlonglongの上限を超えた場合はどうせ条件を満たせないからNo
(真に驚くべき証明を見つけたが、この余白はそれを書くには狭すぎる)
数列に0が含まれるときは、
全ての要素が0のとき) どう変えても和>0かつ積=0になるからNo
非0要素が1個だけのとき) その1個を0に変えれば和=積=0になるからYes
非0要素も0要素も2個以上のとき) どう変えても和>0かつ積=0になるからNo
その他) 唯一の0についてだけ二分探索
二分探索の上限は和も積もオーバーフローしない限界の値にしてる
(l+r)/2と書くとl+rした時点でオーバーフローがあり得るから(l-r)/2+rにする小技も使ってる
最後に求めたlが元の数字と異なるかチェックも必要なことに注意
class PerfectSequences { public: string fixIt(vector<int> a) { ll n = a.size(), s = accumulate(all(a),0ll), p = 1, z = count(all(a),0); if (n==1) return "Yes"; each(i,a) if (i!=0) { if (LONG_LONG_MAX/i<p) return "No"; p *= i; } if (z) { if (n-z==0) return "No"; if (n-z==1) return "Yes"; if (z>=2) return "No"; ll l = 0, r = min(LONG_LONG_MAX/p, LONG_LONG_MAX-s); while (1<r-l) { ll m = (l-r)/2+r; if (s+m>=p*m) l = m; else r = m; } if (s+l==p*l) return "Yes"; return "No"; } each(i,a) { s -= i, p /= i; ll l = 0, r = min(LONG_LONG_MAX/p, LONG_LONG_MAX-s); while (1<r-l) { ll m = (l-r)/2+r; if (s+m>=p*m) l = m; else r = m; } if (s+l==p*l && l!=i) return "Yes"; s += i, p *= i; } return "No"; } };