トップ > AtCoder > AtCoder ABC191

AtCoder ABC191

AtCoder

ABC191参加しました。

atcoder.jp

 

A - Vanishing Pitch

特に難しくもないでしょう。消える区間をV,Tから計算して、Dと比較すればいいです。
解説 - AtCoder Beginner Contest 191

B - Remove It

大抵の言語にはList.RemoveAll()みたいなメソッドが実装されていると思うので、入力を受け取ったら後はそれを呼ぶだけ。

解説 - AtCoder Beginner Contest 191 

C - Digital Graffiti

問題文がちょっと読み解けなかったです。

T字型なら何角形なのか? G(うずまき)型なら?

で、chokudaiさんがtwitterでも述べておりますが、T字は8角形とのこと。

つまり、グリッドの中心だけではなく、その角や辺まで考えないといけないという問題でした。

ここでは、他にも例があったことが書かれています。
この2例があったら、たしかに分かりやすかった。

結局、問題は、図形での頂点の数を数えるということになり、さて頂点とはなにか、を考える必要が出てきます。

これは公式の回答がもうずばりなのですが、あるマスの周囲4マスにある黒マスの数が1,3だったら、頂点となります。

解説 - AtCoder Beginner Contest 191  

D - Circle Lattice Points

鬼門。コンテスト後も延々と計算誤差に苦しめられた。

作問側でもいろいろあったんですね。

f:id:umem0chi:20210211153835p:plain

ナイーブな解き方だと、単純に円に外接する正方形に対してfor文でy方向にぶん回して、正方形内部の格子点が円の内部にあるかを計算する方法があります。
もう少しスマートに考えると、円に外接する正方形に対してfor文でy方向にぶん回して、上のように外接する矩形の矩形の両端から回していって、円の両端を求める方法があります。両端がわかればその点の間の格子点も $ X_r - X_l$ で出せます。 ただ円の半径がお大きい場合にTLEになる可能性があります。

私は円と直線 $ y=d $ の交点を連立方程式で解く方法を選びました。 f:id:umem0chi:20210211154316p:plain

なお公式の回答だと、三平方の定理で解いてますが、どっちでも式が似通って同じ結果になります。

f:id:umem0chi:20210211154319p:plain

なお上の方法は、交点は格子点ではなく小数付きで厳密に出てくるので、丸めも必要です。

何が鬼門かというと、この問題は計算誤差の取り扱いが大変で、公式回答でも言われているように、入力を104倍して整数にしないと計算誤差で苦しめられる恐れがあります。

私はC#で解いていましたからdecimal型を使えてちょっとは楽だったかもしれません が、それでも円と直線の交点を小数で求めた後、格子点に丸めていくときのceil,floorの整数点への丸めを考えるのが面倒だったり、あとMath.Sqrt()を使ったんですが、Math.Sqrt()はdecimal -> doubleに直さないと使えないので、decimalを使って高精度な計算をしていた意味がdoubleへの変換でなくなってしまったためか、提出後にサンプルが２つだけ通らないという最悪なパターンになりました。(これはめんどくさいやつ...)

余談ですが、decimalのMath.Sqrt()に対する以下のような記事が。
Performing Math operations on decimal datatype in C#? - Stack Overflow
まずそもそもSqrt()はdecimalには使えず、使いたいならdoubleにキャストして無理やり使うこともできますが、そもそもそれだとdecimalからdoubleに直したせいで精度が下がるので、decimalを使っていた意味が薄れます。よりよい求め方として、求めた解を更にNewton法で高精度に解を洗練させていくことで、decimal->doubleに直したときの精度低下を補っていくほうがいいですね。

参考までに比較してみました。 Newton法のコードは上のサイトのものを使用。
環境は C#.Net Core 3.1です。

$ \sqrt {2} $ を計算してみます。

    public static void calcSqrt2()
    {
        //例: Sqrt(2)= 1.414213 562373 095048 801688 724209 698078 569671 875376...
        double input = 2.0;

        //1. 通常のSqrt
        Console.WriteLine(Math.Sqrt(input));//1.414213 562373 1 

        //2. 初期値として上の数をdoubleで与えて、Decimalに直してNewton法で高精度化した
        Console.WriteLine(Sqrt((decimal)input));//1.414213 562373 095048 801688 7242

        //2-a. Newton法の部分を全部doubleでやっても、まず変わらない
        Console.WriteLine(Sqrt_double(input));//1.414213 562373 09
    }

    /// <summary>
    /// Sqrtの計算
    /// Newton法で高精度化
    /// </summary>
    /// <param name="x"></param>
    /// <param name="epsilon"></param>
    /// <returns></returns>
    public static decimal Sqrt(decimal x, decimal epsilon = 0.0M)
    {
        if (x < 0) throw new OverflowException("Cannot calculate square root from a negative number");
        decimal cur = (decimal)Math.Sqrt((double)x);//初期値
        decimal prev;
        do
        {
            prev = cur;
            if (prev == 0.0M) return 0;
            cur = (prev + x / prev) / 2
        }
        while (Math.Abs(prev - cur) > epsilon);//更新しても変化が十分なくなるまですすめる
        return cur;
    }
    /// <summary>
    /// 上を全部doubleでしてみる版
    /// </summary>
    /// <param name="x"></param>
    /// <param name="epsilon"></param>
    /// <returns></returns>
    public static double Sqrt_double(double x, double epsilon = 0.0)
    {
        if (x < 0.0) throw new OverflowException("Cannot calculate square root from a negative number");
        var cur = Math.Sqrt(x);//初期値
        var prev = 0.0;
        do
        {
            prev = cur;
            if (prev == 0.0) return 0;
            cur = (prev + x / prev) / 2;
        }
        while (Math.Abs(prev - cur) > epsilon);
        return cur;
    }

Newton法の部分でdecimalを使用することで、結果はより高精度になります。

また、

Mathクラス(C#) - 超初心者向けプログラミング入門

にあるように、負の数に対するMath.Floor(), Math.Ceilingの取り扱いをあまりしたことがなかったので、勉強になりました。C#の場合ですが、ちょっとまとめてみましょう。

    public static void compareRounding()
    {
        //切り捨て(現在の値以下で最大の整数, よって常に数値は小さくなる)
        Console.WriteLine("Math.Floor");
        Console.WriteLine(Math.Floor(3.14));//3
        Console.WriteLine(Math.Floor(-3.14));//-4

        //切り上げ(現在の値以上で最小の整数, よって常に数値は大きくなる)
        Console.WriteLine("Math.Ceiling");
        Console.WriteLine(Math.Ceiling(3.14));//4
        Console.WriteLine(Math.Ceiling(-3.14));//-3

        //小数点以下を捨てる
        Console.WriteLine("Math.Truncate");
        Console.WriteLine(Math.Truncate(3.14));//3
        Console.WriteLine(Math.Truncate(-3.14));//-3

        //切り捨て(0に近づける) => Math.Truncateと同じ
        Console.WriteLine("FloorTowardsZero");
        Console.WriteLine(FloorTowardsZero(3.14));//3
        Console.WriteLine(FloorTowardsZero(-3.14));//-3

        //切り上げ(0から遠ざける)
        Console.WriteLine("CeilingAwayFromZero");
        Console.WriteLine(CeilingAwayFromZero(3.14));//4
        Console.WriteLine(CeilingAwayFromZero(-3.14));//-4
    }

    /// <summary>
    /// 切り捨て(原点に近づくように)
    /// </summary>
    public static double FloorTowardsZero(double a)
    {
        //return a > 0 ? Math.Floor(a) : -Math.Floor(-a);
        return Math.Truncate(a);
    }

    /// <summary>
    ///　切り上げ(原点から離れるように)
    /// </summary>
    public static double CeilingAwayFromZero(double a)
    {
        return a > 0 ? Math.Ceiling(a) : -Math.Ceiling(-a);
    }

ここで自作したのは、今回のコンテストで使ったもの。てっきりMath.Ceiling(), Math.Floor()の負数の挙動は自作した方の挙動になると思ってました...

解説 - AtCoder Beginner Contest 191

動画の解法のほうが計算誤差に悩まされないかもしれない。

まとめ

ABCにしては難しかった気がします。
が、まあ、勉強にはなった。