kmjp's blog

競技プログラミング参加記です

yukicoder : No.328 きれいな連立方程式

yukicoder

手こずったけど辛うじてFA。
http://yukicoder.me/problems/703

問題

定数 c_1, c_2, c_3, c_4が与えられる。
4変数 p_1, p_2, z_1, z_2からなる以下の連立方程式を考える。

  • c_1 = p_1 + p_2
  • c_2 = p_1z_1 + p_2z_2
  • c_3 = p_1{z_1}^2 + p_2{z_1}^2
  • c_4 = p_1{z_1}^3 + p_2{z_2}^3

c_1c_3 - {c_2}^2 \ne 0であるとき、 z_1, z_2はともに実数か、それとも虚数を含むか判定せよ。

解法

最後の式がヒントになっている。
次数が合うようにいくつか式を掛けたりしてみると以下の式ができる。

  • c_1c_3 - {c_2}^2 = p_1p_2(z_1-z_2)^2 = X
  • c_1c_4 - c_2c_3 = p_1p_2(z_1+z_2)(z_1-z_2)^2 = Y
  • c_2c_4 - {c_3^2} = p_1p_2z_1z_2(z_1-z_2)^2 = Z

こうすると、 \displaystyle z_1 + z_2 = \frac{Y}{X}、 \displaystyle z_1z_2 = \frac{Z}{X}であることがわかる。
二次方程式の解と係数の関係を思い出すと、この z_1, z_2は方程式 \displaystyle x^2 - (z_1+z_2)x + z_1z_2 = x^2 - \frac{Y}{X}x + \frac{Z}{X} = 0の書いてあることがわかる。
よって判別式 \displaystyle D = (\frac{Y}{X})^2 - 4*\frac{Z}{X} = \frac{Y^2 - 4XZ}{X^2}が非負なら z_1, z_2は実数、負なら虚数であると判定できる。

ll C[5];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,4) cin>>C[i+1];
	ll X=C[1]*C[3]-C[2]*C[2];
	ll Y=C[1]*C[4]-C[2]*C[3];
	ll Z=C[2]*C[4]-C[3]*C[3];
	
	if(Y*Y-4*X*Z>=0) _P("R\n");
	else _P("I\n");
}

まとめ

コードは非常に単純なのよね。