https://pastebin.com/ABmvkjJj / https://twitter.com/cielavenir/status/281868241964519424 からコピー(pastebinだとあとで自分が検索できないと思うので…実際私もこのpastebin検索するの時間かかった)。
例として、f(x)=-2x3-7x2+9x-1=0の解の正負。
- f(x)=2x3+7x2-9x+1としても(f(x)=0の解の正負については)一般性を失わない
- f'(x)=6x2+14x-9
- f'(x)=0の判別式をDと置くと、
- D=14*14+4*6*9>0よりf(x)は極大値と極小値を持つ
- x1=(-7-sqrt(103))/6,x2=(-7+sqrt(103))/6
- y1=37.20992,y2=-1.506219
- y1*y2<0よりf(x)はx軸と3点で交わる
- x1<0、0<x2より3点のうち1点は負、もう1点は正
- f(x)はy軸と正の座標で交わるから、(グラフの概形より)もう1点は正となる
- 従ってf(x)=0の解の1つは負、2つは正である
のようなことを適切に場合分けしてコードに落とし込めば良い。
(以下は新規に書いた部分)
場合分けの方法だと、極大値・極小値以外の部分は整数で処理できるが、解を求めてから条件に当てはまるかどうか確認する解法だと解を出力する問題の系とすることが可能である。 極大・極小を取るxの値はわかっているので、そこから2分探索すれば良い。
小数2分探索は https://qiita.com/cielavenir/items/3d2e16ab87d8ddba44b0 の手法を使えばEPSを気にしなくて良い。
tyama_aizu2220.cpp は https://github.com/cielavenir/procon/blob/8f8752552f55a6bac0e660c8963e0d38e2eefb98/topsic/pgbattle2023/3-1.cpp からコードを引用しています(逆に言うと、PG BATTLEの方はunverifiedだがAOJでおそらくverifyされていると言えると思います)