Pythonで解くAtCoder(ABC174:B)

こんにちは、クルトンです！
この記事では

AtCoderの「M-SOLUTIONS プロコンオープン 2020」のB問題をPythonを使って解説します。

問題のリンクを載せておきます。

入力の受け取り方や、for文の使い方は下の記事で解説しています。

1行に複数の数字の入力があるときの受け取り方

map(int,input().split())

今回の場合は

N, D = map(int,input().split())

とすることで入力を受け取れます。

また、X, Yについてはfor文と組み合わせて、N回入力を受け取ります

for _ in range(N):
    X, Y = map(int,input().split())

ではここからは解法について説明します。

i個目の点 $(X_i,Y_i)$ の原点からの距離が $D$ 以下であるという条件は

${\sqrt{{X_i^2} + Y_i^2}\leq{D}}$

と表せます。

しかしルートを使って計算すると、浮動小数が生じます。

この浮動小数は誤差を含んでいるため、浮動小数を使うと正しい答えが求まらない場合があり、あまり好ましくありません。

そこで上の式を式変形すると

${X_i^2 + Y_i^2}\leq{D^2}$

と表すことができます。

このように式変形することで整数で計算することができ、すべての場合で正しい答えが求まります。

よって、0を代入した変数ansを用意しておき、上の条件式を満たす $(X_i,Y_i)$ が出てくるたびに1を足していけば、最終的にansが答えとなります。

このansのような回数を数えるための変数を「カウンター」と呼びます。

以下にサンプルコードを載せておきます

今回は

という問題でした。

この問題を通して、「浮動小数は正確な値ではない」ということを覚えておきましょう。

ではまたお会いしましょう！さようなら～

クルトンのプログラミング教室