人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

yukicoder:No.800 四平方定理

問題

yukicoder.me

解法

2つ目の条件式の左辺に x, y, z の 3 文字,右辺に w の 1 文字となっていて全探索するには O(N^3) かかってしまい間に合わない.そこで,この式を変形して,x^2 + y^2 = -z^2 + w^2 + D とすることで左辺・右辺の取りうる値ごとに (x, y), (z, w) の組がいくつあるかを全通り試すことが出来る.

実装では,配列を用いず std::map や std::set を用いると全体の計算量に O(logN^2) がつくことになり最悪 TLE になってしまう.両辺共に取りうる値の範囲が決まっているので std::vector などで数えればよい.O(N^2 + N^2).

解答

yukicoder.me

f:id:babcs2035:20190319062814p:plain