[AtCoder Daily Training ALL 2024/05/29 16:00start] 参加記録
AtCoder Daily Training ALL 2024/05/29 16:00start に参加しました。
A ~ F の6完でした。
残り10分ありましたが、さすがに D 問題を速解きはまだできないので、断念しました。
A - Edge Checker
もしくは こちら
考え方
注意点として、
これは差が
def solve(a: int, b: int) -> bool:
diff: int = abs(a - b)
return diff in {1, 9}
if __name__ == "__main__":
A: int
B: int
A, B = map(int, input().split())
ans: bool = solve(A, B)
print("Yes" if ans else "No")
感想
やるだけ。
B - T-shirt
もしくは こちら
考え方
その間は、
def solve(a: int, b: int, c: int, x: int) -> float:
if 1 <= x <= a:
return 1.0
if x > b:
return 0.0
return c / (b - a)
if __name__ == "__main__":
A: int
B: int
C: int
X: int
A, B, C, X = map(int, input().split())
ans: float = solve(A, B, C, X)
print(ans)
感想
やるだけ。
C - Cutoff
もしくは こちら
考え方
とりあえず、暫定的なスコアを計算します。
これは、全ラウンドのスコアの合計と、最大スコア・最小スコアを除いたものです。
もし、最小スコアを暫定スコアに加えて目標スコアに届くなら、最小スコアより小さいスコアで済みます。
出力するのが最小値なので、
また、最大スコアを暫定スコアに加えて目標スコアに届かないなら、100点を取ったとしても目標スコアに届きません。
よって、問題文より
あとは、目標スコアに足りない分とればいいだけです。
この足りない分は、最小スコアよりも大きく、最大スコア以下です。
よって単に、このスコアを最後に取れば目標スコアに達することができます。
def solve(n: int, x: int, a: list[int]) -> int:
min_a: int = 101
max_a: int = 0
sum_a: int = 0
for a_i in a:
if a_i < min_a:
min_a = a_i
if a_i > max_a:
max_a = a_i
sum_a += a_i
tmp_score: int = sum_a - min_a - max_a
if tmp_score + min_a >= x:
return 0
if tmp_score + max_a < x:
return -1
return x - tmp_score
if __name__ == "__main__":
N: int
X: int
N, X = map(int, input().split())
A: list[int] = list(map(int, input().split()))
ans: int = solve(N, X, A)
print(ans)
感想
一方、残りのパターンにどんなパターンがあるのか少し悩みました。
ここを正確に早く考えられるようになれば、ここまで10分は切れるはずです。
D - Tournament Result
もしくは こちら
考え方
あとは、問題文通りになっているかを確認します。
def solve(n: int, a: list[str]) -> bool:
for i in range(n):
for j in range(i, n):
if i == j:
if a[i][i] == "-":
continue
if a[i][j] == "W" and a[j][i] == "L":
continue
if a[i][j] == "L" and a[j][i] == "W":
continue
if a[i][j] == "D" and a[j][i] == "D":
continue
return False
return True
if __name__ == "__main__":
N: int = int(input())
A: list[str] = [input() for _ in range(N)]
ans: bool = solve(N, A)
print("correct" if ans else "incorrect")
感想
やるだけ。
E - kasaka
もしくは こちら
考え方
基本的な方針は「後ろから見ていく」です。
後ろから見ていったとき、 "a" が続いているなら先頭に "a" を加えればいいだけです。
そうでなくなった時、残りの部分が回文になっているかを確認します。
今回、 "a" の数と、"a" が連なっているかのフラグを持っておくことで、一回のループで回文判定を終わらせています。
ロジックとしては、"a" のみの文字列ならそのまま回文。
先頭から続いている "a" の数と、後ろから続いている "a" の数を比べて後ろの方が長いことを確認したのち、それ以外の間の部分が回文になっているかを判定した方がわかりやすいかと思います。
def solve(s: str) -> bool:
a_cnt: int = 0
a_flag: bool = True
length: int = len(s)
for i in range(length):
if s[length - 1 - i] == "a" and a_flag:
if s[i - a_cnt] != "a":
a_cnt += 1
continue
a_flag = False
# print(s[length - 1 - i], s[i - a_cnt])
if s[length - 1 - i] != s[i - a_cnt]:
return False
return True
if __name__ == "__main__":
S: str = input()
ans: bool = solve(S)
print("Yes" if ans else "No")
感想
最初、先頭に "a" があるケースを考慮していなかったので、WA が出ました。
過去に解いたことがあるはずですが、その時も同じミスをしていた気がします……
ちゃんとテストケース以外も確認してから出すようにします。
F - Many Replacement
もしくは こちら
考え方
元の文字と、置換後の文字を対応させる辞書を作成します。
一つの置換操作に対して、
最後に、この辞書を用いてそれぞれの文字を置換します。
from string import ascii_lowercase
def solve(n: int, s: str, q: int, cd: list[tuple[str, str]]) -> str:
char_dict: dict[str, str] = {c: c for c in ascii_lowercase}
for c, d in cd:
for k, v in char_dict.items():
if v == c:
char_dict[k] = d
rtn: list[str] = []
for c in s:
rtn.append(char_dict[c])
return "".join(rtn)
if __name__ == "__main__":
N: int = int(input())
S: str = input()
Q: int = int(input())
CD: list[tuple[str, str]] = [tuple(input().split()) for _ in range(Q)]
ans: str = solve(N, S, Q, CD)
print(ans)
感想
最初、文字の位置を集合の辞書で管理しようとしましたが、置換する時の和集合の演算があまりにも計算量が大きくなるので TLE を出しました。
過去の経験から del dict[key] が遅く、 dict[key].clear() なら早いということを思い出し、そこらへんをいじっていましたが、そもそもコレクションの結合は遅いわけで盲点でした。
文字列の結合が遅いことは覚えてたんですけどね……
この問題も解いたことがあるはずなのに引っかかりました。
Discussion