トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）の解説記事です。
ABC344 A – Spoiler
問題
問題文の要約は以下の通りです。
問題の要約
英小文字と2つの| からなる文字列 \(S\) が与えられます。
2つの|の間にある文字および| を \(S\) から削除した文字列を出力せよ。
制約
・\(S\) は英小文字および | のみからなる長さ 2 以上 100 以下の文字列
・\(S\) は | をちょうど 2 個含む
入力
\(S\)
出力
答えを出力せよ。
解説1
split関数を使用する。
解説
まず入力 を|で分割します。
# 入力
S=input().split('|')答えは|で分割した文字列の０番目と２番目を結合したものなのでS[0]+S[2]を出力します。
# 出力
print(S[0]+S[2])解答
# 入力
S=input().split('|')
# 出力
print(S[0]+S[2])入力 を|でした文字列をa,b,cとしてa+cを出力しても良いです。
# 入力
a,b,c=input().split('|')
# 出力
print(a+c)解説2
正規表現を使ってパイプ(|)で囲まれた部分を削除して出力する。
解説
re.sub()関数は、正規表現パターンにマッチした部分を指定した置換文字列に置換します。今回の場合、パイプ(|)で囲まれた部分を空文字列に置換します。
# 正規表現を使ってパイプ(|)で囲まれた部分を削除して出力
print(re.sub("\|.*\|", "", S))re.sub("\|.*\|", "", S)は以下のような意味を持ちます。
\|: パイプ(|)をエスケープしています。正規表現ではパイプは特別な意味を持つため、その特別な意味を無効化するためにバックスラッシュ(\)でエスケープしています。.*:.は任意の1文字にマッチし、*は直前のパターンが0回以上繰り返されることを示します。つまり、任意の文字が0回以上繰り返されることを意味します。\|: 同様にパイプ(|)をエスケープしています。
したがって、"\|.*\|"は、パイプ(|)で囲まれた部分を表すパターンを意味します。
解答
import re
# 入力
S = input()
# 正規表現を使ってパイプ(|)で囲まれた部分を削除して出力
print(re.sub("\|.*\|", "", S))ABC344 B – Delimiter
問題
解説
入力をリストに格納し、0が入力されたらリストを逆順で出力する。
解説
Aを空のリストとします。0が入力されるまで繰り返し入力を受け取り、リストに格納します。
# Aを空のリストとする
A=[]
while True:
# 入力
S=int(input())
# 入力をリストAに追加
A.append(S)
# 入力が0なら、ループを終了
if S==0:
breakリストAの内容を逆順に出力します。
# リストAの内容を逆順に出力
for i in range(len(A)-1,-1,-1):
print(A[i])解答
# Aを空のリストとする
A=[]
while True:
# 入力
S=int(input())
# 入力をリストAに追加
A.append(S)
# 入力が0なら、ループを終了
if S==0:
break
# リストAの内容を逆順に出力
for i in range(len(A)-1,-1,-1):
print(A[i])ABC344 C – A+B+C
問題
解説
A,B,Cの各要素から1つずつ選んだものの合計をあらかじめ計算して集合に格納し、効率的には判定ができるようにする。
解説
入力を受け取ります。
# 入力
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))
L = int(input())
C = list(map(int, input().split()))
Q = int(input())
X = list(map(int, input().split()))A,B,Cの各要素から1つずつ選んだものの合計をあらかじめ計算して集合に格納します。
# A, B, Cの各要素から1つずつ選んで作られる合計値を格納するための集合
ABC = set()
# A, B, Cの各要素から1つずつ選んで作られる合計値を格納
for i in range(N):
for j in range(M):
for k in range(L):
ABC.add(A[i] + B[j] + C[k])合計値の集合に存在するか確認します。
# 合計値の集合に存在するか確認
for i in range(Q):
if X[i] in ABC:
print('Yes')
else:
print('No')解答
# 入力
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))
L = int(input())
C = list(map(int, input().split()))
Q = int(input())
X = list(map(int, input().split()))
# A, B, Cの各要素から1つずつ選んで作られる合計値を格納するための集合
ABC = set()
# A, B, Cの各要素から1つずつ選んで作られる合計値を格納
for i in range(N):
for j in range(M):
for k in range(L):
ABC.add(A[i] + B[j] + C[k])
# 合計値の集合に存在するか確認
for i in range(Q):
if X[i] in ABC:
print('Yes')
else:
print('No')ABC344 D – String Bags
問題
解説
動的計画法を用いる。
解説
入力を受け取ります。
# 入力
T=input()
N=int(input())
A=[]
S=[]
for i in range(N):
# A[i] と S[i] を入力から受け取る
AS=list(input().split())
A.append(int(AS[0]))
S.append(AS[1:])dp[i]をTの始めからi文字を作るのに必要な最小コストとします。
最初は無限大で初期化を行い、0文字を作るコストは0なのでdp[0] = 0とします。
# dp[i]：T の始めから i 文字を作るのに必要な最小コスト
# 最初は無限大で初期化
dp = [float('inf')] * (len(T) + 1)
# 0文字を作るコストは0
dp[0] = 0dpを順に計算します。i番目の袋の文字列sを考え、sがT の j位置から始まる部分文字列と一致する場合dpを更新します。
# i番目の袋から順番に処理する
for i in range(N):
# dpの配列をコピー
new_dp = dp[:]
# i番目の袋の文字列を処理
for s in S[i]:
for j in range(len(T)):
# s が T の j 位置から始まる部分文字列と一致する場合
if j + len(s) <= len(T) and T[j:j+len(s)] == s:
# dp を更新
new_dp[j+len(s)] = min(new_dp[j+len(s)], dp[j] + 1)
dp = new_dp 最後にdp[-1] が無限大でない場合は答えをそうでなければ-1を出力します。
# 最終的な結果を出力する。dp[-1] が無限大でない場合は、答え。そうでなければ -1 を出力する。
print(dp[-1] if dp[-1] != float('inf') else -1)解答
# 入力
T=input()
N=int(input())
A=[]
S=[]
for i in range(N):
# A[i] と S[i] を入力から受け取る
AS=list(input().split())
A.append(int(AS[0]))
S.append(AS[1:])
# dp[i]：T の始めから i 文字を作るのに必要な最小コスト
# 最初は無限大で初期化
dp = [float('inf')] * (len(T) + 1)
# 0文字を作るコストは0
dp[0] = 0
# i番目の袋から順番に処理する
for i in range(N):
# dpの配列をコピー
new_dp = dp[:]
# i番目の袋の文字列を処理
for s in S[i]:
for j in range(len(T)):
# s が T の j 位置から始まる部分文字列と一致する場合
if j + len(s) <= len(T) and T[j:j+len(s)] == s:
# dp を更新
new_dp[j+len(s)] = min(new_dp[j+len(s)], dp[j] + 1)
dp = new_dp
# 最終的な結果を出力する。dp[-1] が無限大でない場合は、答え。そうでなければ -1 を出力する。
print(dp[-1] if dp[-1] != float('inf') else -1)