本記事は、AtCoder Beginner Contest 452 (ABC452) に参加した際の、A〜D問題の復習と解答の備忘録です。コンテスト中に考えた解法の方針や、提出したPythonのコード、そして後から振り返って気づいた計算量の課題などについて整理しています。
A - Gothec
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点: 100 点
問題文
以下の 5 つの日を五節句と呼びます。
- 1 月 7 日
- 3 月 3 日
- 5 月 5 日
- 7 月 7 日
- 9 月 9 日
M 月 D 日が五節句に含まれるならば Yes を、含まれないならば No を出力してください。
制約
- M, D は整数
- M 月 D 日はグレゴリオ暦における閏年（うるうどし）の日付として正しい。
自分の解答の方針
5つすべてと比較する。
提出したコード
M,D = map(int,input().split())
if (M,D) in [(1,7),(3,3),(5,5),(7,7),(9,9)]:
print("Yes")
else:
print("No")
B - Draw Frame
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点: 200 点
問題文
縦 H 行、横 W 列 のマス目があります。高橋くんは、このマス目のそれぞれのマスを白か黒で塗ろうとしています。
高橋くんは、マス目に含まれるマスのうち端にあるマスをすべて黒く塗り、それ以外のマスを白く塗ります。高橋くんが色を塗ったあとのマス目を出力してください。
より厳密には
H × W のマス目があります。
上から i 行目 (1 ≤ i ≤ H)、左から j 列目 (1 ≤ j ≤ W) のマスをマス (i,j) と呼ぶことにします。
マス (i,j) とマス (k,l) が |i-k|+|j-l|=1 を満たすとき、かつそのときに限りこれらのマスは辺で隣接していると言います。
マス (i,j) と辺で隣接しているマスが 3 個以下のとき、かつそのときに限りマス (i,j) は端にあると言います。
次の条件を満たす H 個の文字列 S_1, S_2, ..., S_H を求めてください。
- S_i は長さ W の文字列であり、S_i の j 文字目は、マス (i,j) が端にあるとき
#、そうでないとき.である。
制約
- 3 ≤ H ≤ 10
- 3 ≤ W ≤ 10
- 入力はすべて整数
自分の解答の方針
H * W の全てが . の2次元配列を作成し、二重ループですべての条件を調べる。
提出したコード
H,W = map(int,input().split())
mapping = [["." for _ in range(W)] for _ in range(H)]
for i in range(H):
for j in range(W):
if i == 0 or i == H-1 or j == 0 or j == W-1:
mapping[i][j] = "#"
for i in range(H):
print("".join(mapping[i]))
C - Fishbones
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点: 300 点
問題文
アーティストの高砂君は、魚の骨をかたどったオブジェを作りました。
オブジェは N 本の肋骨と 1 本の脊椎からなります。肋骨には 1 から N までの番号が付けられています。
高砂君は、以下の条件をすべて満たすように N+1 本の骨に 1 つずつ文字列を書こうと考えています。
- 脊椎に書く文字列の長さは N である。
- 肋骨 i=1,...,N に対して、以下が成り立つ。
- 肋骨 i に書く文字列の長さは A_i である。
- 肋骨 i に書く文字列の B_i 文字目は、脊椎に書く文字列の i 文字目に一致する。
- N+1 本の骨に書く文字列はいずれも、S_1, ..., S_M のいずれかである（重複してもよい）。
- S_1, ..., S_M は英小文字からなる文字列であり、互いに異なります。
j=1,...,M に対して、以下の質問に答えてください。
- 条件を満たす書き方のうち、脊椎に書く文字列が S_j であるものは存在しますか？
制約
- 1 ≤ N ≤ 10
- 1 ≤ B_i ≤ A_i ≤ 10
- 1 ≤ M ≤ 200000
- 1 ≤ |S_j| ≤ 10
- S_1, ..., S_M は相異なる
自分の解答の方針、考えたこと
骨に書く文字列は重複してもいいことから、各骨に最大 M 個の文字の候補がある。
これを集合（set）として持っておくと、文字列 S_j が書けるかどうかを O(N) で判定できる。
前処理を O(NM) で行い、全体で O(MN) で解くことができる。
これは制約下で十分高速。
提出したコード
N = int(input())
A = []
B = []
for i in range(N):
a,b = map(int,input().split())
A.append(a)
B.append(b-1)
M = int(input())
S_list = []
for i in range(M):
s = list(input())
S_list.append(s)
# 長さNのset()の配列に文字を保存
char_list = [set() for _ in range(N)]
# max2000000
for i in range(N):
for j in range(M):
if len(S_list[j]) == A[i]:
char_list[i].add(S_list[j][B[i]])
for i in range(M):
target = S_list[i]
flag = True
if len(target) != N:
print("No")
continue
for j in range(N):
if S_list[i][j] not in char_list[j]:
flag = False
if flag:
print("Yes")
else:
print("No")
D - No-Subsequence Substring
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点: 400 点
問題文
英小文字からなる文字列 S,T が与えられます。
S の空でない部分文字列 s のうち、T を（連続するとは限らない）部分列として含まないものの個数を求めてください。
ここで、S の 2 つの部分文字列は、取り出した箇所が異なれば文字列として等しくても区別するものとします。
部分文字列とは
文字列 X の部分文字列とは、X の先頭から 0 文字以上、末尾から 0 文字以上を削除して得られる文字列のことを指します。
部分列とは
文字列 X の部分列とは、X の要素を 0 個以上選んで削除し、残った要素を元の順序を保って並べた文字列のことを指します。
制約
- 1 ≤ |S| ≤ 2 × 10^5
- 1 ≤ |T| ≤ 50
自分の解答の方針、考えたこと
S の空でない部分文字列 s は全部で |S|(|S|+1)//2 個ある。
S の start 文字目から end 文字目までの部分文字列を S(start,end) としたとき、start を固定したまま end を増やすことを考えると、ある時点で T を含んでいたら、その後はずっと確定で含み続ける。
また、start を一つ増やしたとき、T を含む瞬間が start が一つ少ない時より遅くなることはあるが、早くなることはない。
なので、含まないマスを数えるのには尺取り法が使える。
あとはある時点での部分文字列内に T が含まれるかどうかの判定ができればよい。
提出コードでは len(S) の文字列に T が割り当て可能かを前から順に見ていったが、コンテスト中は残り時間が少なく焦っていてこれがO(|T|)だと思い込んでいた。後から考えるとこれは最悪計算量 O(|S|) なので、全体で O(|S|^2) となり、キラーケースではTLEとなっていた可能性が高い。なので、これでACできたのは運が良かっただけだと思う。
提出したコード
def check(S,T):
i = 0
for t in T:
while i < len(S) and S[i] != t:
i += 1
if i == len(S):
return False
i += 1
return True
S = input()
T = input()
R = [0 for _ in range(len(S))]
for i in range(len(S)):
if i == 0:
R[i] = 0
else:
R[i] = R[i-1]
while R[i] < len(S) and not check(S[i:R[i]+1],T):
R[i] += 1
ans = 0
for i in range(len(S)):
ans += R[i] - i
print(ans)
Top comments (0)