・0 pv・10 min read
AtCoder Beginner Contest 259 の A 〜 E を解く
はじめに
この記事は 2022-07-09(土) に行われた AtCoder Beginner Contest 259 の解説記事です。
私は ABCDE 5 完でした。
コンテスト中に考えたことの整理を兼ねて忘備録として書いておこうと思います。
この記事が一緒に AtCoder を楽しんでいる人の役に立てたら嬉しいです。
私は ABCDE 5 完でした。
コンテスト中に考えたことの整理を兼ねて忘備録として書いておこうと思います。
この記事が一緒に AtCoder を楽しんでいる人の役に立てたら嬉しいです。
説明不足・間違いがありましたらコメントをください。
A - Growth Record
日本語読解が難しめですね。
変数も 5 個あって、どの変数がどういった意味を持つ値なのかがわかりにくかった様に思えます。
私は脳内メモリが不足してるタイプなので厳しかったです。
変数も 5 個あって、どの変数がどういった意味を持つ値なのかがわかりにくかった様に思えます。
私は脳内メモリが不足してるタイプなので厳しかったです。
考察
- 図にすると以下のようになります。
- M が X より大きいか小さいかによって式を変えれば良さそうです。
実装
def resolve():
N, M, X, T, D = map(int, input().split(" "))
print(T - (X-M)*D if M <= X else T)
resolve()より簡潔に書くこともできます。
def resolve():
N, M, X, T, D = map(int, input().split(" "))
print(T - max(0, X-M)*D)
resolve()B - Counterclockwise Rotation
点を原点まわりに回転させる問題ですね。
考察
本番中に「回転行列」で Google 検索して出てきた以下の数式をコードに落としました。 （考察ではないですね・・・）
2022年7月21日追記：この章の末尾に回転行列の考え方について書きました。気になる人はそちらも参考にしてください。
実装
def resolve():
from math import sin, cos, radians
x, y, d = map(int, input().split(" "))
# 入力は「度」で与えられるのでラジアンに変換する。
d = radians(d)
X = cos(d)*x - sin(d)*y
Y = sin(d)*x + cos(d)*y
print(X, Y)
resolve()オイラーの公式を使った解法について
@dnim_prog さんにオイラーの公式というものを教えてもらった ので実装してみる。
XY平面上の座標をオイラーの公式 () により、複素平面上の座標として扱う。
今回求めたいのは d ° 回転した後の座標なので、
の様に計算する。
def resolve():
from math import sin, cos, radians
x, y, d = map(int, input().split(" "))
# 入力は「度」で与えられるのでラジアンに変換する。
d = radians(d)
p = complex(x, y)
q = complex(cos(d), sin(d))*p
print(q.real, q.imag)
resolve()回転行列について
C - XX to XXX
考察
- 2 個以上連続した文字があればそれを好きな個数連続した文字に変更することができる。
- 1 個の場合、増やすことはできない。
- T の連続する文字の個数を数えて、S 側の該当する箇所を探し出して文字を増やす、みたいなことをやると実装が大変だし多分 TLE する。
aaabbc => [(a, 3), (b, 2), (c, 1)]みたいな変形をすれば楽に実装できるのでは？- ランレングス圧縮というらしい（コンテスト終了後に知った。）
実装
def resolve():
S = list(input())
T = list(input())
# ランレングス圧縮する。aaabbc => [(a, 3), (b, 2), (c, 1)]
def run_length_compless(S):
agg_S = [[S[0], 1]]
for s in S[1:]:
if agg_S[-1][0] == s: agg_S[-1][1] += 1
else: agg_S.append([s, 1])
return agg_S
agg_S = run_length_compless(S)
agg_T = run_length_compless(T)
# 要素の長さが違う場合、S => T の変換はできない。
if len(agg_S) != len(agg_T):
print("No")
return
N = len(agg_S)
# 要素毎に比較して、agg_S[i] => agg_T[i] にできるかどうかを判定する。
for i in range(N):
s, count_s = agg_S[i]
t, count_t = agg_T[i]
# 要素の種類が違う場合、複合できない。
if s != t:
print("No")
return
# S 側の i 番目の要素の長さが 1 の時、それ以上 S 側を伸ばすことができないので、
# T 側の i 番目の要素の長さが 1 で無い限り複合ができない。
if count_s == 1 and count_t != 1:
print("No")
return
# S 側を縮めることはできないので、T 側より S 側が長い時は複合できない。
if count_s > count_t:
print("No")
return
# すべての要素で複合できないケースが存在しない場合、複合できる判定
print("Yes")
resolve()D - Circumferences
考察
- N が最大で 3*(10**3) 程度なので、O(N**2) くらいなら通せそう。
- それぞれの円を頂点として扱って、円と円が触れている => 頂点間に辺が張ってあると見做せばグラフ問題扱いできそう。
- グラフ問題だとすれば始点から終点に辿り着けるかどうかの簡単な問題になる。
- 円と円が触れている判定が厄介。特に円の内側に円が潜り込んでいるパターンの判定をどうする？
- 以下の図の様になるので
(r_i-r_j)**2 > diffで判定できる。
- 以下の図の様になるので
実装
def resolve():
from collections import deque
N = int(input())
s_x, s_y, t_x, t_y = map(int, input().split(" "))
CIRCRES = [[int(x) for x in input().split(" ")] for _ in range(N)]
# EDGES[i]: 円 i が接している円（円 i から円周上を移動することで移動できる円）
EDGES = [[] for _ in range(N)]
for i in range(N-1):
x_i, y_i, r_i = CIRCRES[i]
for j in range(i+1, N):
x_j, y_j, r_j = CIRCRES[j]
# diff: 円iの中心と円jの中心の距離。
# 本来は √ をとる必要があるが、誤差が怖いので √ をとらずに扱う。
diff = pow(x_i-x_j, 2) + pow(y_i-y_j, 2)
# 片方の円の内側にもう片方円が潜り込むパターン
if pow(r_j - r_i, 2) > diff: continue
# 片方の円の内側にもう片方の円が潜り込むパターンを除外した上で、接触判定を行う。
if pow(r_i + r_j, 2) >= diff:
EDGES[i].append(j)
EDGES[j].append(i)
# starts: 始点が触れている円
starts = set()
# goals: 終点が触れている円
goals = set()
for i in range(N):
x_i, y_i, r_i = CIRCRES[i]
diff = pow(x_i-s_x, 2) + pow(y_i-s_y, 2)
if diff == pow(r_i, 2):
starts.add(i)
diff = pow(x_i-t_x, 2) + pow(y_i-t_y, 2)
if diff == pow(r_i, 2):
goals.add(i)
# 始点が触れている円から BFS をやっていって、終点が触れている円にたどり着けたら "Yes"
deq = deque(starts)
checked = [i in starts for i in range(N)]
while deq:
current = deq.popleft()
if current in goals:
print("Yes")
return
for n in EDGES[current]:
if checked[n]: continue
checked[n] = True
if n in goals:
print("Yes")
return
deq.append(n)
print("No")
resolve()E - LCM on Whiteboard
考察
- 最小公倍数の「あり得る値の個数」を求めれば良くて、実際に最小公倍数を求める必要はない。
- 最小公倍数について考える。
- [4, 3] の最小公倍数は 12
- =>
(2^2)*(3^0)と(2^0)*(3^1)の最小公倍数は(2^2)*(3^1) - => ai に含まれる素因数 p の個数を
e[p][i]とすると、全ての p に対してp^max(e[p])を掛け合わせたものが最小公倍数。
- ai を 1 に書き換えた時に最小公倍数の種類が増える条件は？
- ai を 1 に書き換えた結果、上記の
max(e[p])が変わってしまう時 - => ai が
e[p][i] == max(e[p])となるp^e[p][i]、かつ、e[p][i] == e[p][j]となる j が存在しないこと。
- ai を 1 に書き換えた結果、上記の
- ai を 1 に書き換えた時に最小公倍数が X 以外になるパターンを数えて、最後に最小公倍数として X が出現したかどうか判定すれば良い。
実装
def resolve():
from collections import defaultdict
N = int(input())
A = [[] for _ in range(N)]
# max_e[p]: 全ての要素に含まれる p の個数の最大値
max_e = defaultdict(int)
for i in range(N):
M = int(input())
for _ in range(M):
p, e = [int(x) for x in input().split(" ")]
A[i].append((p, e))
max_e[p] = max(max_e[p], e)
# max_counts[p]: 全ての要素の p の個数を見て、p の個数が最大値と一致している要素の個数。
# p の個数が最大値と一致している要素が複数あった場合、その要素を 1 にしても max(e[p]) が変化しないのでその判定に使う。
max_counts = defaultdict(int)
# duplicated_max: 最大値が重複している p の集合
duplicated_max = set()
for i in range(N):
for p, m in A[i]:
if max_e[p] == m:
max_counts[p] += 1
if max_counts[p] >= 2:
duplicated_max.add(p)
# X = lcm(a_1,...a_N) とする。
# a_i を 1 に書き換えた時に最小公倍数が X にならない個数を数える。
ans = 0
for i in range(N):
if any(max_e[p] == m and p not in duplicated_max for p, m in A[i]):
ans += 1
# ans < N の時、どこかで一回は X が出てきたと考えられるので 1 個追加する。
if ans < N: ans += 1
print(ans)
resolve()