本記事は、AtCoder Beginner Contest 454 (ABC454) に参加した際の、A〜D問題の復習と解答の備忘録です。コンテスト中に考えた解法の方針や、提出したPythonのコードについて整理しています。
A - Closed interval
配点 : 100 点
問題文
整数 L,R が与えられます。
L 以上 R 以下の整数がいくつあるか求めてください。
制約
- 1≤L≤R≤100
- 入力される値は全て整数
自分の解答の方針
そのまま $R-L+1$ で計算します。
提出したコード
L, R = map(int, input().split())
print(R - L + 1)
B - Mapping
配点 : 200 点
問題文
1 から N の番号が付いた N 人の人がいます。
また、1 から M の番号が付いた M 種類の服があります。人 i は服 $F_i$ を着ています。
次の 2 個の質問に Yes か No で答えてください。
- 質問 1: N 人全員が異なる種類の服を着ていますか？
- 質問 2: M 種類の服全てについて、その服を着ている人が少なくとも 1 人ずついますか？
制約
- 1≤N≤100
- 1≤M≤100
- 1≤$F_i$≤M
- 入力される値は全て整数
自分の解答の方針
Fについて、重複を除いた数を数えることで質問1と2のどちらも答えられる。
提出したコード
N, M = map(int, input().split())
F = list(map(int, input().split()))
kind = len(list(set(F)))
if kind == N:
print("Yes")
else:
print("No")
if kind == M:
print("Yes")
else:
print("No")
C - Straw Millionaire
配点 : 300 点
問題文
アイテム 1 からアイテム N までの N 種類のアイテムがあります。はじめ、高橋君はアイテム 1 のみ持っています。
高橋君には M 人の友達がいます。i 人目 (1≤i≤M) の友達にアイテム $A_i$ を渡すと、アイテム $B_i$ をもらうことができます。
高橋君が手に入れることのできるアイテムはアイテム 1 を含めて何種類あるか求めてください。
制約
- 2≤N≤3×$10^5$
- 1≤M≤3×$10^5$
- 1≤$A_i, B_i$≤N
- $A_i \neq B_i$
- 入力される値は全て整数
自分の解答の方針
アイテムの受け渡しが木のように枝分かれしていてたどっていくことができるので、幅優先探索（BFS）をする。
提出したコード
from collections import deque, defaultdict
N, M = map(int, input().split())
exchange = defaultdict(list)
for _ in range(M):
A, B = map(int, input().split())
exchange[A].append(B)
getItemCount = 1
geted = [False for _ in range(N+1)]
geted[1] = True
queue = deque([1])
while queue:
item = queue.popleft()
for can_exchange in exchange[item]:
if not geted[can_exchange]:
queue.append(can_exchange)
geted[can_exchange] = True
getItemCount += 1
print(getItemCount)
D - (xx)
配点 : 425 点
問題文
(, x, ) からなる文字列 A が与えられます。
あなたは A に対して次の 2 種類の操作を自由な順番で自由な回数行うことが出来ます。
- A の部分文字列
(xx)を 1 カ所選び、xxに置換する。 - A の部分文字列
xxを 1 カ所選び、(xx)に置換する。
(, x, ) からなる文字列 B が与えられます。
A を B と一致させることが出来るか判定してください。
T 個のテストケースが与えられるので、それぞれに対して答えを求めてください。
制約
- 1≤T≤3×$10^5$
- A, B は
(,x,)からなる長さ 1 以上 2×$10^6$ 以下の文字列 - 全てのテストケースに対する |A|+|B| の総和は 2×$10^6$ 以下
1回目の解答の方針
AとBの文字列の両方から"(xx)"とその両端についている"()"を取り除いていき、最終的に同じになればよさそう
1回目の提出
T = int(input())
for _ in range(T):
A = list(input())
B = list(input())
stackA = []
flag = False
for i in A:
stackA.append(i)
if not flag and len(stackA) >= 2 and stackA[-2] == stackA[-1] == "x":
flag = True
stackA.pop()
stackA.pop()
elif flag and len(stackA) >= 2 and stackA[-2] == "(" and stackA[-1] == ")":
stackA.pop()
stackA.pop()
elif flag and len(stackA) >= 2 and stackA[-2] == stackA[-1] == "x":
stackA.pop()
stackA.pop()
elif flag:
flag = False
stackB = []
flag = False
for i in B:
stackB.append(i)
if not flag and len(stackB) >= 2 and stackB[-2] == stackB[-1] == "x":
flag = True
stackB.pop()
stackB.pop()
elif flag and len(stackB) >= 2 and stackB[-2] == "(" and stackB[-1] == ")":
stackB.pop()
stackB.pop()
elif flag and len(stackB) >= 2 and stackB[-1] == stackB[-2] == "x":
stackB.pop()
stackB.pop()
elif flag:
flag = False
if stackA == stackB:
print("Yes")
else:
print("No")
結果：WA
2回目の解答の方針
"x"の数が異なることがあるかもしれないので、"x"の数をカウントしてみる
2回目の提出
T = int(input())
for _ in range(T):
A = list(input())
B = list(input())
stackA = []
xCountA = 0
flag = False
for i in A:
stackA.append(i)
if not flag and len(stackA) >= 2 and stackA[-2] == stackA[-1] == "x":
flag = True
stackA.pop()
stackA.pop()
xCountA += 2
elif flag and len(stackA) >= 2 and stackA[-2] == "(" and stackA[-1] == ")":
stackA.pop()
stackA.pop()
elif flag and len(stackA) >= 2 and stackA[-2] == stackA[-1] == "x":
stackA.pop()
stackA.pop()
xCountA += 2
elif flag:
flag = False
stackB = []
flag = False
xCountB = 0
for i in B:
stackB.append(i)
if not flag and len(stackB) >= 2 and stackB[-2] == stackB[-1] == "x":
flag = True
stackB.pop()
stackB.pop()
xCountB += 2
elif flag and len(stackB) >= 2 and stackB[-2] == "(" and stackB[-1] == ")":
stackB.pop()
stackB.pop()
elif flag and len(stackB) >= 2 and stackB[-1] == stackB[-2] == "x":
stackB.pop()
stackB.pop()
xCountB += 2
elif flag:
flag = False
if stackA == stackB and xCountA == xCountB:
print("Yes")
else:
print("No")
結果：WA
3回目の解答の方針
"(x(xx)x)"のようなとき、"(x(xx)x)"->"(xx)"->""とはならないことに気が付いた。 なので、"(xx)"が離れているときは消さないようにし、連続しているときだけその両端の"()"も含めて消すようにしてみた。
3回目の提出
T = int(input())
for _ in range(T):
A = list(input())
B = list(input())
stackA = []
flag = False
count = 0
for i in A:
stackA.append(i)
count += 1
if len(stackA) >= 4 and count >= 4 and stackA[-4:] == ["(","x","x",")"]:
flag = True
stackA.pop()
stackA.pop()
stackA.pop()
stackA.pop()
elif flag and len(stackA) >= 2 and stackA[-2] == "(" and stackA[-1] == ")":
stackA.pop()
stackA.pop()
elif flag:
flag = False
count = 1
last = stackA.pop()
stackA.append("x")
stackA.append("x")
stackA.append(last)
if flag:
stackA.append("x")
stackA.append("x")
stackB = []
flag = False
for i in B:
stackB.append(i)
count += 1
if len(stackB) >= 4 and count >= 4 and stackB[-4:] == ["(","x","x",")"]:
flag = True
stackB.pop()
stackB.pop()
stackB.pop()
stackB.pop()
elif flag and len(stackB) >= 2 and stackB[-2] == "(" and stackB[-1] == ")":
stackB.pop()
stackB.pop()
elif flag:
flag = False
count = 1
last = stackB.pop()
stackB.append("x")
stackB.append("x")
stackB.append(last)
if flag:
stackB.append("x")
stackB.append("x")
# print("".join(stackA),"".join(stackB))
if stackA == stackB:
print("Yes")
else:
print("No")
結果：WA
4回目の解答の方針
そもそも"x"を消す必要がなく、"(xx)"が現れたら"xx"に置き換えていくだけでいいことに気が付いた。
4回目の提出
T = int(input())
for _ in range(T):
A = list(input())
B = list(input())
stackA = []
for i in A:
stackA.append(i)
if len(stackA) >= 4 and stackA[-4:] == ["(","x","x",")"]:
stackA = stackA[:-4] + ["x","x"]
stackB = []
for i in B:
stackB.append(i)
if len(stackB) >= 4 and stackB[-4:] == ["(","x","x",")"]:
stackB = stackB[:-4] + ["x","x"]
# print("".join(stackA),"".join(stackB))
if stackA == stackB:
print("Yes")
else:
print("No")
結果：TLE
5回目の解答の方針
配列の上書き部分が原因で遅くなっていそう。 popとappendは計算量がO(1)なはずなので、それに入れ替える。
5回目の提出
T = int(input())
for _ in range(T):
A = list(input())
B = list(input())
stackA = []
for i in A:
stackA.append(i)
if len(stackA) >= 4 and stackA[-4:] == ["(","x","x",")"]:
stackA.pop()
stackA.pop()
stackA.pop()
stackA.pop()
stackA.append("x")
stackA.append("x")
stackB = []
for i in B:
stackB.append(i)
if len(stackB) >= 4 and stackB[-4:] == ["(","x","x",")"]:
stackB.pop()
stackB.pop()
stackB.pop()
stackB.pop()
stackB.append("x")
stackB.append("x")
# print("".join(stackA),"".join(stackB))
if stackA == stackB:
print("Yes")
else:
print("No")
結果：AC