yukicoder 208

yukicoder初参加してみました.atCoderの方がAGC連続で手も足も出なくて悔しいので参加してみました. Twitterでログインできるのはいいですね.
yukicoder contest 208
初参加の感想としては,AtCoderとあまり変わらないのかなと思いました.AtCoderと違いレベルがA,B,C,Dではなく星の数なのでどれくらいが対応しているのかはわかりませんがおそらくA問題は星一つB問題は星2つになりそう.

---

No.799 赤黒かーどげぇむ

実装に時間がかかりました.最初の考えでは

a < b < c < d  ,   a < c < b < d  ,  a < c < d < b  ,  
c < a < b < d  ,   c < a < d < b  ,  c < d < a < b

の場合分けを考えてしまいました.
書いている途中で別の方法を思いつき方針をガラッと変えました.

• a <= i <= b を満たす i についてそれぞれ幾つの対応可能な c <= j <= d が存在するかを求めて答えに加えていく.

        int ans = 0;
        for (int i = a; i <= b; i++) {
            if (c <= i && i <= d) {
                ans += d - c;
            } else {
                ans += d - c + 1;
            }
        }

この時に i が c以上d以下の場合 j はi以外の数字全てになることに注意します. これで 全ての i について試して ans を出力してACできました!

No.800 四平方定理

この問題はコンテスト中にはACすることができませんでした.テストケースは全部通ったのですがいざ提出してみると TLEしてしまいました.原因としては計算量をO(N³)まで増やしてしまったことです.そりゃTLEしますよね.
この問題は解説のをみて感心しました.

   x^2 + y^2 + z^2

これをまともに計算するとO(N³)となってしまうんですが.

  x^2 +  y^2

までならばO(N²)に落とし込むことができます.つまりz²を移行して右辺に放置すれば良いのです．

   x^2 + y^2 = w^2 + D - z^2

左辺の右辺もそれぞれO(N²)で計算することができTLEしなくなります.それぞれの計算結果を記録しておきます

   left[i] := 左辺の計算結果を i にする回数
   right[i] := 右辺の計算結果を i にする回数

これで記録しておきanswerとしては1 <= i <= n² * 2 の間で,left[i] * right[i] の総和おとれば答えが出ます.

コメント

やっぱりコンテストはでると得られるものがあるので積極的に出ていくべきですね.次回は星2つときたいです。