本記事は、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)
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")
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$
- 入力される値はすべて整数
自分の解答の方針
ネタの重さには制限があるがシャリの重さには制限がないため、ネタを大きい順に取り出して、なるべく大きいシャリから割り当てる。割り当てられないネタがあったら割り当てられるネタまで飛ばす。
割り当てるときにカウントを数えておき、最終的なカウントが最大値になる。
提出したコード
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
A.sort()
B.sort()
count = 0
while A and B:
neta = B.pop()
syari = A.pop()
if neta > syari*2:
while neta > syari*2:
if len(B) == 0:
break
neta = B.pop()
if neta > syari*2:
break
count += 1
print(count)
D - Repeatedly Repainting
配点 : 425 点
問題文
$H$ 行 $W$ 列のマス目があります。このマス目の上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ と呼びます。
すべてのマスは白または黒で塗られています。マス目の情報は $H$ 個の長さ $W$ の文字列 $S_1, S_2, \dots, S_H$ によって与えられ、 $S_i$ の $j$ 文字目が . のときマス $(i,j)$ は白で、 $S_i$ の $j$ 文字目が # のときマス $(i,j)$ は黒で塗られています。
あなたは、以下の操作を $10^{100}$ 回行います。
すべてのマスに対して同時に以下の規則で色の塗り替えを行う。
- 操作前に白く塗られているマスは、そのマスに隣接する黒く塗られているマスが存在するとき、またそのときに限り黒く塗り替える。ただし、マス $(x,y)$ とマス $(x',y')$ が隣接しているとは、片方のマスがもう片方のマスの 8 近傍にある、すなわち $\max(|x-x'|,|y-y'|)=1$ であることを指す。
- 操作前に黒く塗られているマスは、白く塗り替える。
操作を終えた後に各マスが何色で塗られているか求めてください。
制約
- $1 \le H \times W \le 10^6$
- $H, W$ は正整数
- $S_i$ は
.,#からなる長さ $W$ の文字列
自分の解答の方針
1回目の操作以降を考えると、一度黒になったものは周囲のマスに関係なくその後ずっと白と黒を1回ずつ繰り返すことになる。
また、そのようなマスを動作しているマスと呼ぶことにすると、動作しているマスの周囲8マスは次のターンに動作しているマスになる。なので、一回目以降に一つでも動作しているマスがあった場合、十分な時間が経過すればすべてのマスが動作しているマスになる。
よって、 $10^{100}$ ターン後のマスの状態は、すべてのマスが何ターン目に動作しているマスになったかが分かれば求めることができる。
ここで、最初のマスから何ターン目に動作しているマスになるかを考える。初めに白だったマスは、そこから一番近くの黒いマスまでの距離分の時間がかかる。初めに黒だったマスは、白いマスと隣接しているものに限り元から動作している状態になっていて、それ以外のマスは最初の操作で白いマスに変化し、それ以降は別の黒から動作させられるまで停止する。なので、黒いマスの場合は初めの状態を無視してそれ以降に白と同様に一番近くの動作している状態（黒）を見ればよい。
これらは、最初の黒を始点とした多始点BFSをすることで、求められる。
最終的には、初めに黒いマスを0,白を-1として、動作するタイミングのターンの数値で上書きしていき、それらが2で割り切れかつ0ではないものが黒、それ以外が白になる。
提出したコード
from collections import deque
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
T = [[-1 for _ in range(W)] for _ in range(H)]
queue = deque([])
count = 0
for i in range(H):
for j in range(W):
if S[i][j] == "#":
T[i][j] = 0
queue.append((i,j,0))
else:
while count < H*W and queue:
y,x,s = queue.popleft()
for (dx, dy) in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]:
nx, ny = x+dx, y+dy
if 0 <= nx < W and 0 <= ny < H and (T[ny][nx] == -1 or (T[ny][nx] == 0 and s != 0)):
T[ny][nx] = s+1
count += 1
queue.append((ny,nx,s+1))
# print(T)
U = [list(map(lambda x: "#" if (x % 2 == 0 and x != 0)else ".",T[i])) for i in range(H)]
for i in range(H):
print("".join(U[i]))