mayoko’s diary

プロコンとかいろいろ。

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

yukicoder

あんまり競プロっぽくないけどお祭りみたいなもんだし良いかなと思っていましたが, ちょっとアレな方法で通されてしまったのでマズかったかな…

問題

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

解法

基本的にはここに書いたとおりです。
http://yukicoder.me/problems/703/editorial

ちなみに, ここで書いた方法を使うことで, 2n 個の未知数があった時も z に関する n 次方程式を立てることが出来ます。3 次以上では解の公式が無かったり面倒だったりするので問題にはしませんでしたが。

思いつくポイントとしては, c_i の形が, 3 項間漸化式の解の形をしていることに気づくことでしょうか。3 項間漸化式の形をしているので,
c_n = A c_{n-1} + B c_{n-2}
という形で書けるはずです。雰囲気的に A, B がどうなるかを察することができれば想定解が思いついたかもしれません。

予想外だった解法は WolframAlpha を使う方法です。
http://www.wolframalpha.com/input/?i=solve[+c1%3Dp1%2Bp2%2C++c2%3Dp1*z1%2Bp2*z2%2C++c3%3Dp1*z1^2%2Bp2z2^2%2C++c4%3Dp1*z1^3%2Bp2*z2^3]

これはクソゲーになってしまったかも…解けないとかなりイライラするタイプの問題な気がするので悩んでた人には申し訳ないです。

writer 解↓

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll c1, c2, c3, c4;
    cin >> c1 >> c2 >> c3 >> c4;
    assert(-5000 <= c1 && c1 <= 5000);
    assert(-5000 <= c2 && c2 <= 5000);
    assert(-5000 <= c3 && c3 <= 5000);
    assert(-5000 <= c4 && c4 <= 5000);
    assert(c1*c3-c2*c2 != 0);
    ll a = c1*c4-c2*c3;
    ll b = (c3*c1-c2*c2) * (c3*c3-c2*c4);
    assert(a*a+4*b != 0);
    if (a*a+4*b > 0) cout << "R" << endl;
    else cout << "I" << endl;
    return 0;
}