babcs2035 https://blog.hatena.ne.jp/babcs2035/ きろく https://babcs2035.hateblo.jp/ 競技プログラミング yukicoder レベル 2.5 問題 問題 解法 解答 問題 yukicoder.me 解法 ２つ目の条件式の左辺に 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 になってしまう．両辺共に取りうる値の範囲が決まっているので… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbabcs2035.hateblo.jp%2Fentry%2F2019%2F03%2F19%2F062839" title="yukicoder：No.800 四平方定理 - きろく" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/b/babcs2035/20190319/20190319062814.png Hatena Blog https://hatena.blog 2019-03-19 06:28:39 rich https://babcs2035.hateblo.jp/entry/2019/03/19/062839 1.0 100%