ABC191参加しました。
atcoder.jp
特に難しくもないでしょう。消える区間をV,Tから計算して、Dと比較すればいいです。
解説 - AtCoder Beginner Contest 191
大抵の言語にはList.RemoveAll()みたいなメソッドが実装されていると思うので、入力を受け取ったら後はそれを呼ぶだけ。
解説 - AtCoder Beginner Contest 191
問題文がちょっと読み解けなかったです。
T字型なら何角形なのか? G(うずまき)型なら?
で、chokudaiさんがtwitterでも述べておりますが、T字は8角形とのこと。
つまり、グリッドの中心だけではなく、その角や辺まで考えないといけないという問題でした。
ここでは、他にも例があったことが書かれています。
この2例があったら、たしかに分かりやすかった。
結局、問題は、図形での頂点の数を数えるということになり、さて頂点とはなにか、を考える必要が出てきます。
これは公式の回答がもうずばりなのですが、あるマスの周囲4マスにある黒マスの数が1,3だったら、頂点となります。
解説 - AtCoder Beginner Contest 191
鬼門。コンテスト後も延々と計算誤差に苦しめられた。
作問側でもいろいろあったんですね。

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

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

なお上の方法は、交点は格子点ではなく小数付きで厳密に出てくるので、丸めも必要です。
何が鬼門かというと、この問題は計算誤差の取り扱いが大変で、公式回答でも言われているように、入力を104倍して整数にしないと計算誤差で苦しめられる恐れがあります。
私はC#で解いていましたからdecimal型を使えてちょっとは楽だったかもしれません
が、それでも円と直線の交点を小数で求めた後、格子点に丸めていくときのceil,floorの整数点への丸めを考えるのが面倒だったり、あとMath.Sqrt()を使ったんですが、Math.Sqrt()はdecimal -> doubleに直さないと使えないので、decimalを使って高精度な計算をしていた意味がdoubleへの変換でなくなってしまったためか、提出後にサンプルが2つだけ通らないという最悪なパターンになりました。(これはめんどくさいやつ...)
余談ですが、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()
{
double input = 2.0;
Console.WriteLine(Math.Sqrt(input));
Console.WriteLine(Sqrt((decimal)input));
Console.WriteLine(Sqrt_double(input));
}
<summary>
</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>
</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));
Console.WriteLine(Math.Floor(-3.14));
Console.WriteLine("Math.Ceiling");
Console.WriteLine(Math.Ceiling(3.14));
Console.WriteLine(Math.Ceiling(-3.14));
Console.WriteLine("Math.Truncate");
Console.WriteLine(Math.Truncate(3.14));
Console.WriteLine(Math.Truncate(-3.14));
Console.WriteLine("FloorTowardsZero");
Console.WriteLine(FloorTowardsZero(3.14));
Console.WriteLine(FloorTowardsZero(-3.14));
Console.WriteLine("CeilingAwayFromZero");
Console.WriteLine(CeilingAwayFromZero(3.14));
Console.WriteLine(CeilingAwayFromZero(-3.14));
}
<summary>
</summary>
public static double FloorTowardsZero(double 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にしては難しかった気がします。
が、まあ、勉強にはなった。