ABC344 A-D問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが週末に開催している、競技プログラミングコンテストのことです。

A-D問題について、自身の復習も兼ねて説明できればと思います。誤った記述やより良い解法などあれば、コメントをいただけると幸いです。

ABC344

A – Spoiler

問題

A問題

英小文字と | 2個からなる文字列が与えられます。2つの | の間にある文字および | を文字列から削除した文字列を出力する問題です。

思考の筋道

split関数を区切り文字「|」で使いましょう。

コード

S = input()

l = S.split('|')
print(l[0] + l[2])

B – Delimiter

問題

B問題

N個の整数が与えられます。これを逆順で表示する問題です。Nが入力として与えられない代わりに、N個目の整数のみが0であることが保証されています。

思考の筋道

while文を使いましょう。0が来たらbreakです。

コード

l = []

while True:
    A = int(input())
    l.append(A)
    if A == 0:
        break

n = len(l)
for i in range(n):
    print(l[n - 1 - i])

C – A+B+C

問題

C問題

3個の整数列 A, B, C と整数列 X が与えられます。Xの各整数について、A, B, C から 1 つずつ整数を選んで和をとることで、同じ値にできるかを調べる問題です。

思考の筋道

A, B, C の要素数は100で、Xの要素数は2×10^5です。そのため、A, B, C, X に関する4重の全探索や、A, B, Xに関する3重の全探索ではTLEです。

はじめからXについて考えるのではなく、まずはA, B, Cだけを見ましょう。事前に3つの整数の和をすべて求め、集合に保管することを考えます。A, B, Cの3重の全探索は計算量10^6なので間に合います。

その後に、Xの各整数が集合に保管されているかを調べればよいでしょう。

コード

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()))

S = set()

for num_A in A:
    for num_B in B:
        for num_C in C:
            S.add(num_A + num_B + num_C)

for num_X in X:
    if num_X in S:
        print("Yes")
    else:
        print("No")

D – String Bags

問題

D問題

文字列がいくつか入った袋1, 2, ……, Nと、文字列Tが与えられます。袋1から順に、袋から文字列を取り出して連結させることで、文字列Tと同じ文字列にすることを目指します。

袋から文字列を取り出さないことも可能です。取り出す袋の数を最小でいくつにできるかを調べる問題です。そもそもどのように取り出しても、Tと同じ文字列にできない場合は-1と表示します。

思考の筋道

樹形図を書きたくなるような遷移性のある問題であり、最大値・最小値・個数を求める問題にも該当します。DP（動的計画法）の気配を感じたいところです。

何袋目まで調べたかを i 、何文字目まで出来上がったかを j とし、dp[i][j]を取り出した袋の最小値としましょう。

漸化式を立てる際、袋を使うか使わないかで式が変わりますので、場合分けします。

コード

T = input()
N = int(input())

INF = 10 ** 9
dp = [[INF for _ in range(len(T) + 1)] for _ in range(N + 1)]
dp[0][0] = 0

for i in range(N):
    S = list(input().split())[1:]
    for j in range(len(T) + 1):
        # 袋i+1を利用しない場合
        if dp[i][j] < dp[i + 1][j]:
            dp[i + 1][j] = dp[i][j]
        # 袋i+1を利用する場合
        for s in S:
            if s == T[j:j + len(s)]:
                if dp[i][j] + 1 < dp[i + 1][j + len(s)]:
                    dp[i + 1][j + len(s)] = dp[i][j] + 1

if dp[N][len(T)] < INF:
    print(dp[N][len(T)])
else:
    print(-1)