iwamutsu256 Posted on May 30 AtCoder Beginner Contest 460 参加記録と解答例 (A D問題) # atcoder # python # 競技プログラミング # 多始点bfs 本記事は、AtCoder Beginner Contest 460 (ABC460) に参加した際の、A〜D問題の復習と解答の備忘録です。コンテスト中に考えた解法の方針や、提出したPythonのコードについて整理しています。 A - Mod While Positive 配点 : 100 点 問題文 正整数 $N, M$ が与えられます。 $M$ の値が 0 でない間以下の操作を繰り返すとき、操作を行う回数を求めてください。 $N$ を $M$ で割った余りを $x$ とする。 $M$ の値を $x$ で置き換える。 なお、この操作を有限回行うことにより $M=0$ になることが証明できます。 制約 $1 \le N, M \le 1000$ 入力される値はすべて整数 自分の解答の方針 $M=0$ が保証されているので、 $M=0$ まで操作を繰り返す 提出したコード N , M = map ( int , input (). split ()) count = 0 while M != 0 : M = N % M count += 1 print ( count ) Enter fullscreen mode Exit fullscreen mode B - Two Rings 配点 : 250 点 問題文 $xy$ 平面上に 2 つの円 $C_1, C_2$ があります。ただし、本問題において円とは円周のことを指します。 円 $C_1$ は中心の座標が $(X_1, Y_1)$ で半径が $R_1$ です。 円 $C_2$ は中心の座標が $(X_2, Y_2)$ で半径が $R_2$ です。 円 $C_1$ と円 $C_2$ が共有点を持つかどうかを判定してください。言い換えると、点 $(X_1, Y_1)$ からの距離が $R_1$ であり、かつ点 $(X_2, Y_2)$ からの距離が $R_2$ であるような点が 1 個以上存在するかどうかを判定してください。 $T$ 個のテストケースが与えられるのでそれぞれについて答えを求めてください。 制約 $1 \le T \le 100$ $0 \le X_1, Y_1, X_2, Y_2 \le 10^9$ $1 \le R_1, R_2 \le 10^9$ 入力される値は全て整数 自分の解答の方針 円が共有点を持つかどうかは、円の中心同士の距離とそれぞれの半径から $$|R_1 - R_2| \le \sqrt{(X_1 - X_2)^2 + (Y_1 - Y_2)^2} \le R_1 + R_2$$ とわかる。 $\sqrt{\quad}$ の計算で誤差が出ないように二乗した状態で大小関係を調べることで判定できる。 提出したコード T = int ( input ()) for _ in range ( T ): X1 , Y1 , R1 , X2 , Y2 , R2 = map ( int , input (). split ()) dist = ( X1 - X2 ) ** 2 + ( Y1 - Y2 ) ** 2 if dist <= ( R1 + R2 ) ** 2 and dist >= ( R1 - R2 ) ** 2 : print ( " Yes " ) else : print ( " No " ) Enter fullscreen mode Exit fullscreen mode C - Sushi 配点 : 300 点 問題文 寿司の材料として、 $N$ 個のシャリと $M$ 個のネタがあります。 $i$ 番目のシャリの重さは $A_i$ 、 $j$ 番目のネタの重さは $B_j$ です。 あなたは、シャリとネタを組み合わせることで寿司を作ろうとしています。寿司を 1 つ作るためには、1 つのシャリと 1 つのネタを組み合わせる必要があります。ただし、ネタの重さはシャリの重さの 2 倍以下でなければなりません。また、1 つのシャリやネタを複数の寿司に使うことはできません。 作ることのできる寿司の個数の最大値を求めてください。 制約 $1 \le N, M \le 2 \times 10^5$ $1 \le A_i, B_j \le 10^9$ 入力される値はすべて整数 自分の解答の方針 ネタの重さには制限があるがシャリの重さには制限がないため、ネタを大きい順に取り出して、なるべく大きいシャリから割り当てる
LIVE