メモ

yukicoderでゆるふわgolf

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

問題はこちら
No.328 きれいな連立方程式 - yukicoder

a[n]=p*α^n+q*β^n とみればそれはもう三項間漸化式でしょう
(一般項がこの形で与えられることとa[n]=s*a[n-1]+t*a[n-2]という形の線形三項間漸化式を満たすことは同値。証明は高校数学の通り「漸化式⇒一般項」を示し、それを逆に辿れることを確かめれば良い)
ということで問題は「三項間漸化式で得られる数列の最初の4項c[i]が与えられ、一般項をc[n]=p*α^n+q*β^nとするとき、α,βは実数か?」となる。
漸化式をc[i]=s*c[i-1]+t*c[i-2]であるとすると、特性方程式はx^2-sx-t=0でありその解が求めるべきα,βとなるので
α,βが共に実数⇔s^2+4t≧0 となる
漸化式においてi=3,4とすることで
c[3]=s*c[2]+t*c[1]
c[4]=s*c[3]+t*c[2]
というs,tに関する連立方程式が得られ、
\displaystyle{s=\frac{c_2c_3-c_1c_4}{c_2^2-c_1c_3},t=\frac{c_2c_4-c_3^2}{c_2^2-c_1c_3}}
と求まる(仮定より分母は非0)
よってs^2+4t≧0に代入し、分母を払えば(分母は平方の形になっているので0より大きい)
(c_2c_3-c_1c_4)^2+4(c_2c_4-c_3^2)(c_2^2-c_1c_3)\geq 0という条件が得られる
各c[i]は絶対値が5000以下なので4乗するとintに収まらないことに気をつける

int main(){
	long a,b,c,d;
	scanf("%ld%ld%ld%ld",&a,&b,&c,&d);
	puts((b*c-a*d)*(b*c-a*d)+4*(b*d-c*c)*(b*b-c*a)>=0?"R":"I");
	return 0;
}

ぎゅっとして

a,b,c,d;main(i){a=scanf("%d%d%d%d",&a,&b,&c,&d)<puts(1L*(i=a*d-b*c)*i<4L*(c*c-b*d)*(b*b-c*a)?"I":"R");}

103B

実際に自分は初見の時この解法で解いた。writer解説よりは天下りじゃないと思うけど、これを見て三項間漸化式に帰着するっていうのは大学受験数学に毒されてる感じがする。

2016/10/17追記
powを使えpowを

a,b,c,d;main(i){a=scanf("%d%d%d%d",&a,&b,&c,&d)<puts(pow(a*d-b*c,2)<4L*(c*c-b*d)*(b*b-c*a)?"I":"R");}

101B