結果

問題 No.328 きれいな連立方程式
ユーザー LeonardoneLeonardone
提出日時 2015-12-22 06:42:43
言語 Ruby
(3.3.0)
結果
AC  
実行時間 95 ms / 2,000 ms
コード長 3,185 bytes
コンパイル時間 178 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 12,288 KB
最終ジャッジ日時 2024-09-18 18:32:21
合計ジャッジ時間 4,303 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#! ruby
# yukicoder My Practice
# author: Leonardone @ NEETSDKASU
############################################################
def gs() gets.chomp end
def gi() gets.to_i end
def gf() gets.to_f end
def gss() gs.split end
def gis() gss.map(&:to_i) end
def gfs() gss.map(&:to_f) 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

紙に手書き計算で解説の式が出てきた (提出した手書きじゃない計算はやっぱり間違ってたわけだ・・・)

[a] c1 = p1 + p2
[b] c2 = (p1 * z1) + (p2 * z2)
[c] c3 = (p1 * z1**2) + (p2 * z2**2)
[d] c4 = (p1 * z1**3) + (p2 * z2**3)

[a]を変形
[e] p2 = c1 - p1

[b]を変形
p2 * z2 = c2 - (p1 * z1)
[e]を代入
(c1 - p1) * z2 = c2 - (p1 * z1)
整理して
[f] (z1 - z2) * p1 = c2 - c1 * z2

[c]と[d]も[b]同様にして
[g] (z1**2 - z2**2) * p1 = c3 - c1 * z2**2
[h] (z1**3 - z2**3) * p1 = c4 - c1 * z2**3

[g]と[h]の左のやつを因数分解して
(z1 - z2) * (z1 + z2) * p1 = c3 - c1 * z2**2
(z1 - z2) * (z1**2 + z1 * z2 + z2**2) * p1 = c4 - c1 * z2**3
それぞれに[f]を代入
[i] (c2 - c1 * z2) * (z1 + z2) = c3 - c1 * z2**2
[j] (c2 - c1 * z2) * (z1**2 + z1 * z2 + z2**2) = c4 - c1 * z2**2

[i]を変形すると
[k] c2 * (z1 + z2) - c1 * z1 * z2 = c3

[j]を変形すると
c2 * (z1**2 + z1 * z2 + z2**2) - c1 * z1 * z2 * (z1 + z2) = c4
c2 * ((z1 + z2)**2 - z1 * z2) - c1 * z1 * z2 * (z1 + z2) = c4
(c2 * (z1 + z2) - c1 * z1 * z2) * (z1 + z2) - c2 * z1 * z2 = c4
ここで[k]が出てくるので代入
[l] c3 * (z1 + z2) - c2 * z1 * z2 = c4

X = z1 + z2
Y = z1 * z2
で[k][l]を置と
[m] c2 * X - c1 * Y = c3
[n] c3 * X - c2 * Y = c4
となるわけだ
連立するとXは
     c2**2 * X - c1 * c2 * Y = c2 * c3
-) c1 * c3 * X - c1 * c2 * Y = c1 * c4
---------------------------------------
(c2**2 - c1 * c3) * X = c2 * c3 - c1 * c4

c2**2 - c1 * c3 != 0 なので
X = (c2 * c3 - c1 * c4) / (c2**2 - c1 * c3)

連立してYは
   c2 * c3 * X - c1 * c3 * Y = c3**2
-) c2 * c3 * X   - c2**2 * Y = c2 * c4
---------------------------------------
(c2**2 - c1 * c3) * Y = c3**2 - c2 * c4
c2**2 - c1 * c3 != 0 なので
Y = (c3**2 - c2 * c4) / (c2**2 - c1 * c3)

X = z1 + z2
Y = z1 * z2
なので
z2 = X - z1
ゆえに
Y = z1 * (X - z1)
0 = z1**2 - X * z1 + Y
となる
これが複素解になるのは判別式 D = b^2-4ac < 0
つまり
D = (-X)**2 - 4 * Y < 0

分数計算は避けたいので

T = c2**2 - c1 * c3
とおき
X = U / T
Y = V / T
D = (U**2 - 4 * V * T) / T**2 < 0
とできる T**2は正なので割る必要なく
D = U**2 - 4 * Y * T
を求めればよい

U = c2 * c3 - c1 * c4
V = c3**2 - c2 * c4


=end


c1, c2, c3, c4 = gis

T = c2**2 - c1 * c3
U = c2 * c3 - c1 * c4
V = c3**2 - c2 * c4
D = U**2 - 4 * V * T

if D < 0
    puts :I
else
    puts :R
end
0