2022年7月9日開催のAtcoder Beginner Contest 259を、備忘的にギリ茶の私の回答と反省を残しつつ、解説を入れていきます！
D問題が勉強になりました。グラフ問題に帰着する点だけはわかったのですが、結局うまくできず、解説見ながら書きました。DFSなどもちゃんと勉強しなきゃなとなった回です。
コンテンツ一覧
A - Growth Record
問題
高橋君は \(\ N \) 歳の誕生日を迎えました。この時の彼の身長は \(\ T \) cmです。
また、以下のことが分かっています。
- 高橋君は\(\ 0 \) 歳の誕生日(生まれた当日)から\(\ X \) 歳の誕生日までの間、毎年身長が\(\ D \) cmずつ伸びた。より厳密に書くと \(\ i = 1,2,3,\ldots,X \) それぞれに対し, \(\ i-1 \) 歳の誕生日から\(\ i \)歳の誕生日までの間に身長が\( D \) cm伸びた。
- 高橋君は\(\ D \) 歳の誕生日から\(\ N \) 歳の誕生日までの間、身長が変化していない。
高橋君の\(\ M \) 歳の誕生日の時の身長が何cmだったかを求めてください。
ちゃんと読めば難しい問題ではないですが、A問題の割には文字が多くてちょっと焦ります。
制約と入力形式
- $$ 0 \leq M < N \leq 100 $$
- $$ 1 \leq X \leq N $$
- $$ 1 \leq T \leq 200 $$
- $$ 1 \leq D \leq 100 $$
- 高橋君の\(\ 0 \) 歳の誕生日の時の身長は\(\ 1 \) cm以上である
- 入力はすべて整数
入力は\(\ N \quad M \quad X \quad T \quad D \) が標準入力で与えられます
回答アプローチ
入力された\(\ M \) の値によって返す数式を分岐させるやり方を取りました。まず、ベースの身長（0歳の時の身長）が以下の式で求まります。
$$ T - D \times X \tag{1} $$
その後、\(\ M \) までの身長を求めていきます。 \(\ ( M < X ) \)
$$ T - D \times X + D \times M \tag{2} $$
N,M,X,T,D = map(int,input().split())
r = T + (M-X)*D if M<X else T
print(r)全ての年齢における身長を愚直に全部リスト化していくやり方もありそうですね。もちろんこのやり方だと計算オーダが大きくなった時に対応はしきれないですが、今回のオーダくらいならこちらのやり方でも問題ないですね。
N,M,X,T,D = map(int,input().split())
L = [T-X*D+i*D if i<X else T for i in range(N+1)]
print(L[M])B - Counterclockwise Rotation
問題
\(\ x \) 軸の正の向きが右, \(\ y \) 軸の正の向きが上であるような\(\ xy \) 座標平面において、点\(\ (a,b) \) を原点を中心として反時計回りに\(\ d \) 度回転させた点を求めてください。
制約と入力形式
- $$ -1000 \leq a,b \leq 1000 $$
- $$ 1 \leq d \leq 360 $$
- 入力はすべて整数
入力は\(\ a \quad b \quad d \) が標準入力で与えられます
回答アプローチ
若干の数学の知識が必要になる問題です。二次元平面上で、\(\ (x,y) \) を原点中心に反時計回りに \(\ \theta \) 回転させた後の\(\ (x',y') \)は以下の式で求められます。
$$ \begin{bmatrix} x' \\ y' \\ \end{bmatrix} = \begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix} \tag{3}$$
上記のように簡単な行列計算が必要になりますが、この程度なら出力ひとつひとつに対して計算を明記しても良いですね。三角関数の計算は、math ライブラリで一通り可能です。また、入力は度数法ですが、関数に入れる際はラジアン法で渡す必要があるので、変換をかます必要があります。
import math
x,y,d = map(int,input().split())
d = math.radians(d) #度数法からラジアン法への変換が必要
D = [[math.cos(d),-math.sin(d)],[math.sin(d),math.cos(d)]]
R = []
for d1,d2 in D:
R.append(d1*x + d2*y)
print(*R)また、pythonの標準では行列計算は上記のように for 文で記述する必要がありますが、numpyを使えば直感的な表記で行列の積が計算できます。
import numpy as np
x,y,d = map(int,input().split())
d = np.radians(d) #度数法からラジアン法への変換が必要
D = np.array([[np.cos(d),-np.sin(d)],[np.sin(d),np.cos(d)]])
print(*D.dot([x,y]))大規模な行列計算が発生する場合は numpyを使った方が有利ですが、この程度の計算だとリストで for 文を回す計算の方が高速です。
C - XX to XXX
問題
英小文字からなる \(\ 2 \) つの文字列 \(\ S,T \) が与えられます。 次の操作を好きな回数（\(\ 0 \) 回でも良い）行うことで、 \(\ S \) を \(\ T \) と一致させることができるかを判定してください。
\(\ S \) において同じ文字が \(\ 2 \) 文字連続しているところの間に、その文字と同じ文字を \(\ 1 \) つ挿入する。 すなわち、下記の \(\ 3 \) つの手順からなる操作を行う。
- 現在の \(\ S \) の長さを \(\ N \) とし \(\ S = S_1,S_2,\ldots, S_N \) とする。
- \(\ 1 \) 以上 \(\ N-1 \) 以下の整数 ii であって, \(\ S_i = S_{i+1} \) を満たすものを\(\ 1 \) つ選択する。（ただし、そのような \(\ i \) が存在しない場合は、何もせずに手順 3.をスキップして操作を終了する。）
- \(\ S \) の \(\ i \) 文字目と \(\ i+1 \) 文字目の間に文字 \(\ S_i (= S_{i+1}) \) を\(\ 1 \) つ挿入する。その結果, \(\ S \) は長さ\(\ N \) の文字列\(\ S_1,S_2,\ldots, S_i , S_i ,S_{i+1},\ldots, S_N \) となる。
こういう問題では操作を再現して、シュミレートする必要があるかどうかを考えてみます。
制約と入力形式
- \(\ S \) と \(\ T \) はそれぞれ英小文字からなる長さ \(\ 2 \) 以上 \(\ 2 \times 10 ^ 5 \) 以下の文字列
条件がざっくりなのはそれはそれで厄介なのです
入力は\(\ S \quad T \) が改行で標準入力で与えられます
回答アプローチ
最初は、\(\ S \) と \(\ T \) の文字が2文字以上連続している所を全て2文字に修正して（aaaaabbbbcde だとしたら aabbcde）\(\ S \) と \(\ T \) が一致すれば良いのではと考えました。
iS = input()
S = [iS[0],iS[1]]
for s in iS[2:]:
if S[-2] == S[-1] == s:
continue
else:
S.append(s)
iT = input()
T = [iT[0],iT[1]]
for t in iT[2:]:
if T[-2] == T[-1] == t:
continue
else:
T.append(t)
if S == T:
print("Yes")
else:
print("No")ただ、これだとWAになります。2問だけWAなどの場合は境界条件を考慮できてない可能性が高いなと考えます。この場合だと入力が2文字の場合などです。
しかし今回の場合は2文字の場合なども考慮できているので、そこではなさそうです。そもそも根本的に \(\ S \) は \(\ T \) より短いと勘違いしてましたが、そのような条件はどこにもありません。今回の場合、 \(\ S \) に文字を追加していくことしかできないので、\(\ T \) の方が短い場合はそもそも一致させることは不可能です。そして、\(\ T \) の方が長いにせよ、 \(\ S \) に文字を追加していくことしかできないので、文字の連続数が \(\ S \) の方が短ければそれも不可能です。（ 例えば\(\ S \) : aaaabbbb, \(\ T \) : aabbbbbbbbb などの場合、aの部分を \(\ T \) と一致させることは不可能です。）この部分が考慮できていませんでした。
なので、文字とその連続数をリストで保存していき、その連続数が \(\ S \) の方が短ければOKというようなプログラムを書きました。
s = input()
t = input()
def text_count(iS):
S = []
count = 1
stock = iS[0]
for s in iS[1:]:
if stock == s:
count += 1
else:
S.append([stock,count]) #文字と続いた回数をセットで
stock,count = s,1 # リセット
S.append([stock,count])
return(S)
S,T = text_count(s),text_count(t)
if len(S) != len(T):#そもそも長さが違えばNG
print("No")
else:
flag = True
for sc,tc in zip(S,T):
if sc[0] == tc[0] and tc[1]>=sc[1]>=2:
continue
elif sc[0] == tc[0] and tc[1] == sc[1] ==1:
continue
else:
flag = False
break
if flag:
print("Yes")
else:
print("No")D - Circumferences
問題
\(\ xy \) -平面上の \(\ N \) 個の円が与えられます。 \( i = 1,2,3, \ldots, N \) について、\(\ i \) 番目の円は点 \(\ x_i , y_i \) を中心とする半径 \(\ r_i \)の円です。
\(\ N \) 個の円のうち少なくとも\(\ 1 \) つ以上の円の円周上にある点のみを通って、点\(\ s_x, s_y \) から点\(\ t_x, t_y \) に行くことができるかどうかを判定してください。
制約と入力形式
- $$ 1 \leq N \leq 3000 $$
- $$ -10^9 \leq x_i,y_i \leq 10^9 $$
- $$ 1 \leq r_i \leq 10^9 $$
- \(\ s_x, s_y \) は\(\ N \) 個の円のうち少なくとも\(\ 1 \) つ以上の円の円周上にある
- \(\ t_x, t_y \) は\(\ N \) 個の円のうち少なくとも\(\ 1 \) つ以上の円の円周上にある
- 入力はすべて整数
回答アプローチ
グラフ問題に帰着させるんだろなぁとは思いつつ、基本解説見ながらになってしまいました。
円ごとに接続を判定して、グラフ問題へと帰着していきます。半径\(\ r_1 \) の円 \(\ C_1 \) と 半径\(\ r_2 \) の円\(\ C_2 \)の場合、それぞれの円の中心間の距離を\(\ d \) とした時、 \(\ r_1 - r_2 \leq d \leq r_1 + r_2 \) が成り立つ時に円が交わるまたは接します。２点間の距離は、\(\ \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2} \) というように求めます。しかし、平方根は誤差が発生しやすいくかつ計算時間もかかるのでなるべく使いたくないので、二乗して計算します。
点\(\ s_x, s_y \) と点\(\ t_x, t_y \) がどこの円の上にあるかは与えられていないので、どこにあるかを探す必要があります。接続判定と同じような処理で、それぞれの円の中心との距離と、円の半径が一致すればその円の上に存在することがわかります。複数の円の上に存在する可能性もありますが、どれか一つの円が分かれば十分です。（以下のプログラムでは複数の円上にある場合、全ての円をリストで保存していますが、使うのは一つだけです。）
また、グラフ問題にしたのち、深さ優先探索（DFS）を行うのですが、Pythonでは再帰回数に上限が設けられているので（AtCoderのPyPy環境では1000回が上限）これを明示的に上限数を増やす必要があります。
ポイント
- 二乗のまま計算して、誤差を減らす。
- Pythonでは再帰回数に上限がある。
import math
import sys
sys.setrecursionlimit(3000**2) #pythonは再帰に上限あり。デフォルトでは1000
N = int(input())
sx,sy,tx,ty = map(int,input().split())
L = []
for _ in range(N):
L.append(list(map(int,input().split())))
G = [[] for _ in range(N)]
kyori2 = lambda a,b,c,d:(c-a)**2 + (d-b)**2 #距離の二乗を返すラムダ関数
S,T = [],[]
used = [0]*N
def dfs(v): #DFS
used[v] = True
if v == T[-1]:
return True
for g in G[v]:
if used[g]:
continue
elif dfs(g):
return True
return False
for i in range(N):
if kyori2(L[i][0],L[i][1],sx,sy) - L[i][2]**2 == 0:
S.append(i)
if kyori2(L[i][0],L[i][1],tx,ty) - L[i][2]**2 == 0:
T.append(i)
for j in range(i+1,N):
if (L[i][2]-L[j][2])**2 <= kyori2(L[i][0],L[i][1],L[j][0],L[j][1]) <= (L[i][2]+L[j][2])**2:
G[i].append(j)
G[j].append(i)
if S and T:
if dfs(S[-1]):
print("Yes")
else:
print("No")
else:
print("No")ちなみに、接続判定をする際、平方根を用いる場合は誤差からか、WAとなるテストケースが発生します。
import math
import sys
sys.setrecursionlimit(3000**2) #pythonは再帰に上限あり。デフォルトでは1000
N = int(input())
sx,sy,tx,ty = map(int,input().split())
L = []
for _ in range(N):
L.append(list(map(int,input().split())))
G = [[] for _ in range(N)]
kyori = lambda a,b,c,d:math.sqrt((c-a)**2 + (d-b)**2) #平方根をとって距離を出力
S,T = [],[]
used = [0]*N
def dfs(v):
used[v] = True
if v == T[-1]:
return True
for g in G[v]:
if used[g]:
continue
elif dfs(g):
return True
return False
for i in range(N):
if kyori(L[i][0],L[i][1],sx,sy) - L[i][2] == 0:
S.append(i)
if kyori(L[i][0],L[i][1],tx,ty) - L[i][2] == 0:
T.append(i)
for j in range(i+1,N):
if (L[i][2]-L[j][2]) <= kyori(L[i][0],L[i][1],L[j][0],L[j][1]) <= (L[i][2]+L[j][2]):
G[i].append(j)
G[j].append(i)
if S and T:
if dfs(S[-1]):
print("Yes")
else:
print("No")
else:
print("No")