結果

問題 No.328 きれいな連立方程式
ユーザー LeonardoneLeonardone
提出日時 2015-12-22 04:39:50
言語 Ruby
(3.3.0)
結果
WA  
実行時間 -
コード長 5,595 bytes
コンパイル時間 46 ms
コンパイル使用メモリ 11,980 KB
実行使用メモリ 16,084 KB
最終ジャッジ日時 2023-10-18 22:31:46
合計ジャッジ時間 3,859 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 82 ms
16,084 KB
testcase_01 AC 83 ms
16,084 KB
testcase_02 AC 83 ms
16,084 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 83 ms
16,084 KB
testcase_06 AC 83 ms
16,084 KB
testcase_07 WA -
testcase_08 AC 84 ms
16,084 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 85 ms
16,084 KB
testcase_12 AC 86 ms
16,084 KB
testcase_13 AC 85 ms
16,084 KB
testcase_14 AC 87 ms
16,084 KB
testcase_15 AC 85 ms
16,084 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 84 ms
16,084 KB
testcase_21 AC 84 ms
16,084 KB
testcase_22 AC 84 ms
16,084 KB
testcase_23 AC 84 ms
16,084 KB
testcase_24 AC 85 ms
16,084 KB
testcase_25 AC 85 ms
16,080 KB
testcase_26 AC 85 ms
16,084 KB
testcase_27 AC 84 ms
16,084 KB
testcase_28 AC 83 ms
16,084 KB
testcase_29 AC 83 ms
16,084 KB
testcase_30 AC 83 ms
16,084 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

#! 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
両辺を２乗してみると
[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
[h] 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
長い…

解説の形に至らなかったから
間違えてる可能性大

うっかり、c1かc2がゼロの場合は3次式にならないので3次判別式が無効だった

c1 = 0 のとき [h] は
0 = c1 * c2 * z2**3 + (c1 * c3 - c2**2) * z2**2 - (c1 * c4 + c2 * c3) * z2 + c2 * c4 - c3**2
= - c2**2 * z2**2 - c2 * c3 * z2 + c2 * c4 - c3**2
= c2**2 * z2**2 + c2 * c3 * z2 + c3**2 - c2 * c4
この場合は2次の判別式を使わなければ b**2 - 4 * a * c だっけか
= P * z2**2 + Q * z2 + R と置くとすると
P = c2**2
Q = c2 * c3
R = c3**2 - c2 * c4
よって判別式は
Q**2 - 4 * P * R

c2 = 0 のとき [h] は
0 = c1 * c2 * z2**3 + (c1 * c3 - c2**2) * z2**2 - (c1 * c4 + c2 * c3) * z2 + c2 * c4 - c3**2
= c1 * c3 * z2**2 - c1 * c4 * z2 - c3**2
同様に
= W * z2**2 + X * z2 + Y とおくとすると
W = c1 * c3
X = - c1 * c4
Y = - c3**2
判別式は
X**2 - 4 * W * Y

ちなみに c1 * c3 - c2**2 != 0 なので c1 と c2 が同時にゼロになることはない


これで正しいかは分からん
結局のところ解説と同じ形になってないしな

=end

c1, c2, c3, c4 = gis

if c1 == 0
    P = c2**2
    Q = c2 * c3
    R = c3**2 - c2 * c4
    H1 = Q**2 - 4 * P * R
    if H1 < 0
        puts :I
    else
        puts :R
    end
    exit
end

if c2 == 0
    W = c1 * c3
    X = - c1 * c4
    Y = - c3**2
    H2 = X**2 - 4 * W * Y
    if H2 < 0
        puts :I
    else
        puts :R
    end
    exit
end




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
0