#! ruby # yukicoder My Practice # author: Leonardone @ NEETSDKASU ############################################################ def gs() gets.chomp end def gi() gets.to_i end def gss() gs.split end def gis() gss.map(&:to_i) end def nmapf(n,f) n.times.map{ __send__ f } end def ngs(n) nmapf n,:gs end def ngi(n) nmapf n,:gi end def ngss(n) nmapf n,:gss end def ngis(n) nmapf n,:gis end def arr2d(h,w,v=0) h.times.map{[v] * w} end def for2p(hr,wr,&pr) hr.each{|i|wr.each{|j| yield(i,j)}} end def nsum(n) n * (n + 1) / 2 end def vcount(d,r=Hash.new(0)) d.inject(r){|r,e| r[e]+=1;r} end ############################################################ =begin 解説読後 http://yukicoder.me/problems/703/editorial 一連の式からp1とp2を消すと出てくるのか? c1 * c2 - c3**2 != 0 という式から p1とp2が非ゼロであることは求まったが [a] p2 = c1 - p1 [b] p2 * z2 = c2 - p1 * z1 [c] p2 * z2**2 = c3 - p1 * z1**2 [d] p2 * z2**3 = c4 - p1 * z1**4 [b]に[a]を代入 (c1 - p1) * z2 = c2 - p1 * z1 (z1 - z2) * p1 = c2 - c1 * z2 z1 != z2 は保障されてるので [e] p1 = (c2 - c1 * z2) / (z1 - z2) [c]に[a]を代入すると (z1**2 - z2**2) * p1 = c3 - c1 * z2**2 (z1**2 - z2**2)は非ゼロの保障はない、因数分解で(z1 + z2)*(z1 - z2)となり z2=-z1ならゼロになる これに[e]を代入してみる (z1**2 - z2**2) * (c2 - c1 * z2) / (z1 - z2) = c3 - c1 * z2**2 (z1 + z2) * (c2 - c1 * z2) = c3 - c1 * z2**2 これを展開してどうにかなるのか? c2 * z1 - c1 * z1 * z2 + c2 * z2 - c1 * z2**2 = c3 - c1 * z2**2 - c1 * z2**2 が両辺で共通項なので消せるな c2 * z1 - c1 * z1 * z2 = c3 z1でまとめると 0 = (c2 - c1 * z2) * z1 - c3 z2でまとめると 0 = c1 * z1 * z2 - c2 * z1 + c3 z1でまとめたほうを整理して [f] (c2 - c1 * z2) * z1 = c3 両辺を2乗してみると [g] (c2 - c1 + z2)**2 * z1**2 = c3**2 [d]に[a]を代入すると (z1**3 - z2**3) * p1 = c4 - c1 * z2**3 (z1**3 - z2**3)は因数分解で(z1 - z2)*(z1**2 + z1 * z2 + z2**2) となる非ゼロか不明(たぶん非ゼロ?) これに[e]を代入してみる (z1**3 - z2**3) * (c2 - c1 * z2) / (z1 - z2) = c4 - c1 * z2**3 (z1**2 + z1 * z2 + z2**2) * (c2 - c1 * z2) = c4 - c1 * z2**3 c2 * z1**2 - c1 * z1**2 * z2 + c2 * z1 * z2 - c1 * z1 * z2**2 + c2 * z2**2 - c1 * z2**3 = c4 - c1 * z2**3 また共通項の -c1 * z2**3 が出たので消す c2 * z1**2 - c1 * z1**2 * z2 + c2 * z1 * z2 - c1 * z1 * z2**2 + c2 * z2**2 = c4 z1でまとめると 0 = (c2 - c1 * z2) * z1**2 + z2 * (c2 - c1 * z2) * z1 + c2 * z2**2 - c4 z2でまとめると 0 = (c2 - c1 * z1) * z2**2 + (c2 * z1 - c1 * z1**2) * z2 + c2 * z1**2 - c4 z1でまとめたほうをよく見ると[f]と[g]が隠れてる幹事がするので両辺に(c2 - c1 * z2)を掛けたあとで[f][g]を代入してみる 0 = (c2 - c1 * z2)**2 * z1**2 + z2 * (c2 - c1 * z2) * (c2 - c1 * z2) * z1 + (c2 - c1 * z2) * (c2 * z2**2 - c4) 0 = c3**2 + z2 * (c2 - c1 * z2) * c3 + (c2 - c1 * z2) * (c2 * z2**2 - c4) 0 = c3**2 + c2 * c3 * z2 - c1 * c3 * z2**2 + c2**2 * z2**2 - c2 * c4 - c1 * c2 * z2**3 + c1 * c4 * z2 0 = - c1 * c2 * z2**3 + (c2**2 - c1 * c3) * z2**2 + (c2 * c3 + c1 * c4) * z2 + c3**2 - c2 * c4 0 = c1 * c2 * z2**3 + (c1 * c3 - c2**2) * z2**2 - (c1 * c4 + c2 * c3) * z2 + c2 * c4 - c3**2 f(z2) = c1 * c2 * z2**3 + (c1 * c3 - c2**2) * z2**2 - (c1 * c4 + c2 * c3) * z2 + c2 * c4 - c3**2 と置いて微分してみる f'(z2) = 3 * c1 * c2 * z2**2 + 2 * (c1 * c3 - c2**2) * z2 - (c1 * c4 + c2 * c3) 意味ないっぽいので 3次方程式の解の公式じゃなく判別式というのをを使うか A * z2**3 + B * z2**2 + C * z1 + D と置くとすると A = c1 * c2 B = c1 * c3 - c2**2 C = - (c1 * c4 + c2 * c3) D = c2 * c4 - c3**2 判別式 - Wikipedia https://ja.wikipedia.org/wiki/%E5%88%A4%E5%88%A5%E5%BC%8F より B**2 * C**2 - 4 * A * C**3 - 4 * B**3 * D - 27 * A**2 * D**2 + 18 * A * B * C * D 長い… 解説の形に至らなかったから 間違えてる可能性大 =end c1, c2, c3, c4 = gis A = c1 * c2 B = c1 * c3 - c2**2 C = - (c1 * c4 + c2 * c3) D = c2 * c4 - c3**2 H = B**2 * C**2 - 4 * A * C**3 - 4 * B**3 * D - 27 * A**2 * D**2 + 18 * A * B * C * D if H < 0 puts :I else puts :R end